[그래프 알고리즘]위상정렬

DAG Directed Acyclic Graph

DAG는 사이클이 없는 방향 그래프를 의미합니다.

나가는 엣지만 있고 들어오는 엣지가 없는 노드를 선택하여 DFS 순회하면 모든 노드를 방문할 수 있습니다.

위상정렬 Topological Sort

위상정렬이란 DAG인 그래프의 노드를 어떤 순서대로 나열하는 것으로,

위상정렬된 그래프의 노드열에서는 뒤에 오는 노드에서 앞에 노드로 가는 경로는 존재하지 않습니다.

한 DAG의 위상 정렬 결과는 여러개일 수 있습니다.

위상정렬된 노드들을 2차원 평면에 놓는다면, 엣지들을 왼쪽에서 오른쪽으로만 향하게 할 수 있습니다.

DFS로 구현

위상정렬은 DFS로 간단하게 구현됩니다.

한 노드에서 연결된 다른 노드들을 모두 순회하고, 자신의 노드 번호를 리스트에 넣으면 됩니다.

그러면 그 리스트에는 위상정렬의 역순으로 노드들의 번호가 저장되어 있으므로, 이를 뒤집으면 위상정렬된 노드들의 번호가 됩니다.

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	#define N_NODE 10
	vector<int> adjList[N_NODE];
	void addEdge(int u, int v){
	adjList[u].push_back(v);
	}
	vector<bool> visited(N_NODE, false);
	vector<int> topologicalOrder;
	void dfs(int here){
	// 방문 표시하기
	visited[here] = true;
	for(int there : adjList[here]){
	// 방문하지 않았다면 DFS
	if(!visited[there]) dfs(there);
	}
	// 마지막에 리스트에 현재 노드 넣기
	topologicalOrder.push_back(here);
	}
	int main(){
	// 사이클이 존재하지 않는 방향 그래프
	addEdge(3, 4);
	addEdge(7, 1);
	addEdge(1, 2);
	addEdge(2, 3);
	addEdge(9, 2);
	addEdge(8, 3);
	addEdge(5, 7);
	addEdge(6, 0);
	addEdge(5, 6);
	addEdge(0, 1);
	addEdge(5, 8);
	// 방문하지 않은 모든 노드에 대해 DFS
	for(int i=0;i<N_NODE;i++){
	if(!visited[i]) dfs(i);
	}
	// 결과 뒤집기
	reverse(topologicalOrder.begin(), topologicalOrder.end());
	for(int node : topologicalOrder) {
	cout << node << " ";
	}
	return 0;
	}

view raw topological_sort_dfs.cpp hosted with ❤ by GitHub