无向图

1. 邻接表数组

邻接表数组时一个以顶点为索引的列表数组，其中的每个元素都是和该顶点相邻的顶点列表。

我们可以使用邻接表数组来存储图。

2. 图数据类型

public class Graph {
    private final int V;         // 顶点数目
    private int E;               // 边的数目
    private Bag<Integer>[] adj; // 领接表，用背包数据类型来存储，需要自己实现背包类
    /**
     * 创建一个含有 V 个顶点但不含有边的图
     */
    public Graph(int V) {
        this.V = V;
        this.E = 0;
        adj = (Bag<Integer>[]) new Bag[V]; // 创建邻接表
        for (int v = 0; v < V; v++) { // 将所有邻接表初始化为空
            adj[v] = new Bag<Integer>();
        }
    }
    public int V() {
        return V;
    }
    public int E() {
        return E;
    }
    public void addEdge(int v, int w) {
        adj[v].add(w); // 将 w 添加到 v 的链表中
        adj[w].add(v); // 将 v 添加到 w 的链表中
        E++;
    }
    /**
     * adjacent 是相邻的英文单词; 该方法放回和 v 相邻的所有顶点
     */
    public Iterable<Integer> adj(int v) {
        return adj[v];
    }
}

3. 深度优先搜索（DFS）

要搜索一幅图，只需用一个递归方法来遍历所有顶点。

在访问其中一个顶点时：

• 将它标记为已访问；
• 递归的访问它的所有没有被标记过的邻居顶点。

这种方法就称为深度优先搜索（DFS）。

public class DepthFirstSearch {
    private boolean[] marked; // 存储着是结点是否被标记过的信息数组
    private int count;

    /**
     * @param s: 起始结点
     */
    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++;
        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;
    }
}

4. 使用 DFS 查找图中的路径

import java.util.Stack;
/**
 * 找出给定的起点 s 到与它连通的所有顶点的路径
 */
public class DepthFirstPaths {
    private boolean[] marked;
    private int[] edgeTo;        // 从起点到一个顶点的已知路径上的最后一个顶点
    private final int s;          // 起点

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

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

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

    public Iterable<Integer> PathTo(int v) {
        if (!hasPathTo(v))
            return null;
        Stack<Integer> path = new Stack<Integer>();
        for (int x = v; x != s; x = edgeTo[x]) {
            path.push(x);
        }

        path.push(s);
        return path;
    }
}

5. 广度优先搜索（BFS）

广度优先搜索使用了一个队列来保存所有已经被标记过但其邻接表还未被检查过的顶点。

先将顶点加入队列，然后重复以下步骤直到队列为空：

• 取队列中的下一个顶点 v 并标记它；
• 将与 v 相邻的所有未标记过的顶点加入队列。

  6. 使用 BFS 查找图中的路径

  ```java /**

• 找出图中从构造函数得到的起点 s 到与其它所有顶点的最短路径 */ import java.util.LinkedList; import java.util.Queue; import java.util.Stack;

public class BreadthFirstPaths { private boolean[] marked; // 到达该顶点的最短路径已知嘛 private int[] edgeTo; // 到达该顶点的已知路径上的最后一个顶点 private final int s; // 起点

public BreadthFirstPaths(Graph G, int s) {
    marked = new boolean[G.V()];
    edgeTo = new int[G.V()];
    this.s = s;
    bfs(G, s);
}

private void bfs(Graph G, int s) {
    Queue<Integer> queue = new LinkedList<>(); // LinkedList 实现了 Queue 接口，可以当队列使用
    marked[s] = true; // 标记起点
    queue.add(s); // 将它加入队列

    while (!queue.isEmpty()) {
        int v = queue.remove(); // 从队列中删去下一顶点
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                edgeTo[w] = v;
                marked[w] = true;
                queue.add(w);
            }
        }
    }
}

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

public Iterable<Integer> PathTo(int v) {
    if (!hasPathTo(v))
        return null;
    Stack<Integer> path = new Stack<>();
    for (int x = v; x != s; x = edgeTo[x]) {
        path.push(x);
    }

    path.push(s);
    return path;
}

} ```