中国网站建设新闻,优秀网站架构,为拟建设的网站申请一个域名,江门提供网站制作平台一、拓扑排序
拓扑排序是基于依赖关系的节点#xff0c;根据依赖关系而生成的序列。节点和依赖关系往往要生成有向无环图。类似的问题有#xff1a;穿衣服裤子的先后关系#xff0c;生成穿衣序列/专业课程与前置课程形成的课程学习序列/代码编译依赖关系形成的编译顺序序列…一、拓扑排序
拓扑排序是基于依赖关系的节点根据依赖关系而生成的序列。节点和依赖关系往往要生成有向无环图。类似的问题有穿衣服裤子的先后关系生成穿衣序列/专业课程与前置课程形成的课程学习序列/代码编译依赖关系形成的编译顺序序列。
public class Graph {private int v; // 顶点的个数private LinkedListInteger adj[]; // 邻接表public Graph(int v) {this.v v;adj new LinkedList[v];for (int i0; iv; i) {adj[i] new LinkedList();}}public void addEdge(int s, int t) { // s先于t边s-tadj[s].add(t);}
}
二、实现
0x00Kahn 算法
根据邻接表很容易计算出每个节点的入度。 遍历每个入度将入度为0的节点放入队列。 队列不空循环 取出队首元素输出他然后遍历他的邻接节点将邻接节点入度-1如果邻接节点恰好为0将节点放入队列。 时间复杂度求入度O(ve),循环输出O(ve)合起来O(ve) 空间复杂度入度数组O(v),队列O(v) public void topoSortByKahn() {int[] inDegree new int[v]; // 统计每个顶点的入度for (int i 0; i v; i) {for (int j 0; j adj[i].size(); j) {int w adj[i].get(j); // i-winDegree[w];}}LinkedListInteger queue new LinkedList();for (int i 0; i v; i) {if (inDegree[i] 0) queue.add(i);}while (!queue.isEmpty()) {int i queue.remove();System.out.print(- i);for (int j 0; j adj[i].size(); j) {int k adj[i].get(j);inDegree[k]--;if (inDegree[k] 0) queue.add(k);}}
}0x01 DFS 深度优先搜索算法
深度优先搜索是要一通到底的所以需要将邻接表返过来改成逆邻接表。方法遍历邻接表对i的每个邻接节点j都将i加到j的逆邻接表中。图的深度优先搜索不跟树一样没有根节点所以要尝试从每个节点都开始一次自然需要visited数组防止重复。对某个节点深度遍历完之后再输出。时间复杂度求入度O(ve),顶点两次 边一次 空间复杂度入度数组O(v),队列O(v) public void topoSortByDFS() {// 先构建逆邻接表边s-t表示s依赖于tt先于sLinkedListInteger inverseAdj[] new LinkedList[v];for (int i 0; i v; i) { // 申请空间inverseAdj[i] new LinkedList();}for (int i 0; i v; i) { // 通过邻接表生成逆邻接表for (int j 0; j adj[i].size(); j) {int w adj[i].get(j); // i-winverseAdj[w].add(i); // w-i}}boolean[] visited new boolean[v];for (int i 0; i v; i) { // 深度优先遍历图if (visited[i] false) {visited[i] true;dfs(i, inverseAdj, visited);}}
}private void dfs(int vertex, LinkedListInteger inverseAdj[], boolean[] visited) {for (int i 0; i inverseAdj[vertex].size(); i) {int w inverseAdj[vertex].get(i);if (visited[w] true) continue;visited[w] true;dfs(w, inverseAdj, visited);} // 先把vertex这个顶点可达的所有顶点都打印出来之后再打印它自己System.out.print(- vertex);
}显然用于拓扑排序的图是不可以成环的。自然拓扑排序算法可以用于检测图中的环。对于kahn算法极端化思维如果所有的节点形成大环那么没有入度为0的节点也就不会有任何输出。普通思维如果存在环总会到一个位置没有任何节点入度为0。就会少输出节点。如果输出的节点总结点意味着存在环。
三、思考题
[1]在今天的讲解中我们用图表示依赖关系的时候如果 a 先于 b 执行我们就画一条从 a 到 b 的有向边反过来如果 a 先于 b我们画一条从 b 到 a 的有向边表示 b 依赖 a那今天讲的 Kahn 算法和 DFS 算法还能否正确工作呢如果不能应该如何改造一下呢
1.如果有向边反向代表依赖关系则Kahn算法无法工作改造方法是1.1把对入度的计算改为对出度的计算即首先输出出度为0的节点然后依次把与该节点相邻的节点的出度都减1重复此过程直到输出所有节点1.2 改成逆连接表计算入度而DFS算法中则会输出相反的结果由于邻接表和逆邻接表正好是相反的因此改造方法是在DFS中把对逆邻接表的的访问改为对邻接表的访问即可。
[2]我们今天讲了两种拓扑排序算法的实现思路Kahn 算法和 DFS 深度优先搜索算法如果换做 BFS 广度优先搜索算法还可以实现吗 2.采用BFS算法无法保证在某个结点输出之前先输出其所有依赖的节点因为有可能该节点和其所依赖的某个节点可能在BFS算法中处于同一个层次因为这两个节点可能都和某个节点相邻因此采用BFS算法有可能会输出不正确的拓扑次序。
笔记整理来源 王争 数据结构与算法之美
