방향성 비순환 그래프의 위상 정렬을 수행하기 위해 DFS를 적용하는 C++ 프로그램

DAG(Directed Acyclic Graph)의 토폴로지 정렬은 정점 u가 순서에서 v 앞에 오는 모든 방향 모서리 uv에 대해 정점의 선형 정렬입니다. 그래프가 DAG가 아닌 경우 그래프에 대한 Topological Sorting이 불가능합니다.

함수 및 의사코드

Begin
   function topologicalSort():
   a) Mark the current node as visited.
   b) Recur for all the vertices adjacent to this vertex.
   c) Push current vertex to stack which stores result.
End
Begin
   function topoSort() which uses recursive topological sort() function:
   a) Mark all the vertices which are not visited.
   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;
   //declaration of functions
   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;
   //Recur for all the vertices adjacent to this vertex.
   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];
   //Mark all the vertices which are not visited.
   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;
}

출력

Topological Sort of the given graph
5 4 1 3 2 0