/*
AOV Topological, 위상정렬
*/
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph
{
int vertices; //정점의 개수
list<int> *adj;
void topologicalSortUtil(int v, bool visited[], stack<int> &Stack)//위상정렬에서 쓰이는 함수
{
visited[v] = true; //현재 노드를 방문했다고 표시
//정점에 연결되어있는 모든 정점에 대해 재귀
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); i++)
if (!visited[*i])
topologicalSortUtil(*i, visited, Stack);
Stack.push(v); //현재 정점 스택에 넣는다
}
public:
Graph(int v) :vertices(v)
{
adj = new list<int>[vertices];
}
~Graph()
{
delete[]adj;
}
void addEdge(int v, int w)
{
adj[v].push_back(w); //정점끼리 연결
}
void topologicalSort()
{
stack<int> Stack;
//모든 정점을 방문하지 않음으로 표시
bool *visited = new bool[vertices];
for (int i = 0; i < vertices; i++)
visited[i] = false;
//각 정점마저 앞서 정의한 함수 호출
for (int i = 0; i < vertices; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack);
//위상정렬된 결과 출력
while (Stack.empty() == false)
{
cout << Stack.top() << " ";
Stack.pop();
}
cout << endl;
}
};
int main(void)
{
Graph g(6);
//Figure 6.37
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(0, 3);
g.addEdge(1, 4);
g.addEdge(2, 4);
g.addEdge(2, 5);
g.addEdge(3, 4);
g.addEdge(3, 5);
cout << "위상정렬된 결과" << endl;
g.topologicalSort();
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서, https://github.com/Alexoner/dsa/blob/master/ds/graph/search/topologicalSort.cpp
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
*https://github.com/Alexoner/dsa/blob/master/ds/graph/search/topologicalSort.cpp