图的遍历

797. 所有可能的路径

图的存储

如果需要对图进行一系列的操作，那么首选需要搞清楚图的存储方式

不同于二叉树，图的节点之间的关系相对复杂

对于一颗二叉树，邻接节点只有 0，1 或 2 个，所以用两个左右孩子指针域来保存邻接节点。「这里的邻接节点仅仅指指向的节点，而不包括被指向的节点」

对于一个图来说，其邻接节点可能有很多个，远大于树的孩子节点个数。所以这里有两种方法来存储图的信息：邻接表 & 邻接矩阵

• 邻接表：把节点的邻接节点存储在一个列表中

• 邻接矩阵：维护一个二维数组 $matrix$$matrix$。如果节点 $i$$i$ 和节点 $j$$j$ 之间存在边，那么 $matrix[i][j]=1$$matrix[i][j]=1$；反之则为 $0$$0$

代码形式如下：

// 邻接表
// graph[x] 存储 x 的所有邻居节点
List<Integer>[] graph;
// 递归
for (Integer v : graph[x]) {
    traversal(graph, v, ...);
}

// 邻接矩阵
// matrix[x][y] 记录 x 是否有一条指向 y 的边
boolean[][] matrix;
// 递归
for (int i = 0; i < matrix[x].length; i++) {
    // 存在边，进行递归
    if (matrix[x][i] == 1) {
        traversal(matrix, i, ...);
    }
}

// 相比于递归的操作，邻接表更为方便

邻接矩阵 $\Rightarrow$$\Rightarrow$ 邻接表

对于无权图来说 $edges[i]=(u_i,v_i)$$edges[i] = (u_i, v_i)$

private List<Integer>[] buildGraph (int[][] edges, int n) {
    List<Integer>[] graph = new ArrayList[n + 1];
    for (int i = 1; i <= n; i++) graph[i] = new ArrayList<Integer>();
    for (int[] edge : edges) {
        int from = edge[0];
        int to = edge[1];
        graph[from].add(to);
    }
    return graph;
}

对于有权图来说 $edges[i]=(u_i,v_i,w_i)$$edges[i] = (u_i, v_i, w_i)$

private List<int[]>[] buildGraph (int[][] edges, int n) {
    List<int[]>[] graph = new ArrayList[n + 1];
    for (int i = 1; i <= n; i++) graph[i] = new ArrayList<int[]>();
    for (int[] edge : edges) {
        int from = edge[0];
        int to = edge[1];
        int weight = edge[2];
        graph[from].add(new int[]{to, weight});
    }
    return graph;
}

优劣比较：

树的先序遍历

在说图的遍历之间，我们首先复习一下树的遍历（只看先序遍历，其他顺序遍历同理）

下面代码的功能：输出树的所有从根节点到叶子结点的路径

// 记录所有路径的结果集
private List<List<Integer>> res;
public List<List<Integer>> allPath(TreeNode root) {
    res = new ArrayList<>();
    traversal(root, new ArrayList<>());
    return res;
}
// 套路：四个阶段 (判空，先序，递归，后序)
private void traversal(TreeNode root, List<Integer> path) {
    // 判空：由于在进入递归的时候没有判空，故此处需要判空
    if (root == null) return ;
    // 先序：首次进入节点，加入路径中
    path.add(root.val);
    
    // 判断路径是否满足加入结果集中的条件
    // 即：判断当前节点是否是叶子节点
    if (root.left == null && root.right == null) {
        res.add(new ArrayList<>(path));
    }
    
    // 递归：此处没有判空，直接进入递归：root.left 和 root.right 可能为空
    traversal(root.left, path);
    traversal(root.right, path);
    // 后序：最后离开节点，从路径中去除
    path.remove(path.size() - 1);
}

图 & 树的分析对比

前面铺垫了这么多，现在正式进入本文的核心内容

其中图和树有异曲同工之处，看了下面的分析相信这种感觉更加的强烈

无环图

先来看看最简单的一种类型：无环图。这种类型不需要考虑节点是否被访问过，因为不存在环，无需考虑无限递归的可能性

树的先序遍历指出了套路的四个阶段，即：判空，先序，递归，后序。我们详细分析树和图每个阶段的不同

1. 先来看判空和递归部分

// 递归
for (Integer v : graph[x]) {
    traversal(graph, v, ...);
}

如果 graph[x] == null是不会进入递归中的，所以对于图来说，可以不需要第一步判空

对于树的递归部分来说，没有判断root.left == null和root.right == null，所以需要第一步判空

traversal(root.left, path);
traversal(root.right, path);

2. 先序和后序阶段其实基本一样，这里就不详细阐述了

3. 处理阶段

根据题目的不同要求，会有不同的处理操作。就此题需要得到所有路径来说，如果是树的话，完整路径的判断标志：是否为叶子节点；如果是图的话，完整路径的判断标志：是否到达了最后一个节点

// 树
if (root.left == null && root.right == null) {
    res.add(new ArrayList<>(path));
}
// 图
if (v == graph.length - 1) {
    res.add(new ArrayList<>(list));
}

有环图

其实有环图和无环图的唯一区别就是加了一个visited[]数组来标记节点的访问情况

然后只需要在先序部分做少许修改即可，直接上代码

多说一句：为什么对于图的遍历函数中多了一个节点参数？

其实很简单，如果是树，root就是当前需要处理的节点；而对于图，我们并不能从graph[][]中判断出当前需要处理的节点，所以需要明确指出

boolean[] visited;
private void traversal(int[][] graph, int v, ...) {
    // 处理有环图的操作
    // 如果被访问过，直接跳过
    if (visited[v]) return ;
    // 未访问过，先标记
    visited[v] = true;

    // 先序
    // 递归
    // 后序
}

图的遍历

直接看一个无环图的题目 所有可能的路径

x
private List<List<Integer>> res;
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    res = new ArrayList<>();
    traversal(graph, 0, new ArrayList<>());
    return res;
}
private void traversal(int[][] graph, int s, List<Integer> list) {
    // 先序
    list.add(s);
    if (s == graph.length - 1) {
        res.add(new ArrayList<>(list));
    }
    // 递归
    for (int v : graph[s]) {
        traversal(graph, v, list);
    }
    // 后序
    list.remove(list.size() - 1);
}