Topology Sort 알고리즘

작업들 사이에 선후관계가 존재할 때,
그 선후관계를 유지하면서 전체 작업의 수행 순서를 그래프를 이용해 정렬하는 알고리즘이다.

입력값 1 4는 1번 작업을 먼저 수행한 뒤 4번 작업을 수행해야 한다는 의미

방향 그래프로 1→4가 된다

5→4도 마찬가지 방향 그래프로 표현 가능

즉, 입력으로 주어진 작업 순서 정보들을 이용해 방향 그래프를 구성한다.

예를 들어 4번 작업은 여러 작업으로부터 영향을 받는 노드이며, 연결된 간선이 총 3개이다. (차수는 3)

 

노드로 들어오는 간선의 개수를 진입 차수라고 하며,
토폴로지 정렬에서는 진입 차수가 중요하고, 나가는 간선은 상대적으로 중요하지 않다.

4번 노드의 진입 차수는 2이다.

 

4번 작업으로 들어오는 간선을 가진 작업들이 모두 먼저 끝나야만 4번 작업을 수행할 수 있다.

따라서 입력을 받아 그래프를 구성할 때, 각 작업의 진입 차수를 저장하는 1차원 배열을 함께 만들어 두어야 한다.

진입 차수를 저장할 degree 배열을 0으로 초기화한다.

1 4가 주어지면, 1번 작업에서 4번 작업으로 향하는 방향 간선을 그래프에 추가하고

4번 작업으로 들어오는 간선이 하나 늘어났으므로, degree[4]를 1 증가시킨다.

5 4인 경우에도, 5 → 4 간선을 추가하고 degree[4]를 다시 1 증가

2 5 → degree[5]++

2 3 → degree[3]++

마지막으로 6 2 → degree[2]++

 

이렇게 degree 배열에 각 작업의 진입 차수가 누적되어 저장

입력을 받으면서 그래프와 진입 차수를 함께 만든다.

진입 차수 계산 후 큐를 만든다. (진입 차수가 0인 작업을 관리하기 위한)

진입 차수가 0이라는 것은 선행 작업이 하나도 남아 있지 않다는 의미이므로,
해당 작업은 지금 바로 수행할 수 있다.

현재 3번은 선행해야 할 작업이 2개 있다

마찬가지로 2번의 진입차수는 1, 아직 할 작업이 있어 바로 수행할 수 없다.

먼저 1번부터 6번 작업까지 순회하면서, 진입 차수가 0인 작업들을 모두 큐에 넣는다.

큐에서 하나의 작업을 꺼내고, 여기서는 1번 작업이 선택되므로 이를 출력한다. (1번 작업을 실제로 수행했다는 의미)

 

1번 작업이 완료되었으므로, 1번의 간선을 제거하고, 연결된 노드의 진입 차수를 감소시킨다.

예를 들어 1 → 4 간선이 존재하므로, 4번 작업의 진입 차수를 1 감소시킨다.

degree[4]-- → 2 → 1

다음으로 큐에 들어 있는 작업 중 하나인 6번 작업을 꺼내어 수행한다.

6번에서 나가는 간선을 제거하고, 연결된 노드의 진입 차수를 감소시킨다.

이 과정에서 6 → 2 간선이 제거되므로, 2번 작업의 진입 차수가 1에서 0으로 감소한다.

0이 되는 순간 큐에 추가한다. 

큐에서 2번 작업을 꺼낸다.

2번 작업에서 출발하는 간선인 2 → 5, 2 → 3을 제거한다.

5번, 3번 작업의 진입 차수를 각각 1씩 감소시킨다.

5번 작업의 진입 차수가 0이 되므로, 큐에 5번 작업을 추가한다.

큐에서 5번 작업을 꺼낸다.

5 → 4 제거하고 degree[4] 1 감소, 4가 0 돼서 큐에 삽입

이 과정을 반복한다.

4 → 3 제거, 진입차수 3 1 감소

그 결과 3번 작업의 진입 차수가 0이 되므로 큐에 추가한다.
이후에는 더 이상 진입 차수를 감소시킬 간선이 남아 있지 않다.

마지막으로 3번 작업을 처리하고 나면
큐가 비게 되고, 모든 작업이 처리되면서 토폴로지 정렬이 종료된다.

순서는 1 6 2 5 4 3

 

코드

cin>>n>>m;
vector<vector<int>> graph(n+1,vector<int>(n+1,0)); //그래프 만들기 위한 인접행렬 
vecotr<int> dergree(n+1); //진입차수 계산하기 위한 일의 갯수
queueue<int> Q;

//for문 돌면서 방향 그래프 a->b로만 갈 수 있는 거 체크하고 b라는 진입차수 1 증가 시킨다.  
for(int i=0; i<m; I++){
	cin>>a>>b;
	graph[a][b]=1;
	degree[b]++;
}

//for문 돌면서 진입차수 0인거 큐에 넣는다. 
//진입차수 0이라는거는 선행해야할 작업이 더이상 없다는 것
for(inti=1; i<=n ;i++){
	if(degree[i]==0)Q.push(i);
}

//이제 큐 돌리면 된다. 
while(!Q.empty()){
	int now=Q.front();
	Q.pop();
	cout<<now<<" ";
	//now가 만드는 진입 차수를 그래프 탐색하면서 찾고 감소 시켜준다. rmflrh 0되면 다시 q에 넣어주기 
	for(int i=1; i<=n; I++){
		if graph[now][i]==1){
			degree[i]--;
			if(degree[i]==0) Q.push(i);
		}
	}
}

return 0

 

 

출처: it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++)