\(17.1\)图的构建

1.图的\(API\)

public class Graph {
    private final int V;
    private int E;
    private Bag<Integer>[] adj;

    public Graph(int V) {
        this.V = V;
        this.E = 0;
        adj = (Bag<Integer>[])new Bag[V];// Create array of lists.
        for (int v = 0; v < V; v += 1) {
            adj[v] = new Bag<Integer>();
        }
    }

    public Graph(In in) {
        this(in.readInt()); // Read V and construct this graph.
        int E = in.readInt(); // Read E.
        for (int i = 0; i < E; i++) { // Add an edge.
            int v = in.readInt(); // Read a vertex,
            int w = in.readInt(); // read another vertex,
            addEdge(v, w); // and add edge connecting them.
        }
    }

    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 += 1;
    }

    public Iterable<Integer> adj(int v) {
        return adj[v];
    }
}

2.\(dfs\)

public class DepthFirstSearch {
    private boolean[] marked;
    private int count;

    public DepthFirstSearch(Graph G, int s) {
        marked = new boolean[G.V];
        dfs(G, s);
    }

    private void dfs(Graph G, int v) {
        marked[v] = true;
        count += 1;
        for (int w : G.adj[v]) {
            if (!marked[w]) dfs(G, w);
        }

    }

    public boolean marked(int w) {
        return marked[w];
    }

    public int count() {
        return count;
    }
}

3.路径的寻找