그래프에서 토폴로지 정렬을 수행할 수 있는지 확인하는 C++ 프로그램

방향성 비순환 그래프에서 위상 정렬을 사용하여 선형 순서로 정점을 정렬할 수 있습니다.

위상 정렬은 방향성 비순환 그래프에서만 작동합니다. 방향성 비순환 그래프(DAG)에는 토폴로지 정렬이 두 개 이상 있을 수 있습니다.

다음 C++ 프로그램에서는 그래프에서 사이클의 존재를 확인하기 위해 토폴로지 정렬을 수행합니다.

알고리즘

Topo_Sort 함수의 경우

Begin
   Define function Topo_Sort()
      Declare x to the integer datatype, vstd[] of the Boolean array and Stack as a stack.
         Pass them as parameter.
      Initialize vstd[x] = true to mark the current node as vstd.
      Declare an iterator i.
      for (i = a[x].begin(); i != a[x].end(); ++i)
         if (!vstd[*i]) then
      Call Topo_Sort(*i, vstd, Stack) function.
   Call push() function to insert values into stack.
End.

예시

#include<iostream>
#include <list>
#include <stack>
using namespace std;
class grph { // Class to represent a graph
   int ver;
   list<int> *a; // Pointer to an array containing adjacency listsList
   void Topo_Sort(int x, bool vstd[], stack<int> &Stack); // A function used by TopologicalSort
   public:
      grph(int ver); // Constructor of grpf
   void Insert_Edge(int x, int y); // to insert an edge to graph
   void Topol_Sort(); // prints a Topological Sort of the complete graph
};
grph::grph(int ver) {
   this->ver = ver;
   a = new list<int>[ver];
}
void grph::Insert_Edge(int x, int y) {
   a[x].push_back(y); // Add y to x’s list.
}
// A recursive function used by Topol_Sort
void grph::Topo_Sort(int x, bool vstd[], stack<int> &Stack) {
   vstd[x] = true; // Mark the current node as vstd.
   list<int>::iterator i;
   for (i = a[x].begin(); i != a[x].end(); ++i)
      if (!vstd[*i])
         Topo_Sort(*i, vstd, Stack);
   // Push current vertex to stack which stores result
   Stack.push(x);
}
void grph::Topol_Sort() {
   stack<int> Stack;
   // Mark all the vertices as not vstd
   bool *vstd = new bool[ver];
   for (int i = 0; i < ver; i++)
      vstd[i] = false;
   for (int i = 0; i < ver; i++)
      if (vstd[i] == false)
         Topo_Sort(i, vstd, Stack);
   while (Stack.empty() == false) {
      cout << Stack.top() << " ";
      Stack.pop();
   }
}
int main() {
   grph g(6); // Create a graph given in the above diagram
   g.Insert_Edge(5, 2);
   g.Insert_Edge(5, 0);
   g.Insert_Edge(4, 0);
   g.Insert_Edge(4, 1);
   g.Insert_Edge(2, 3);
   g.Insert_Edge(3, 1);
   cout << "Topological Sort of the graph is: \n";
   g.Topol_Sort();
   return 0;
}

출력

Topological Sort of the graph is:
5 4 2 3 1 0