【算法】图的存储和遍历（Java）

  今天学习图的存储和遍历。

1.图的存储

图的存储一般采用领接矩阵和邻接表。这里讲解邻接表。简单来说，邻接表就是每个顶点定义一个列表，记录该顶点的所有出边。这里可以用 ArrayList 来存储每个节点的出边。

// 邻接表
List<List<Integer>> edges = new ArrayList<>();
// 每个节点 new 一个 List 存放出边
for (int i = 0; i < n; i++) {
    edges.add(new ArrayList<>());
}

2.图的遍历

图的遍历一般是 DFS 和 BFS。

2.1 DFS 遍历

和之前讲过的 DFS 一样，沿着一条路都到头，再退回到有未访问的岔路口，继续访问其他路径。重复这样的 *** 作直到遍历完整个图。这里有两个概念：

• 连通分量：无向图中，两个顶点可以互相到达就称这两个顶点连通。所以顶点连通就是连通图；否则是非连通图，其中的极大连通子图是连通分量。
• 强连通分量：有向图中，两个顶点可以互相到达就称这两个顶点强连通。所以顶点强连通就是强连通图；否则是非强连通图，其中的极大强连通子图是强连通分量。

遍历图就要对所有的连通块都进行遍历。DFS 过程中经过的点标记为已访问，下次不再处理，直到所有的顶点都被标记。

public class Main {
    private static int n;
    private static List<List<Integer>> edges;
    private static boolean[] visited;

    public static void main(String[] args) {
        n = 4;  // 4 个点的图
        /*
         *   0 —— 1
         *   |  / |
         *   3 —— 2
         */
        edges = new ArrayList<>();
        visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            edges.add(new ArrayList<>());
        }
        edges.get(0).add(1);
        edges.get(0).add(3);

        edges.get(1).add(0);
        edges.get(1).add(2);
        edges.get(1).add(3);

        edges.get(2).add(1);
        edges.get(2).add(3);

        edges.get(3).add(0);
        edges.get(3).add(1);
        edges.get(3).add(2);

        DFSTrave();
    }
    public static void DFSTrave() {
        for (int u = 0; u < n; u++) {
            if (visited[u] == false) {
                DFS(u);
            }
        }
    }
    public static void DFS(int u) {
        System.out.println(u + " ");
        visited[u] = true;
        for (int v : edges.get(u)) {
            if (visited[v] == false) {
                DFS(v);
            }
        }
    }
}

2.2 BFS 遍历

和之前讲过的 BFS 一样，每到岔路口，用队列存储未访问过的节点，依次遍历。

public class Main {
    private static int n;
    private static List<List<Integer>> edges;
    private static boolean[] visited;

    public static void main(String[] args) {
        n = 4;  // 4 个点的图
        /*
         *   0 —— 1
         *   |  / |
         *   3 —— 2
         */
        edges = new ArrayList<>();
        visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            edges.add(new ArrayList<>());
        }
        edges.get(0).add(1);
        edges.get(0).add(3);

        edges.get(1).add(0);
        edges.get(1).add(2);
        edges.get(1).add(3);

        edges.get(2).add(1);
        edges.get(2).add(3);

        edges.get(3).add(0);
        edges.get(3).add(1);
        edges.get(3).add(2);

        BFSTrave();
    }
    public static void BFSTrave() {
        for (int u = 0; u < n; u++) {
            if (visited[u] == false) {
                BFS(u);
            }
        }
    }
    public static void BFS(int u) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(u);
        visited[u] = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                System.out.println(cur + " ");
                for (int v : edges.get(i)) {
                    if (!visited[v]) {
                        queue.offer(v);
                        visited[v] = true;
                    }
                }
            }
        }
    }
}

3.例题：力扣1971. 寻找图中是否存在路径^[1]

有一个具有 n个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。

请你确定是否存在从顶点 start 开始，到顶点 end 结束的 有效路径 。

给你数组 edges 和整数 n、start和end，如果从 start 到 end 存在 有效路径 ，则返回 true，否则返回 false 。

示例 1：

输入：n = 3, edges = [[0,1],[1,2],[2,0]], start = 0, end = 2
输出：true
解释：存在由顶点 0 到顶点 2 的路径:
  0 → 1 → 2 
  0 → 2

示例 2：

输入：n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], start = 0, end = 5
输出：false
解释：不存在由顶点 0 到顶点 5 的路径.

这里给出 DFS 的方法：

class Solution {
    private List<List<Integer>> eg;
    private boolean[] visited;
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        eg = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            eg.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            eg.get(edge[0]).add(edge[1]);
            eg.get(edge[1]).add(edge[0]);
        }
        visited = new boolean[n];
        DFS(source);
        return visited[destination];
    }
    public void DFS(int source) {
        visited[source] = true;
        for (int v : eg.get(source)) {
            if (visited[v] == false) {
                DFS(v);
            }
        }
    }
}

Reference

[1]力扣1971. 寻找图中是否存在路径：https://leetcode-cn.com/problems/find-if-path-exists-in-graph/

欢迎关注公众号。