C ++程序应用DFS对有向无环图进行拓扑排序

Z时代
2024-01-10
分类：综合

DAG（有向无环图）的拓扑排序是顶点的线性排序，这样对于每个有向边uv，在此排序中，顶点u在v之前。如果该图不是DAG，则无法对图进行拓扑排序。

函数和伪代码

Begin
   function topologicalSort():
   a) Mark the current node as visited.
   b) 为与该顶点相邻的所有顶点递归。
   c) Push current vertex to stack which stores result.
End
Begin
   function topoSort() which uses recursive topological sort() function:
   a) 标记所有未访问的顶点。
   b) Call the function topologicalSort().
   c) Print the content.
End

示例

#include<iostream>
#include <list>
#include <stack>
using namespace std;
class G {
   int n;
   list<int> *adj;
   //功能声明
   void topologicalSort(int v, bool visited[], stack<int> &Stack);
   public:
   G(int n); //constructor
   void addEd(int v, int w);
   void topoSort();
};
G::G(int n) {
   this->n = n;
   adj = new list<int> [n];
}
void G::addEd(int v, int w) // add the edges to the graph. {
   adj[v].push_back(w); //add w to v’s list
}
void G::topologicalSort(int v, bool visited[], stack<int> &Stack) {
   visited[v] = true; //mark current node as visited
   list<int>::iterator i;
   //为与该顶点相邻的所有顶点递归。
   for (i = adj[v].begin(); i != adj[v].end(); ++i)
      if (!visited[*i])
         topologicalSort(*i, visited, Stack);
         Stack.push(v);
}
void G::topoSort() {
   stack<int> Stack;
   bool *visited = new bool[n];
   //标记所有未访问的顶点。
   for (int i = 0; i < n; i++)
      visited[i] = false;
      for (int i = 0; i < n; i++)
         if (visited[i] == false)
            //Call the function topologicalSort().
            topologicalSort(i, visited, Stack);
         while (Stack.empty() == false) {
            cout << Stack.top() << " "; //print the element
            Stack.pop();
         }
}
int main() {
   G g(6);
   g.addEd(4, 2);
   g.addEd(5, 1);
   g.addEd(4, 0);
   g.addEd(3, 1);
   g.addEd(1, 3);
   g.addEd(3, 2);
   cout << " Topological Sort of the given graph \n";
   g.topoSort();
   return 0;
}