Topological Sort 위상 정렬
비순환 방향 그래프 일 때 정렬가능하다.
* DAG (Directed Acyclic Graph) - 사이클이 없는 방향 그래프
책에서는 DFS를 이용한 방법으로 구현하였다.
나는 이해가 잘 안되서 다른 사람들의 설명을 추가로 보았다.
BFS, DFS, 진입 간선을 이용한 여러 방법이 있었는데 진입 간선을 이용한 방법이 제일 편했다.
구현 방향
그래프에서 진입 간선이 없는 정점을 큐에 추가한다.
큐에서 하나를 꺼내서 간선을 제거한다.
진입 간선이 없는 정점을 큐에 추가한다.
반복
void Graph::TopologicalSort() {
int num = getVortexcnt();
ind.resize(num + 1, 0);
VORTEX* temp = graph->Vhead;
EDGE* Etemp = nullptr;
while (temp) {
Etemp = temp->Ehead;
while (Etemp) {
ind[Etemp->to->Data]++;
Etemp = Etemp->next;
}
temp = temp->next;
}
int i = 0;
while (i < num) {
if (ind[i] == 0) {
q.push(getVortex(i));
}
i++;
}
q.pop();
while (!q.empty()) {
temp = q.front();
q.pop();
std::cout << temp->Data << " ";
Etemp = temp->Ehead;
while (Etemp) {
ind[Etemp->to->Data]--;
if (ind[Etemp->to->Data] == 0)
q.push(Etemp->to);
Etemp = Etemp->next;
}
}
std::cout << "\n";
clear();
}