淄博 网站建设,摄影网站规划设计书,清空wordpress数据库表,北京软件公司引言
拓扑排序是有向无环图#xff08;DAG#xff09;中的一种线性排序#xff0c;使得对于图中的每一条有向边 ( u \rightarrow v )#xff0c;顶点 ( u ) 在排序中出现在顶点 ( v ) 之前。本文将详细介绍两种实现拓扑排序的算法#xff1a;Kahn算法和基于深度优先搜索DAG中的一种线性排序使得对于图中的每一条有向边 ( u \rightarrow v )顶点 ( u ) 在排序中出现在顶点 ( v ) 之前。本文将详细介绍两种实现拓扑排序的算法Kahn算法和基于深度优先搜索DFS的算法。
目录
Kahn算法基于DFS的算法
Kahn算法
定义
Kahn算法是一种基于入度的拓扑排序算法。该算法通过不断移除入度为0的顶点及其边来构建拓扑排序。
算法步骤
初始化计算图中所有顶点的入度并将所有入度为0的顶点添加到一个队列中。构建排序从队列中取出一个顶点将其添加到拓扑排序的结果中并移除该顶点及其所有出边。对于每个被移除的出边如果目标顶点的入度减为0则将该顶点添加到队列中。检测环重复步骤2直到队列为空。如果排序结果中的顶点数量小于图中的顶点数量则说明图中存在环无法进行拓扑排序。
示例
假设我们有一个有向无环图顶点集合为 ({A, B, C, D, E, F})边集合为 ({(A, C), (B, C), (B, D), (C, E), (D, F), (E, F)})。 #mermaid-svg-jH16KKWaDR9jPW0N {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-jH16KKWaDR9jPW0N .error-icon{fill:#552222;}#mermaid-svg-jH16KKWaDR9jPW0N .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-jH16KKWaDR9jPW0N .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-jH16KKWaDR9jPW0N .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-jH16KKWaDR9jPW0N .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-jH16KKWaDR9jPW0N .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-jH16KKWaDR9jPW0N .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-jH16KKWaDR9jPW0N .marker{fill:#333333;stroke:#333333;}#mermaid-svg-jH16KKWaDR9jPW0N .marker.cross{stroke:#333333;}#mermaid-svg-jH16KKWaDR9jPW0N svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-jH16KKWaDR9jPW0N .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-jH16KKWaDR9jPW0N .cluster-label text{fill:#333;}#mermaid-svg-jH16KKWaDR9jPW0N .cluster-label span{color:#333;}#mermaid-svg-jH16KKWaDR9jPW0N .label text,#mermaid-svg-jH16KKWaDR9jPW0N span{fill:#333;color:#333;}#mermaid-svg-jH16KKWaDR9jPW0N .node rect,#mermaid-svg-jH16KKWaDR9jPW0N .node circle,#mermaid-svg-jH16KKWaDR9jPW0N .node ellipse,#mermaid-svg-jH16KKWaDR9jPW0N .node polygon,#mermaid-svg-jH16KKWaDR9jPW0N .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-jH16KKWaDR9jPW0N .node .label{text-align:center;}#mermaid-svg-jH16KKWaDR9jPW0N .node.clickable{cursor:pointer;}#mermaid-svg-jH16KKWaDR9jPW0N .arrowheadPath{fill:#333333;}#mermaid-svg-jH16KKWaDR9jPW0N .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-jH16KKWaDR9jPW0N .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-jH16KKWaDR9jPW0N .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-jH16KKWaDR9jPW0N .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-jH16KKWaDR9jPW0N .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-jH16KKWaDR9jPW0N .cluster text{fill:#333;}#mermaid-svg-jH16KKWaDR9jPW0N .cluster span{color:#333;}#mermaid-svg-jH16KKWaDR9jPW0N div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-jH16KKWaDR9jPW0N :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} A C B D E F Kahn算法实现
下面是用Java实现Kahn算法的代码示例
import java.util.*;public class KahnAlgorithm {private int vertices; // 顶点数量private ListInteger[] adjList; // 邻接表public KahnAlgorithm(int vertices) {this.vertices vertices;adjList new List[vertices];for (int i 0; i vertices; i) {adjList[i] new ArrayList();}}// 添加边public void addEdge(int src, int dest) {adjList[src].add(dest);}// Kahn算法实现的拓扑排序public void topologicalSort() {int[] inDegree new int[vertices];for (int i 0; i vertices; i) {for (int dest : adjList[i]) {inDegree[dest];}}QueueInteger queue new LinkedList();for (int i 0; i vertices; i) {if (inDegree[i] 0) {queue.add(i);}}ListInteger topOrder new ArrayList();while (!queue.isEmpty()) {int u queue.poll();topOrder.add(u);for (int neighbor : adjList[u]) {if (--inDegree[neighbor] 0) {queue.add(neighbor);}}}if (topOrder.size() ! vertices) {System.out.println(图中存在环无法进行拓扑排序);return;}System.out.println(拓扑排序结果);for (int node : topOrder) {System.out.print(node );}}public static void main(String[] args) {KahnAlgorithm graph new KahnAlgorithm(6);graph.addEdge(0, 2);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(2, 4);graph.addEdge(3, 5);graph.addEdge(4, 5);graph.topologicalSort();}
}代码注释 类和构造函数 public class KahnAlgorithm {private int vertices; // 顶点数量private ListInteger[] adjList; // 邻接表public KahnAlgorithm(int vertices) {this.vertices vertices;adjList new List[vertices];for (int i 0; i vertices; i) {adjList[i] new ArrayList();}}KahnAlgorithm 类包含图的顶点数量和邻接表并有一个构造函数来初始化这些变量。 添加边 public void addEdge(int src, int dest) {adjList[src].add(dest);
}addEdge 方法用于向图中添加边。 Kahn算法的拓扑排序 public void topologicalSort() {int[] inDegree new int[vertices];for (int i 0; i vertices; i) {for (int dest : adjList[i]) {inDegree[dest];}}QueueInteger queue new LinkedList();for (int i 0; i vertices; i) {if (inDegree[i] 0) {queue.add(i);}}ListInteger topOrder new ArrayList();while (!queue.isEmpty()) {int u queue.poll();topOrder.add(u);for (int neighbor : adjList[u]) {if (--inDegree[neighbor] 0) {queue.add(neighbor);}}}if (topOrder.size() ! vertices) {System.out.println(图中存在环无法进行拓扑排序);return;}System.out.println(拓扑排序结果);for (int node : topOrder) {System.out.print(node );}
}topologicalSort 方法实现了Kahn算法进行拓扑排序。 主函数 public static void main(String[] args) {KahnAlgorithm graph new KahnAlgorithm(6);graph.addEdge(0, 2);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(2, 4);graph.addEdge(3, 5);graph.addEdge(4, 5);graph.topologicalSort();
}main 方法创建一个图并进行拓扑排序。
Kahn算法的执行过程图解 #mermaid-svg-BF2NtbGN5vQPbIaQ {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-BF2NtbGN5vQPbIaQ .error-icon{fill:#552222;}#mermaid-svg-BF2NtbGN5vQPbIaQ .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-BF2NtbGN5vQPbIaQ .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-BF2NtbGN5vQPbIaQ .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-BF2NtbGN5vQPbIaQ .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-BF2NtbGN5vQPbIaQ .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-BF2NtbGN5vQPbIaQ .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-BF2NtbGN5vQPbIaQ .marker{fill:#333333;stroke:#333333;}#mermaid-svg-BF2NtbGN5vQPbIaQ .marker.cross{stroke:#333333;}#mermaid-svg-BF2NtbGN5vQPbIaQ svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-BF2NtbGN5vQPbIaQ .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-BF2NtbGN5vQPbIaQ .cluster-label text{fill:#333;}#mermaid-svg-BF2NtbGN5vQPbIaQ .cluster-label span{color:#333;}#mermaid-svg-BF2NtbGN5vQPbIaQ .label text,#mermaid-svg-BF2NtbGN5vQPbIaQ span{fill:#333;color:#333;}#mermaid-svg-BF2NtbGN5vQPbIaQ .node rect,#mermaid-svg-BF2NtbGN5vQPbIaQ .node circle,#mermaid-svg-BF2NtbGN5vQPbIaQ .node ellipse,#mermaid-svg-BF2NtbGN5vQPbIaQ .node polygon,#mermaid-svg-BF2NtbGN5vQPbIaQ .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-BF2NtbGN5vQPbIaQ .node .label{text-align:center;}#mermaid-svg-BF2NtbGN5vQPbIaQ .node.clickable{cursor:pointer;}#mermaid-svg-BF2NtbGN5vQPbIaQ .arrowheadPath{fill:#333333;}#mermaid-svg-BF2NtbGN5vQPbIaQ .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-BF2NtbGN5vQPbIaQ .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-BF2NtbGN5vQPbIaQ .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-BF2NtbGN5vQPbIaQ .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-BF2NtbGN5vQPbIaQ .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-BF2NtbGN5vQPbIaQ .cluster text{fill:#333;}#mermaid-svg-BF2NtbGN5vQPbIaQ .cluster span{color:#333;}#mermaid-svg-BF2NtbGN5vQPbIaQ div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-BF2NtbGN5vQPbIaQ :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 取出顶点F 取出顶点E 取出顶点D 取出顶点C 取出顶点B 取出顶点A 初始化入度和队列 入度为0 入度为0 取出A 取出B 取出C 取出D 取出E 取出F 结果: A, B, C, D, E, F 队列: F 结果: A, B, C, D, E 队列: E, F 移除E的出边 结果: A, B, C, D 队列: D, E 移除D的出边 结果: A, B, C 队列: C, D 移除C的出边 结果: A, B 队列: B, C 移除B的出边 结果: A 队列: A, B 移除A的出边 加入队列 顶点 A 加入队列 顶点 B 基于DFS的算法
定义
基于DFS的拓扑排序算法通过递归的方式遍历图的每个顶点并在访问完所有邻接顶点后将顶点压入栈中最终从栈顶依次弹出顶点即为拓扑排序结果。
算法步骤
初始化创建一个栈用于存储排序结果标记所有顶点为未访问。DFS遍历对于每个未访问的顶点进行DFS遍历。递归访问该顶点的所有邻接顶点访问完毕后将该顶点压入栈中。构建排序重复步骤2直到所有顶点都被访问。最后从栈顶
依次弹出顶点即为拓扑排序结果。
示例
假设我们有一个有向无环图顶点集合为 ({A, B, C, D, E, F})边集合为 ({(A, C), (B, C), (B, D), (C, E), (D, F), (E, F)})。 #mermaid-svg-L5XiFInSIf9Ewj2N {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-L5XiFInSIf9Ewj2N .error-icon{fill:#552222;}#mermaid-svg-L5XiFInSIf9Ewj2N .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-L5XiFInSIf9Ewj2N .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-L5XiFInSIf9Ewj2N .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-L5XiFInSIf9Ewj2N .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-L5XiFInSIf9Ewj2N .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-L5XiFInSIf9Ewj2N .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-L5XiFInSIf9Ewj2N .marker{fill:#333333;stroke:#333333;}#mermaid-svg-L5XiFInSIf9Ewj2N .marker.cross{stroke:#333333;}#mermaid-svg-L5XiFInSIf9Ewj2N svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-L5XiFInSIf9Ewj2N .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-L5XiFInSIf9Ewj2N .cluster-label text{fill:#333;}#mermaid-svg-L5XiFInSIf9Ewj2N .cluster-label span{color:#333;}#mermaid-svg-L5XiFInSIf9Ewj2N .label text,#mermaid-svg-L5XiFInSIf9Ewj2N span{fill:#333;color:#333;}#mermaid-svg-L5XiFInSIf9Ewj2N .node rect,#mermaid-svg-L5XiFInSIf9Ewj2N .node circle,#mermaid-svg-L5XiFInSIf9Ewj2N .node ellipse,#mermaid-svg-L5XiFInSIf9Ewj2N .node polygon,#mermaid-svg-L5XiFInSIf9Ewj2N .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-L5XiFInSIf9Ewj2N .node .label{text-align:center;}#mermaid-svg-L5XiFInSIf9Ewj2N .node.clickable{cursor:pointer;}#mermaid-svg-L5XiFInSIf9Ewj2N .arrowheadPath{fill:#333333;}#mermaid-svg-L5XiFInSIf9Ewj2N .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-L5XiFInSIf9Ewj2N .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-L5XiFInSIf9Ewj2N .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-L5XiFInSIf9Ewj2N .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-L5XiFInSIf9Ewj2N .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-L5XiFInSIf9Ewj2N .cluster text{fill:#333;}#mermaid-svg-L5XiFInSIf9Ewj2N .cluster span{color:#333;}#mermaid-svg-L5XiFInSIf9Ewj2N div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-L5XiFInSIf9Ewj2N :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} A C B D E F 基于DFS的算法实现
下面是用Java实现基于DFS的拓扑排序算法的代码示例
import java.util.*;public class DFSTopologicalSort {private int vertices; // 顶点数量private ListInteger[] adjList; // 邻接表public DFSTopologicalSort(int vertices) {this.vertices vertices;adjList new List[vertices];for (int i 0; i vertices; i) {adjList[i] new ArrayList();}}// 添加边public void addEdge(int src, int dest) {adjList[src].add(dest);}// 递归实现DFSprivate void DFS(int vertex, boolean[] visited, StackInteger stack) {visited[vertex] true;for (int neighbor : adjList[vertex]) {if (!visited[neighbor]) {DFS(neighbor, visited, stack);}}stack.push(vertex);}// 基于DFS的拓扑排序public void topologicalSort() {StackInteger stack new Stack();boolean[] visited new boolean[vertices];for (int i 0; i vertices; i) {if (!visited[i]) {DFS(i, visited, stack);}}System.out.println(拓扑排序结果);while (!stack.isEmpty()) {System.out.print(stack.pop() );}}public static void main(String[] args) {DFSTopologicalSort graph new DFSTopologicalSort(6);graph.addEdge(0, 2);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(2, 4);graph.addEdge(3, 5);graph.addEdge(4, 5);graph.topologicalSort();}
}代码注释 类和构造函数 public class DFSTopologicalSort {private int vertices; // 顶点数量private ListInteger[] adjList; // 邻接表public DFSTopologicalSort(int vertices) {this.vertices vertices;adjList new List[vertices];for (int i 0; i vertices; i) {adjList[i] new ArrayList();}}DFSTopologicalSort 类包含图的顶点数量和邻接表并有一个构造函数来初始化这些变量。 添加边 public void addEdge(int src, int dest) {adjList[src].add(dest);
}addEdge 方法用于向图中添加边。 递归实现DFS private void DFS(int vertex, boolean[] visited, StackInteger stack) {visited[vertex] true;for (int neighbor : adjList[vertex]) {if (!visited[neighbor]) {DFS(neighbor, visited, stack);}}stack.push(vertex);
}DFS 方法递归访问顶点及其邻接顶点并在访问完所有邻接顶点后将顶点压入栈中。 基于DFS的拓扑排序 public void topologicalSort() {StackInteger stack new Stack();boolean[] visited new boolean[vertices];for (int i 0; i vertices; i) {if (!visited[i]) {DFS(i, visited, stack);}}System.out.println(拓扑排序结果);while (!stack.isEmpty()) {System.out.print(stack.pop() );}
}topologicalSort 方法实现了基于DFS的拓扑排序输出拓扑排序结果。 主函数 public static void main(String[] args) {DFSTopologicalSort graph new DFSTopologicalSort(6);graph.addEdge(0, 2);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(2, 4);graph.addEdge(3, 5);graph.addEdge(4, 5);graph.topologicalSort();
}main 方法创建一个图并进行拓扑排序。
基于DFS算法的执行过程图解 #mermaid-svg-m8IAiSUIvwZHcnIv {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-m8IAiSUIvwZHcnIv .error-icon{fill:#552222;}#mermaid-svg-m8IAiSUIvwZHcnIv .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-m8IAiSUIvwZHcnIv .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-m8IAiSUIvwZHcnIv .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-m8IAiSUIvwZHcnIv .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-m8IAiSUIvwZHcnIv .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-m8IAiSUIvwZHcnIv .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-m8IAiSUIvwZHcnIv .marker{fill:#333333;stroke:#333333;}#mermaid-svg-m8IAiSUIvwZHcnIv .marker.cross{stroke:#333333;}#mermaid-svg-m8IAiSUIvwZHcnIv svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-m8IAiSUIvwZHcnIv .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-m8IAiSUIvwZHcnIv .cluster-label text{fill:#333;}#mermaid-svg-m8IAiSUIvwZHcnIv .cluster-label span{color:#333;}#mermaid-svg-m8IAiSUIvwZHcnIv .label text,#mermaid-svg-m8IAiSUIvwZHcnIv span{fill:#333;color:#333;}#mermaid-svg-m8IAiSUIvwZHcnIv .node rect,#mermaid-svg-m8IAiSUIvwZHcnIv .node circle,#mermaid-svg-m8IAiSUIvwZHcnIv .node ellipse,#mermaid-svg-m8IAiSUIvwZHcnIv .node polygon,#mermaid-svg-m8IAiSUIvwZHcnIv .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-m8IAiSUIvwZHcnIv .node .label{text-align:center;}#mermaid-svg-m8IAiSUIvwZHcnIv .node.clickable{cursor:pointer;}#mermaid-svg-m8IAiSUIvwZHcnIv .arrowheadPath{fill:#333333;}#mermaid-svg-m8IAiSUIvwZHcnIv .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-m8IAiSUIvwZHcnIv .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-m8IAiSUIvwZHcnIv .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-m8IAiSUIvwZHcnIv .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-m8IAiSUIvwZHcnIv .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-m8IAiSUIvwZHcnIv .cluster text{fill:#333;}#mermaid-svg-m8IAiSUIvwZHcnIv .cluster span{color:#333;}#mermaid-svg-m8IAiSUIvwZHcnIv div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-m8IAiSUIvwZHcnIv :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 输出结果 DFS遍历顶点1 DFS遍历顶点0 初始化 从栈顶依次弹出顶点 拓扑排序结果:0 1 3 2 4 5 访问顶点1 顶点1 顶点1的邻接顶点3 访问顶点3 顶点3的邻接顶点5 顶点5已访问,跳过 将顶点3压入栈中 将顶点1压入栈中 访问顶点0 顶点0 顶点0的邻接顶点2 访问顶点2 顶点2的邻接顶点4 访问顶点4 顶点4的邻接顶点5 访问顶点5 将顶点5压入栈中 将顶点4压入栈中 将顶点2压入栈中 创建栈 标记所有顶点为未访问 结论
通过上述讲解和实例代码我们详细展示了Kahn算法和基于DFS的拓扑排序算法的定义、步骤及其实现。希望这篇博客对您有所帮助 如果您觉得这篇文章对您有帮助请关注我的CSDN博客点赞并收藏这篇文章您的支持是我持续创作的动力 关键内容总结
Kahn算法的定义和实现基于DFS的拓扑排序算法的定义和实现两种算法的执行过程图解 推荐阅读深入探索设计模式专栏详细讲解各种设计模式的应用和优化。点击查看深入探索设计模式。 特别推荐设计模式实战专栏深入解析设计模式的实际应用提升您的编程技巧。点击查看设计模式实战。
如有任何疑问或建议欢迎在评论区留言讨论。谢谢阅读
