图的拓扑排序代码
2021/8/29 6:08:21
本文主要是介绍图的拓扑排序代码,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1 // A C++ program to print topological 2 // sorting of a DAG 3 #include <iostream> 4 #include <list> 5 #include <stack> 6 using namespace std; 7 8 // Class to represent a graph 9 class Graph { 10 // No. of vertices' 11 int V; 12 13 // Pointer to an array containing adjacency listsList 14 list<int>* adj; 15 16 // A function used by topologicalSort 17 void topologicalSortUtil(int v, bool visited[], 18 stack<int>& Stack); 19 20 public: 21 // Constructor 22 Graph(int V); 23 24 // function to add an edge to graph 25 void addEdge(int v, int w); 26 27 // prints a Topological Sort of 28 // the complete graph 29 void topologicalSort(); 30 }; 31 32 Graph::Graph(int V) 33 { 34 this->V = V; 35 adj = new list<int>[V]; 36 } 37 38 void Graph::addEdge(int v, int w) 39 { 40 // Add w to v’s list. 41 adj[v].push_back(w); 42 } 43 44 // A recursive function used by topologicalSort 45 void Graph::topologicalSortUtil(int v, bool visited[], 46 stack<int>& Stack) 47 { 48 // Mark the current node as visited. 49 visited[v] = true; 50 51 // Recur for all the vertices 52 // adjacent to this vertex 53 list<int>::iterator i; 54 for (i = adj[v].begin(); i != adj[v].end(); ++i) 55 if (!visited[*i]) 56 topologicalSortUtil(*i, visited, Stack); 57 58 // Push current vertex to stack 59 // which stores result 60 Stack.push(v); 61 } 62 63 // The function to do Topological Sort. 64 // It uses recursive topologicalSortUtil() 65 void Graph::topologicalSort() 66 { 67 stack<int> Stack; 68 69 // Mark all the vertices as not visited 70 bool* visited = new bool[V]; 71 for (int i = 0; i < V; i++) 72 visited[i] = false; 73 74 // Call the recursive helper function 75 // to store Topological 76 // Sort starting from all 77 // vertices one by one 78 for (int i = 0; i < V; i++) 79 if (visited[i] == false) 80 topologicalSortUtil(i, visited, Stack); 81 82 // Print contents of stack 83 while (Stack.empty() == false) { 84 cout << Stack.top() << " "; 85 Stack.pop(); 86 } 87 } 88 89 // Driver Code 90 int main() 91 { 92 // Create a graph given in the above diagram 93 Graph g(6); 94 g.addEdge(5, 2); 95 g.addEdge(5, 0); 96 g.addEdge(4, 0); 97 g.addEdge(4, 1); 98 g.addEdge(2, 3); 99 g.addEdge(3, 1); 100 101 cout << "Following is a Topological Sort of the given " 102 "graph \n"; 103 104 // Function Call 105 g.topologicalSort(); 106 107 return 0; 108 }
这篇关于图的拓扑排序代码的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)