关于后端:图论算法遍历基础

读完本文，你不仅学会了算法套路，还能够顺便去 LeetCode 上拿下如下题目：

797. 所有可能的门路（中等）

———–

常常有读者问我「图」这种数据结构，其实我在学习数据结构和算法的框架思维中说过，尽管图能够玩出更多的算法，解决更简单的问题，但实质上图能够认为是多叉树的延长。

面试口试很少呈现图相干的问题，就算有，大多也是简略的遍历问题，基本上能够齐全照搬多叉树的遍历。

那么，本文仍然秉持咱们号的格调，只讲「图」最实用的，离咱们最近的局部，让你心里对图有个直观的意识，文末我给出了其余经典图论算法，了解本文后应该都能够拿下的。

一幅图是由节点和边形成的，逻辑构造如下：

什么叫「逻辑构造」？就是说为了不便钻研，咱们把图形象成这个样子。

依据这个逻辑构造，咱们能够认为每个节点的实现如下：

/* 图节点的逻辑构造 */
class Vertex {
    int id;
    Vertex[] neighbors;}

看到这个实现，你有没有很相熟？它和咱们之前说的多叉树节点简直齐全一样：

/* 根本的 N 叉树节点 */
class TreeNode {
    int val;
    TreeNode[] children;}

所以说，图真的没啥浅近的，就是高级点的多叉树而已。

不过呢，下面的这种实现是「逻辑上的」，实际上咱们很少用这个 Vertex 类实现图，而是用常说的 邻接表和邻接矩阵 来实现。

比方还是方才那幅图：

用邻接表和邻接矩阵的存储形式如下：

邻接表很直观，我把每个节点 x 的街坊都存到一个列表里，而后把 x 和这个列表关联起来，这样就能够通过一个节点 x 找到它的所有相邻节点。

邻接矩阵则是一个二维布尔数组，咱们姑且称为 matrix，如果节点 x 和 y 是相连的，那么就把 matrix[x][y] 设为 true（上图中绿色的方格代表 true）。如果想找节点 x 的街坊，去扫一圈 matrix[x][..] 就行了。

如果用代码的模式来体现，邻接表和邻接矩阵大略长这样：

// 邻接矩阵
// graph[x] 存储 x 的所有街坊节点
List<Integer>[] graph;

// 邻接矩阵
// matrix[x][y] 记录 x 是否有一条指向 y 的边
boolean[][] matrix;

那么，为什么有这两种存储图的形式呢？必定是因为他们各有优劣。

对于邻接表，益处是占用的空间少。

你看邻接矩阵外面空着那么多地位，必定须要更多的存储空间。

然而，邻接表无奈疾速判断两个节点是否相邻。

比如说我想判断节点 1 是否和节点 3 相邻，我要去邻接表里 1 对应的街坊列表里查找 3 是否存在。但对于邻接矩阵就简略了，只有看看 matrix[1][3] 就晓得了，效率高。

所以说，应用哪一种形式实现图，要看具体情况。

好了，对于「图」这种数据结构，能看懂下面这些就绰绰够用了。

那你可能会问，咱们这个图的模型仅仅是「有向无权图」，不是还有什么加权图，无向图，等等……

其实，这些更简单的模型都是基于这个最简略的图衍生进去的。

有向加权图怎么实现？很简略呀：

如果是邻接表，咱们不仅仅存储某个节点 x 的所有街坊节点，还存储 x 到每个街坊的权重，不就实现加权有向图了吗？

如果是邻接矩阵，matrix[x][y] 不再是布尔值，而是一个 int 值，0 示意没有连贯，其余值示意权重，不就变成加权有向图了吗？

如果用代码的模式来体现，大略长这样：

// 邻接矩阵
// graph[x] 存储 x 的所有街坊节点以及对应的权重
List<int[]>[] graph;

// 邻接矩阵
// matrix[x][y] 记录 x 指向 y 的边的权重，0 示意不相邻
int[][] matrix;

无向图怎么实现？也很简略，所谓的「无向」，是不是等同于「双向」？

如果连贯无向图中的节点 x 和 y，把 matrix[x][y] 和 matrix[y][x] 都变成 true 不就行了；邻接表也是相似的操作，在 x 的街坊列表里增加 y，同时在 y 的街坊列表里增加 x。

把下面的技巧合起来，就变成了无向加权图……

好了，对于图的根本介绍就到这里，当初不论来什么乌七八糟的图，你心里应该都有底了。

上面来看看所有数据结构都逃不过的问题：遍历。

学习数据结构和算法的框架思维说过，各种数据结构被创造进去无非就是为了遍历和拜访，所以「遍历」是所有数据结构的根底。

图怎么遍历？还是那句话，参考多叉树，多叉树的遍历框架如下：

/* 多叉树遍历框架 */
void traverse(TreeNode root) {if (root == null) return;

    for (TreeNode child : root.children) {traverse(child);
    }
}

图和多叉树最大的区别是，图是可能蕴含环的，你从图的某一个节点开始遍历，有可能走了一圈又回到这个节点。

所以，如果图蕴含环，遍历框架就要一个 visited 数组进行辅助：

