위상 정렬

출처: www.youtube.com/watch?v=aOhhNFTIeFI&t=1307s

---

<위상 정렬>

- 사이클이 없는 방향 그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것

(*사이클이 있으면 모든 노드의 진입 차수가 1이상이 됨 -> 위상정렬 수행 불가)

[진입 차수와 진출 차수]

- 진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수

- 진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수

 

[위상 정렬 알고리즘]

- 큐를 이용(dfs를 이용해서도 가능)

1. 진입차수가 0인 모든 노드를 큐에 넣는다.

2. 큐가 빌 때까지 다음의 과정을 반복한다.

    1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.

    2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

 

-> 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다.

[위상 정렬의 특징]

- DAG에 대해서만 수행 가능

- 여러 가지 답이 존재할 수 있다

    : 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우

- 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단

- 스택을 활용한 DFS를 이용해 위상 정렬을 수행할 수도

 

from collections import deque

v,e = map(int , input().split()) #노드의 개수, 간선
indegree = [0] * (v+1) #진입차수 초기화

graph = [[] for i in range(v+1)] # 간선정보 초기화

#간선 정보 입력 받기
for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b) # a에서 b로 이동
    indegree[b] +=1 # 진입차수 증가

#위상정렬 함수
def topology_sort():
    result = [] #수행 결과
    q = deque() #큐
    #처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
    for i in range( 1, v+1):
        if indegree[i] == 0:
            q.append(i)
    #큐가 빌때까지 반복
    while q:
        #큐에서 원소 꺼내기
        now = q.popleft()
        result.append(now)
        #해당 원소와 연결된 노드들의 진입차수에서 1 빼기
        for i in graph[now]:
            indegree[i] -=1
            #새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if indegree[i] == 0:
                q.append(i)
    #위상 정렬 수행 결과 출력
    for i in result:
        print(i, end = ' ')

topology_sort()

int v, e; //노드 개수, 간선 개수
int indegree[100001]; 진입차수
vector<int> graph[100001]; //간선정보 연결 리스트

void topologySort(){
    vector<int> result;
    queue<int> q;
    
    for(int i= 1; i <= v; i++){
        if( indegree[i] == 0)
            q.push(i);
    }
    
    while(!q.empty()){
        int now = q.front();
        q.pop();
        result.push_back(now);
        for(int i= 0 ; i < graph[now].size(); i++){
            //해당 원소와 연결된 노드들의 진입차수에서 1 빼기
            indegree[graph[now][i]] -=1;
            //새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if(indegree[graph[now][i]] == 0){
                q.push(graph[now][i]);
            }
        }
    }
    
    for(int i=0 ; i< result.size(); i++){
        cout << result[i] <<" " ;
    }
}
    

[위상 정렬 알고리즘 성능 분석]

- 위상 정렬을 위해 차례대로 모든 노드를 확인하며 각 노드에서 나가는 간선을 차례대로 제거해야 함

    : 위상 정렬 알고리즘의 시간 복잡도는 O(V+E)