DAG에 대한 무작위 선형 확장을 만드는 C++ 프로그램

여기서 우리는 방향성 비순환 그래프(DAG)의 랜덤 선형 확장을 생성하는 방법을 볼 것입니다. 선형 확장은 기본적으로 DAG의 토폴로지 정렬입니다. 그래프가 아래와 같다고 생각합시다 -

방향성 비순환 그래프의 위상 정렬은 정점의 선형 순서입니다. 방향 그래프의 모든 모서리 u-v에 대해 정점 u는 순서에서 정점 v보다 먼저 옵니다.

소스 정점이 대상 정점 다음에 올 것이라는 것을 알고 있으므로 스택을 사용하여 이전 요소를 저장해야 합니다. 모든 노드를 완료한 후 스택에서 간단히 표시할 수 있습니다.

입력

출력

토폴로지 정렬 순서 이후의 노드 − 5 4 2 3 1 0

알고리즘

topoSort(u, 방문, 스택)

입력 - 시작 정점 u, 방문한 노드를 추적하기 위한 배열. 노드를 저장할 스택입니다.

출력 − 스택에서 정점을 토폴로지 순서로 정렬합니다.

Begin
   mark u as visited
   for all vertices v which is adjacent with u, do
      if v is not visited, then
         topoSort(c, visited, stack)
      done
      push u into stack
End

topologicalSorting(그래프) 수행

입력 - 주어진 방향성 비순환 그래프.

출력 − 노드의 순서입니다.

Begin
   initially mark all nodes as unvisited
   for all nodes v of the graph, do
      if v is not visited, then
         topoSort(i, visited, stack)
      done
      pop and print all elements from the stack
End

예시

#include<iostream>
#include<stack>
#define NODE 6
using namespace std;
int graph[NODE][NODE] = {
   {0, 0, 0, 0, 0, 0},
   {0, 0, 0, 0, 0, 0},
   {0, 0, 0, 1, 0, 0},
   {0, 1, 0, 0, 0, 0},
   {1, 1, 0, 0, 0, 0},
   {1, 0, 1, 0, 0, 0}
};
void topoSort(int u, bool visited[], stack<int> &stk) {
   visited[u] = true; //set as the node v is visited
   for(int v = 0; v<NODE; v++) {
      if(graph[u][v]){ //for allvertices v adjacent to u
         if(!visited[v])
            topoSort(v, visited, stk);
      }
   }
   stk.push(u); //push starting vertex into the stack
}
void performTopologicalSort() {
   stack<int> stk;
   bool vis[NODE];
   for(int i = 0; i<NODE; i++)
      vis[i] = false; //initially all nodes are unvisited
   for(int i = 0; i<NODE; i++)
      if(!vis[i]) //when node is not visited
         topoSort(i, vis, stk);
   while(!stk.empty()) {
      cout << stk.top() << " ";
      stk.pop();
   }
}
main() {
   cout << "Nodes after topological sorted order: ";
   performTopologicalSort();
}

출력

Nodes after topological sorted order: 5 4 2 3 1 0