// 记录被遍历过的节点
boolean[] visited;
// 记录从终点到以后节点的门路
boolean[] onPath;

/* 图遍历框架 */
void traverse(Graph graph, int s) {if (visited[s]) return;
    // 通过节点 s，标记为已遍历
    visited[s] = true;
    // 做抉择：标记节点 s 在门路上
    onPath[s] = true;
    for (int neighbor : graph.neighbors(s)) {traverse(graph, neighbor);
    }
    // 撤销抉择：节点 s 来到门路
    onPath[s] = false;
}

留神 visited 数组和 onPath 数组的区别，因为二叉树算是非凡的图，所以用遍历二叉树的过程来了解下这两个数组的区别：

上述 GIF 形容了递归遍历二叉树的过程，在 visited 中被标记为 true 的节点用灰色示意，在 onPath 中被标记为 true 的节点用绿色示意，这下你能够了解它们二者的区别了吧。

如果让你解决门路相干的问题，这个 onPath 变量是必定会被用到的，比方拓扑排序中就有使用。

另外，你应该留神到了，这个 onPath 数组的操作很像回溯算法外围套路中做「做抉择」和「撤销抉择」，区别在于地位：回溯算法的「做抉择」和「撤销抉择」在 for 循环外面，而对 onPath 数组的操作在 for 循环里面。

在 for 循环外面和里面惟一的区别就是对根节点的解决。

比方上面两种多叉树的遍历：

void traverse(TreeNode root) {if (root == null) return;
    System.out.println("enter:" + root.val);
    for (TreeNode child : root.children) {traverse(child);
    }
    System.out.println("leave:" + root.val);
}

void traverse(TreeNode root) {if (root == null) return;
    for (TreeNode child : root.children) {System.out.println("enter:" + child.val);
        traverse(child);
        System.out.println("leave:" + child.val);
    }
}

前者会正确打印所有节点的进入和来到信息，而后者唯独会少打印整棵树根节点的进入和来到信息。

为什么回溯算法框架会用后者？因为回溯算法关注的不是节点，而是树枝，不信你看回溯算法外围套路外面的图。

显然，对于这里「图」的遍历，咱们应该把 onPath 的操作放到 for 循环里面，否则会漏掉记录起始点的遍历。

说了这么多 onPath 数组，再说下 visited 数组，其目标很显著了，因为图可能含有环，visited 数组就是避免递归反复遍历同一个节点进入死循环的。

当然，如果题目通知你图中不含环，能够把 visited 数组都省掉，根本就是多叉树的遍历。

上面咱们来看力扣第 797 题「所有可能门路」，函数签名如下：

List<List<Integer>> allPathsSourceTarget(int[][] graph);

题目输出一幅 有向无环图，这个图蕴含 n 个节点，标号为 0, 1, 2,..., n - 1，请你计算所有从节点 0 到节点 n - 1 的门路。

输出的这个 graph 其实就是「邻接表」示意的一幅图，graph[i] 存储这节点 i 的所有街坊节点。

比方输出 graph = [[1,2],[3],[3],[]]，就代表上面这幅图：

算法应该返回 [[0,1,3],[0,2,3]]，即 0 到 3 的所有门路。

解法很简略，以 0 为终点遍历图，同时记录遍历过的门路，当遍历到起点时将门路记录下来即可。

既然输出的图是无环的，咱们就不须要 visited 数组辅助了，间接套用图的遍历框架：

// 记录所有门路
List<List<Integer>> res = new LinkedList<>();
    
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    // 保护递归过程中通过的门路
    LinkedList<Integer> path = new LinkedList<>();
    traverse(graph, 0, path);
    return res;
}

/* 图的遍历框架 */
void traverse(int[][] graph, int s, LinkedList<Integer> path) {

    // 增加节点 s 到门路
    path.addLast(s);

    int n = graph.length;
    if (s == n - 1) {
        // 达到起点
        res.add(new LinkedList<>(path));
        path.removeLast();
        return;
    }

    // 递归每个相邻节点
    for (int v : graph[s]) {traverse(graph, v, path);
    }
    
    // 从门路移出节点 s
    path.removeLast();}

这道题就这样解决了，留神 Java 的语言个性，向 res 中增加 path 时须要拷贝一个新的列表，否则最终 res 中的列表都是空的。

最初总结一下，图的存储形式次要有邻接表和邻接矩阵，无论什么花里胡哨的图，都能够用这两种形式存储。

在口试中，最常考的算法是图的遍历，和多叉树的遍历框架是十分相似的。

当然，图还会有很多其余的乏味算法，比方二分图断定，环检测和拓扑排序（编译器循环援用检测就是相似的算法），最小生成树，Dijkstra 最短门路算法等等，有趣味的读者能够去看看，本文就到这了。

_____________

查看更多优质算法文章点击我的头像，手把手带你刷力扣，致力于把算法讲清楚！我的算法教程曾经取得 90k star，欢送点赞！

关于后端:图论算法遍历基础

图的逻辑构造和具体实现

图的遍历

题目实际

Just My Socks（注册教程内含优惠码）

关于后端:图论算法遍历基础

图的逻辑构造和具体实现

图的遍历

题目实际

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）