[알고리즘] Topology Sort (위상정렬)
: 순서가 정해져 있는 작업을 차례로 수행
Directed Acyclic Graph에만 적용이 가능하다!
queue를 이용한 알고리즘
구현 순서
- 진입 차수가 0인 정점을 큐에 삽입한다
- 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다
- 간선을 제거한 후, 진입차수가 0이 된 정점을 큐에 삽입한다
- 큐가 빌 때까지 2~3을 반복한다
- 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것
- 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상정렬의 결과
시간 복잡도: O(V+E)
#include<vector>
#include<queue>
#define Max 10
int n;
int inDegree[Max];
vector<int> a[Max];
void topologySort(){
int result[Max];
queue<int> q;
for(int i=1;i<=n;i++){
if(inDegree[i]==0) //진입차수가 0인 노드 삽입
q.push(i);
}
for(int i=1;i<=n;i++){
if(q.empty()) return; //사이클이 발생한 경우
int x = q.front();
result[i] = x;
for(int j=0;j<a[x].size();j++){
int y = a[x][j];
if(--inDegree[y]==0){ //진입 차수를 제거 후 0이면 큐에 삽입
q.push(y);
}
}
}
}
int main(){
//...
//inDegree에 해당 노드로 들어오는 간선 개수 저장하기
//a에 연결된 노드 저장하기
/**Topology Sort**/
topologySort();
//...
}