非某戎胸建图函数javaList[] buildGraph(int numCourses, int[][] prerequisites) {// 图中共有 numCourses 个节点List[] graph new LinkedList[numCourses];for (int i 0; i numCourses; i) {graph[i] new LinkedList();}for (int[] edge : prerequisites) {int from edge[1], to edge[0];// 添加一条从 from 指向 to 的有向边// 边的方向是「被依赖」关系即修完课程 from 才能修课程 tograph[from].add(to);}return graph;}环检测算法DFSjava// 记录一次递归堆栈中的节点boolean[] onPath;// 记录遍历过的节点防止走回头路boolean[] visited;// 记录图中是否有环boolean hasCycle false;boolean canFinish(int numCourses, int[][] prerequisites) {List[] graph buildGraph(numCourses, prerequisites);visited new boolean[numCourses];onPath new boolean[numCourses];for (int i 0; i numCourses; i) {// 遍历图中的所有节点traverse(graph, i);}// 只要没有循环依赖可以完成所有课程return !hasCycle;}void traverse(List[] graph, int s) {if (onPath[s]) {// 出现环hasCycle true;}if (visited[s] || hasCycle) {// 如果已经找到了环也不用再遍历了return;}// 前序代码位置visited[s] true;onPath[s] true;for (int t : graph[s]) {traverse(graph, t);}// 后序代码位置onPath[s] false;}BFSjava// 主函数public boolean canFinish(int numCourses, int[][] prerequisites) {// 建图有向边代表「被依赖」关系List[] graph buildGraph(numCourses, prerequisites);// 构建入度数组int[] indgree new int[numCourses];for (int[] edge : prerequisites) {int from edge[1], to edge[0];// 节点 to 的入度加一indgree[to];}// 根据入度初始化队列中的节点Queue q new LinkedList();for (int i 0; i numCourses; i) {if (indgree[i] 0) {// 节点 i 没有入度即没有依赖的节点// 可以作为拓扑排序的起点加入队列q.offer(i);}}// 记录遍历的节点个数int count 0;// 开始执行 BFS 循环while (!q.isEmpty()) {// 弹出节点 cur并将它指向的节点的入度减一int cur q.poll();count;for (int next : graph[cur]) {indgree[next]--;if (indgree[next] 0) {// 如果入度变为 0说明 next 依赖的节点都已被遍历q.offer(next);}}}// 如果所有节点都被遍历过说明不成环return count numCourses;}这段 BFS 算法的思路1、构建邻接表和之前一样边的方向表示「被依赖」关系。2、构建一个 indegree 数组记录每个节点的入度即 indegree[i] 记录节点 i 的入度。3、对 BFS 队列进行初始化将入度为 0 的节点首先装入队列。4、开始执行 BFS 循环不断弹出队列中的节点减少相邻节点的入度并将入度变为 0 的节点加入队列。5、如果最终所有节点都被遍历过count 等于节点数则说明不存在环反之则说明存在环。拓扑排序算法对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序是将G中所有顶点排成一个线性序列使得图中任意一对顶点u和v若边(u,v)∈E(G)则u在线性序列中出现在v之前。通常这样的线性序列称为满足拓扑次序(Topological Order)的序列简称拓扑序列。简单的说由某个集合上的一个偏序得到该集合上的一个全序这个操作称之为拓扑排序。DFSjava// 记录后序遍历结果List postorder new ArrayList();// 记录是否存在环boolean hasCycle false;boolean[] visited, onPath;// 主函数public int[] findOrder(int numCourses, int[][] prerequisites) {List[] graph buildGraph(numCourses, prerequisites);visited new boolean[numCourses];onPath new boolean[numCourses];// 遍历图for (int i 0; i numCourses; i) {traverse(graph, i);}// 有环图无法进行拓扑排序if (hasCycle) {return new int[]{};}// 逆后序遍历结果即为拓扑排序结果Collections.reverse(postorder);int[] res new int[numCourses];for (int i 0; i numCourses; i) {res[i] postorder.get(i);}return res;}// 图遍历函数void traverse(List[] graph, int s) {if (onPath[s]) {// 发现环hasCycle true;}if (visited[s] || hasCycle) {return;}// 前序遍历位置onPath[s] true;visited[s] true;for (int t : graph[s]) {traverse(graph, t);}// 后序遍历位置postorder.add(s);onPath[s] false;}BFSjava// 主函数public int[] findOrder(int numCourses, int[][] prerequisites) {// 建图和环检测算法相同List[] graph buildGraph(numCourses, prerequisites);// 计算入度和环检测算法相同int[] indgree new int[numCourses];for (int[] edge : prerequisites) {int from edge[1], to edge[0];indgree[to];}// 根据入度初始化队列中的节点和环检测算法相同Queue q new LinkedList();for (int i 0; i numCourses; i) {if (indgree[i] 0) {q.offer(i);}}// 记录拓扑排序结果int[] res new int[numCourses];// 记录遍历节点的顺序索引int count 0;// 开始执行 BFS 算法while (!q.isEmpty()) {int cur q.poll();// 弹出节点的顺序即为拓扑排序结果res[count] cur;count;for (int next : graph[cur]) {indgree[next]--;if (indgree[next] 0) {q.offer(next);}}}if (count ! numCourses) {// 存在环拓扑排序不存在return new int[]{};}return res;}二分图判定算法二分图的顶点集可分割为两个互不相交的子集图中每条边依附的两个顶点都分属于这两个子集且两个子集内的顶点不相邻。给你一幅「图」请你用两种颜色将图中的所有顶点着色且使得任意一条边的两个端点的颜色都不相同你能做到吗这就是图的「双色问题」其实这个问题就等同于二分图的判定问题如果你能够成功地将图染色那么这幅图就是一幅二分图反之则不是DFSjava// 记录图是否符合二分图性质private boolean ok true;// 记录图中节点的颜色false 和 true 代表两种不同颜色private boolean[] color;// 记录图中节点是否被访问过private boolean[] visited;// 主函数输入邻接表判断是否是二分图public boolean isBipartite(int[][] graph) {int n graph.length;color new boolean[n];visited new boolean[n];// 因为图不一定是联通的可能存在多个子图// 所以要把每个节点都作为起点进行一次遍历// 如果发现任何一个子图不是二分图整幅图都不算二分图for (int v 0; v n; v) {if (!visited[v]) {traverse(graph, v);}}return ok;}// DFS 遍历框架private void traverse(int[][] graph, int v) {// 如果已经确定不是二分图了就不用浪费时间再递归遍历了if (!ok) return;visited[v] true;for (int w : graph[v]) {if (!visited[w]) {// 相邻节点 w 没有被访问过// 那么应该给节点 w 涂上和节点 v 不同的颜色color[w] !color[v];// 继续遍历 wtraverse(graph, w);} else {// 相邻节点 w 已经被访问过// 根据 v 和 w 的颜色判断是否是二分图if (color[w] color[v]) {// 若相同则此图不是二分图ok false;}}}}BFSjava// 记录图是否符合二分图性质private boolean ok true;// 记录图中节点的颜色false 和 true 代表两种不同颜色private boolean[] color;// 记录图中节点是否被访问过private boolean[] visited;public boolean isBipartite(int[][] graph) {int n graph.length;color new boolean[n];visited new boolean[n];for (int v 0; v n; v) {if (!visited[v]) {// 改为使用 BFS 函数bfs(graph, v);}}return ok;}// 从 start 节点开始进行 BFS 遍历private void bfs(int[][] graph, int start) {Queue q new LinkedList();visited[start] true;q.offer(start);while (!q.isEmpty() ok) {int v q.poll();// 从节点 v 向所有相邻节点扩散for (int w : graph[v]) {if (!visited[w]) {// 相邻节点 w 没有被访问过// 那么应该给节点 w 涂上和节点 v 不同的颜色color[w] !color[v];// 标记 w 节点并放入队列visited[w] true;q.offer(w);} else {// 相邻节点 w 已经被访问过// 根据 v 和 w 的颜色判断是否是二分图if (color[w] color[v]) {// 若相同则此图不是二分图ok false;}}}}}Union-Find并查集大白话就是当我们需要判断两个元素是否在同一个集合里的时候我们就要想到用并查集。并查集主要有两个功能将两个元素添加到一个集合中。判断两个元素在不在同一个集合名称并查集直接体现了它的核心功能合并集合与查询元素所属集合。在英文中它通常被称为Union-Find数据结构或Disjoint-Set数据结构。并查集的基本思想是使用树形结构来表示每个集合树的根节点作为集合的代表元素。并查集核心特性快速查找能够快速判断两个元素是否属于同一集合快速合并能够快速将两个集合合并为一个路径压缩优化查找操作使树的高度尽量小按秩合并优化合并操作减少树的高度增长Union-Find 算法主要需要实现这两个 APIjavaclass UF {/* 将 p 和 q 连接 */public void union(int p, int q);/* 判断 p 和 q 是否连通 */public boolean connected(int p, int q);/* 返回图中有多少个连通分量 */public int count();}这里所说的「连通」是一种等价关系也就是说具有如下三个性质1、自反性节点p和p是连通的。2、对称性如果节点p和q连通那么q和p也连通。3、传递性如果节点p和q连通q和r连通那么p和r也连通。比如说有一幅图09 任意两个不同的点都不连通调用connected都会返回 false连通分量为 10 个。如果现在调用union(0, 1)那么 0 和 1 被连通连通分量降为 9 个。再调用union(1, 2)这时 0,1,2 都被连通调用connected(0, 2)也会返回 true连通分量变为 8 个。基础算法设定树的每个节点有一个指针指向其父节点如果是根节点的话这个指针指向自己。比如说刚才那幅 10 个节点的图一开始的时候没有相互连通就是这样javaclass UF {// 记录连通分量private int count;// 节点 x 的节点是 parent[x]private int[] parent;/* 构造函数n 为图的节点总数 */public UF(int n) {// 一开始互不连通this.count n;// 父节点指针初始指向自己parent new int[n];for (int i 0; i n; i)parent[i] i;}/* 其他函数 */}如果某两个节点被连通则让其中的任意一个节点的根节点接到另一个节点的根节点上javapublic void union(int p, int q) {int rootP find(p);int rootQ find(q);if (rootP rootQ)return;// 将两棵树合并为一棵parent[rootP] rootQ;// parent[rootQ] rootP 也一样count--; // 两个分量合二为一}/* 返回某个节点 x 的根节点 */private int find(int x) {// 根节点的 parent[x] xwhile (parent[x] ! x)x parent[x];return x;}/* 返回当前的连通分量个数 */public int count() {return count;}这样如果节点p和q连通的话它们一定拥有相同的根节点javapublic boolean connected(int p, int q) {int rootP find(p);int rootQ find(q);return rootP rootQ;}至此Union-Find 算法就基本完成了。那么这个算法的复杂度是多少呢我们发现主要 APIconnected和union中的复杂度都是find函数造成的所以说它们的复杂度和find一样。find主要功能就是从某个节点向上遍历到树根其时间复杂度就是树的高度。我们可能习惯性地认为树的高度就是logN但这并不一定。logN的高度只存在于平衡二叉树对于一般的树可能出现极端不平衡的情况使得「树」几乎退化成「链表」树的高度最坏情况下可能变成N。所以说上面这种解法find,union,connected的时间复杂度都是 O(N)。这个复杂度很不理想的你想图论解决的都是诸如社交网络这样数据规模巨大的问题对于union和connected的调用非常频繁每次调用需要线性时间完全不可忍受。平衡性优化要知道哪种情况下可能出现不平衡现象关键在于union过程javapublic void union(int p, int q) {int rootP find(p);int rootQ find(q);if (rootP rootQ)return;// 将两棵树合并为一棵parent[rootP] rootQ;// parent[rootQ] rootP 也可以count--;}我们一开始就是简单粗暴的把p所在的树接到q所在的树的根节点下面那么这里就可能出现「头重脚轻」的不平衡状况比如下面这种局面长此以往树可能生长得很不平衡。我们其实是希望小一些的树接到大一些的树下面这样就能避免头重脚轻更平衡一些。解决方法是额外使用一个size数组记录每棵树包含的节点数我们不妨称为「重量」javaclass UF {private int count;private int[] parent;// 新增一个数组记录树的“重量”private int[] size;public UF(int n) {this.count n;parent new int[n];// 最初每棵树只有一个节点// 重量应该初始化 1size new int[n];for (int i 0; i n; i) {parent[i] i;size[i] 1;}}/* 其他函数 */}比如说size[3] 5表示以节点3为根的那棵树总共有5个节点。这样我们可以修改一下union方法javapublic void union(int p, int q) {int rootP find(p);int rootQ find(q);if (rootP rootQ)return;// 小树接到大树下面较平衡if (size[rootP] size[rootQ]) {parent[rootQ] rootP;size[rootP] size[rootQ];} else {parent[rootP] rootQ;size[rootQ] size[rootP];}count--;}这样通过比较树的重量就可以保证树的生长相对平衡树的高度大致在logN这个数量级极大提升执行效率。此时find,union,connected的时间复杂度都下降为 O(logN)即便数据规模上亿所需时间也非常少。路径压缩其实我们并不在乎每棵树的结构长什么样只在乎根节点。因为无论树长啥样树上的每个节点的根节点都是相同的所以能不能进一步压缩每棵树的高度使树高始终保持为常数如图所示这样每个节点的父节点就是整棵树的根节点find就能以 O(1) 的时间找到某一节点的根节点相应的connected和union复杂度都下降为 O(1)。要做到这一点主要是修改find函数逻辑非常简单但你可能会看到两种不同的写法。第一种是在find中加一行代码javaprivate int find(int x) {while (parent[x] ! x) {// 这行代码进行路径压缩parent[x] parent[parent[x]];x parent[x];}return x;}用语言描述就是每次 while 循环都会把一对儿父子节点改到同一层这样每次调用find函数向树根遍历的同时顺手就将树高缩短了。路径压缩的第二种写法是这样java// 第二种路径压缩的 find 方法public int find(int x) {if (parent[x] ! x) {parent[x] find(parent[x]);}return parent[x];}这个递归过程有点不好理解你可以自己手画一下递归过程。我把这个函数做的事情翻译成迭代形式方便你理解它进行路径压缩的原理java// 这段迭代代码方便你理解递归代码所做的事情public int find(int x) {// 先找到根节点int root x;while (parent[root] ! root) {root parent[root];}// 然后把 x 到根节点之间的所有节点直接接到根节点下面int old_parent parent[x];while (x ! root) {parent[x] root;x old_parent;old_parent parent[old_parent];}return root;}这种路径压缩的效果如下比起第一种路径压缩显然这种方法压缩得更彻底直接把一整条树枝压平一点意外都没有。就算一些极端情况下产生了一棵比较高的树只要一次路径压缩就能大幅降低树高从 摊还分析 的角度来看所有操作的平均时间复杂度依然是 O(1)所以从效率的角度来说推荐你使用这种路径压缩算法。另外如果使用路径压缩技巧那么size数组的平衡优化就不是特别必要了。所以你一般看到的 Union Find 算法应该是如下实现javaclass UF {// 连通分量个数private int count;// 存储每个节点的父节点private int[] parent;// n 为图中节点的个数public UF(int n) {this.count n;parent new int[n];for (int i 0; i n; i) {parent[i] i;}}// 将节点 p 和节点 q 连通public void union(int p, int q) {int rootP find(p);int rootQ find(q);if (rootP rootQ)return;parent[rootQ] rootP;// 两个连通分量合并成一个连通分量count--;}// 判断节点 p 和节点 q 是否连通public boolean connected(int p, int q) {int rootP find(p);int rootQ find(q);return rootP rootQ;}public int find(int x) {if (parent[x] ! x) {parent[x] find(parent[x]);}return parent[x];}// 返回图中的连通分量个数public int count() {return count;}}Union-Find 算法的复杂度可以这样分析构造函数初始化数据结构需要 O(N) 的时间和空间复杂度连通两个节点union、判断两个节点的连通性connected、计算连通分量count所需的时间复杂度均为 O(1)。到这里相信你已经掌握了 Union-Find 算法的核心逻辑总结一下我们优化算法的过程1、用parent数组记录每个节点的父节点相当于指向父节点的指针所以parent数组内实际存储着一个森林若干棵多叉树。2、用size数组记录着每棵树的重量目的是让union后树依然拥有平衡性保证各个 API 时间复杂度为 O(logN)而不会退化成链表影响操作效率。3、在find函数中进行路径压缩保证任意树的高度保持在常数使得各个 API 时间复杂度为 O(1)。使用了路径压缩之后可以不使用size数组的平衡优化。优点查找和合并操作的平均时间复杂度接近O(1)实现简单易于理解空间复杂度低只需要两个数组适用于处理大量动态连通性问题缺点不支持分裂操作将一个集合分成两个不方便查询集合中的所有元素在某些特殊情况下性能可能退化应用场景Kruskal最小生成树算法在Kruskal算法中并查集是核心数据结构。该算法按权重从小到大遍历边使用并查集判断加入某条边是否会形成环从而高效构建最小生成树。网络连通性问题并查集可高效解决动态连通性问题比如判断网络中两个节点是否连通、社交网络中用户间的关系连接等。当关系变化时只需执行简单的union操作判断连通性时使用find操作即可。等价类划分在编译器设计、电路分析等领域并查集可用于等价类识别与合并。当系统发现两个元素等价时执行union操作需要判断等价关系时使用find操作这种动态维护等价关系的能力正是并查集的优势所在。判断无向图中的环当向无向图中添加边时如果边的两个端点已在同一个集合中则添加这条边会形成环。在很多图算法和网络设计问题中都可以使用这一特性。Kruskal 最小生成树算法Kruskal 的 关键就是 并查集算法先说「树」和「图」的根本区别树不会包含环图可以包含环。如果一幅图没有环完全可以拉伸成一棵树的模样。说的专业一点树就是「无环连通图」。那么什么是图的「生成树」呢其实按字面意思也好理解就是在图中找一棵包含图中的所有节点的树。专业点说生成树是含有图中所有顶点的「无环连通子图」。容易想到一幅图可以有很多不同的生成树比如下面这幅图红色的边就组成了两棵不同的生成树对于加权图每条边都有权重所以每棵生成树都有一个权重和。比如上图右侧生成树的权重和显然比左侧生成树的权重和要小。那么最小生成树很好理解了所有可能的生成树中权重和最小的那棵生成树就叫「最小生成树」。PS一般来说我们都是在无向加权图中计算最小生成树的所以使用最小生成树算法的现实场景中图的边权重一般代表成本、距离这样的标量。所谓最小生成树就是图中若干边的集合我们后文称这个集合为mst最小生成树的英文缩写你要保证这些边1、包含图中的所有节点。2、形成的结构是树结构即不存在环。3、权重和最小。前两条其实可以很容易地利用 Union-Find 算法做到关键在于第 3 点如何保证得到的这棵生成树是权重和最小的。这里就用到了贪心思路将所有边按照权重从小到大排序从权重最小的边开始遍历如果这条边和mst中的其它边不会形成环则这条边是最小生成树的一部分将它加入mst集合否则这条边不是最小生成树的一部分不要把它加入mst集合。这样最后mst集合中的边就形成了最小生成树算法代码如下javaint minimumCost(int n, int[][] connections) {// 城市编号为 1...n所以初始化大小为 n 1UF uf new UF(n 1);// 对所有边按照权重从小到大排序Arrays.sort(connections, (a, b) - (a[2] - b[2]));// 记录最小生成树的权重之和int mst 0;for (int[] edge : connections) {int u edge[0];int v edge[1];int weight edge[2];// 若这条边会产生环则不能加入 mstif (uf.connected(u, v)) {continue;}// 若这条边不会产生环则属于最小生成树mst weight;uf.union(u, v);}// 保证所有节点都被连通// 按理说 uf.count() 1 说明所有节点被连通// 但因为节点 0 没有被使用所以 0 会额外占用一个连通分量return uf.count() 2 ? mst : -1;