Site Search:

Graph

Graph is a data structure that DFS and BFS operate on. The space is O(E + V), add edge cost is O(logV).

Code:

import java.util.*;
public class Graph {
    int V = 0;
    int E = 0;
    Set<Integer>[] adj;
    public Graph(int V) {
        this.V = V;
        adj = (Set<Integer>[])new HashSet[V];
        for(int i = 0; i < V; i++) {
            adj[i] = new HashSet<>();
        }
    }
    public int V() { return V;}
    public int E() { return E;}
    public void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }
    public Iterable<Integer> adj(int v) {
        return adj[v];
    }

}

Examples:

Digraph







MST






SPT