위상정렬

Topology Sort 위상정렬

- 개념 : 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘.

     방향성을 거스르지 않는다.

     여러 경로가 존재할 수 있기에, 답은 다양하게 나올 수 있다.

- 위상 정렬은 DAG(Directed Acyclic Graph, 사이클이 없는 방향그래프)에서만 사용이 가능하다.

- 시간복잡도 : O(V+E), V 정점 개수 E 간선 개수

- 구현방법 

  1. 스택 (DFS 방법)

① 임의의 정점에서 시작한다.

② 시작한 정점과 연결된 정점들을 모두 방문한다.

③ 방문한 정점에서 더이상 탐색할 정점이 없으면 스택에 push해준다.

모든 정점을 방문할 때까지 위의 과정은 반복한다.(만약 더이상 탐색할 정점이 없는데 모든 정점을 방문하지 않았다면 DAG가 아닌 것)

최종적으로 스택에 있는 모든 값들을 pop하며 출력한다.

  2. 큐

① 진입차수(한 정점에서 자신에게 들어오는 방향인 간선의 수)가 0인 정점을 큐에 삽입한다.

② 큐에서 원소를 pop 해서 출력하고, 그 원소와 연결된 모든 간선을 제거한다.

③ 간선 제거 후에 진입차수가 0이 된 정점을 큐에 삽입한다.

큐가 빌 때까지 위의 과정을 반복한다.(만약, 모든 정점 방문 전에 큐가 빈다면 DAG가 아닌 것)

- 관련문제

[백준] 2252 줄 세우기

위상정렬을 이용해서 풀면 되며, 구현방법은 큐를 이용.

코드)

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
int n, m;
vector <int> adj[32002];
int indegree[32002];
 
int main() {
    scanf("%d %d", &n, &m);
    
    int a, b;
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        indegree[b]++;
    }
    
    queue <int> qu;
    for (int i = 1; i <= n; i++) {//진입차수가 0인 정점 삽입
        if (indegree[i] == 0) qu.push(i);
    }
 
    for (int i = 1; i <= n; i++) {//위상정렬이 정확히 발생하려면 N개의 정점 방문
        //만약 N개 정점을 방문하기 전에 queue 가 비면 사이클이 발생했다는 뜻
        /*
        if(qu.empty()){
            printf("사이클 발생");
            break;
        }
        */
        int here = qu.front();
        qu.pop();
        printf("%d ", here);
        for (int i = 0; i < adj[here].size(); i++) {
            int next = adj[here][i];
            indegree[next]--;//간선제거
            if (indegree[next] == 0) {
                qu.push(next);
            }
        }
    
    }
    
    return 0;
 
}