다양한 알고리즘 - 위상정렬

안녕하세요. 오늘은 위상 정렬에 대해서 알아보려고 합니다.

 

위상 정렬은 정렬 알고리즘의 일종입니다. 

 

위상 정렬은 일반적으로 작업들 간의 의존 관계를 표현하고, 이를 바탕으로 작업들을 순서대로 실행해야 할 때 사용합니다.

 

이론적으로 설명하자면,

 

방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것입니다.'

 

 

0. 집입차수 계산

 

먼저 우리는 집입차수에 대해서 알고 넘어가야합니다.

 

진입차수란 특정한 노드로 '들어오는' 간선의 개수를 의미합니다.

 

이는, 해당 노드의 선행 작업의 개수를 의미합니다.

 

자세한 진입차수의 대한 개념은 다음 링크로 들어가시면 체크해보실 수 있습니다.

https://sonlife97.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%A7%84%EC%9E%85%EC%B0%A8%EC%88%98%EB%9E%80

[자료구조] 진입차수란?

 

 

 

1. 선행 작업이 없는 노드 선택

 

진입차수가 0인 노드를 찾습니다. 즉, 선행 작업이 없는 노드를 의미합니다.

 

진입차수가 0인 노드를 선택하고, 이를 작업 목록에 추가합니다.

 

선택한 노드와 열결된 간선을 제거합니다. 이는 해당 노드를 완료했음을 의미합니다.

 

 

 

2. 선택한 노드와 연결된 노드들의 진입차수 갱신

 

선택한 노드를 제거한 결과, 그와 연결된 노드들의 진입차수를 1씩 감소시킵니다.

 

그리고진입차수가 0인 노드를 계속해서 선택하고 작업 목록에 추가합니다.

 

 

 

3. 위의 단계를 반복

 

연결된 간선을 제거하고 진입차수를 갱신합니다.

 

더 이상 진입차수가 0인 노드가 없을 때까지 반복합니다.

 

 

 

4. 결과 확인

 

작업 목록에 모든 노드가 추가되었을 때, 위상 정렬이 완료됩니다.

 

작업 목록에 포함된 노드들은 선후 관계를 지키며 순서대로 수행할 수 있는 순서를 나타내게 됩니다.

 

 

 

5. 순환 그래프 확인

 

위상 정렬은 비순환 그래프에서만 가능하므로, 순환 그래프에서 위상 정렬을 시도하면 실패합니다.

 

순환 그래프에서는 모든 노드를 나열하는 것이 불가능합니다.

 

 

예시를 통한 위상 정렬 과정

 

 

선행 작업이 없는 노드 선택 후 진입차수가 0일 노드를 큐에 삽입

 

예시 그래프에선 노드1이 진입차수가 0입니다.

 

선택한 A노드를 출력 리스트(큐)에 추가합니다.

 

노드	1	2	3	4	5	6	7
진입차수	0	1	1	2	1	2	1

 

큐

노드 1

 

 

선택한 노드와 연결된 노드들의 진입차수 갱신

 

먼저 큐에 들어 있는 노드 1를 꺼내서 노드 1와 연결되어 있는 간선들을 제거합니다. 

 

그렇게 하면 새롭게 노드 2과 노드 5가 진입차수가 0 이 됩니다.

 

노드	1	2	3	4	5	6	7
진입차수	0	0	1	2	0	2	1

 

큐	노드 2, 노드 5

 

 

이제 큐에 들어 있는 노드 2를 꺼냅니다. 이제 2과 연결되어 있는 간선들을 제거합니다.

 

간선이 제거되면서 노드 6의 진입차수는 1로 변경됩니다.

 

이제 새롭게 노드 3의 진입차수가 0이 됩니다. 따라서 노드 3를 큐에 삽입합니다.

 

노드	1	2	3	4	5	6	7
진입차수	0	0	0	2	0	1	1

 

큐	노드 5, 노드 3

 

 

이제 큐에 있는 노드 5를 꺼내고 5와 연결된 간선들을 제거합니다.

 

그러면 새롭게 노드 6의 진입차수가 0이 됩니다. 따라서 노드 6를 큐에 삽입합니다.

 

노드	1	2	3	4	5	6	7
진입차수	0	0	0	2	0	0	1

 

큐	노드 3, 노드 6

 

 

이제 큐에 있는 노드 3를 꺼내고 3와 연결된 간선들을 제거합니다.

 

간선이 제거되면서 노드 4의 진입차수는 1로 변경됩니다.

 

큐는 새롭게 진입차수가 0이된 노드가 없으므로 넘어갑니다.

 

 

노드	1	2	3	4	5	6	7
진입차수	0	0	0	1	0	0	1

 

큐

노드 6

 

 

이제 큐에 있는 노드 6를 꺼내고 6와 연결된 간선들을 제거합니다.

 

간선이 제거되면서 노드 4의 진입차수는 0로 변경됩니다.

 

따라서 노드 4를 큐에 삽입합니다.

 

노드	1	2	3	4	5	6	7
진입차수	0	0	0	0	0	0	1

 

큐

노드 4

 

 

이제 큐에 있는 노드 4를 꺼내고 4와 연결된 간선들을 제거합니다.

 

간선이 제거되면서 노드 7의 진입차수는 0로 변경됩니다.

 

따라서 노드 7를 큐에 삽입합니다.

 

노드	1	2	3	4	5	6	7
진입차수	0	0	0	0	0	0	0

 

큐

노드 7

 

 

이제 큐에 있는 노드 7를 꺼내고 마지막 7와 연결된 간선들을 제거합니다.

 

이번에는 새롭게 친입차수가 0이되는 노드가 없으므로 그냥 없어갑니다.

 

노드	1	2	3	4	5	6	7
진입차수	0	0	0	0	0	0	0

 

큐

 

위 과정을 수행하는 동안 큐에서 빠져나간 노드를 순서대로 출력하면, 그것이 바로 위상 정렬을 수행한 결과가 됩니다.

 

 

위상정렬 소스코드

from collections import deque

# 정점(Vertex)과 간선(Edge)의 개수를 입력받습니다.
v, e = map(int, input().split())

# 진입 차수(Indegree)를 0으로 초기화합니다. 정점 번호가 1부터 시작하기 때문에 v+1 크기로 설정합니다.
indegree = [0] * (v+1)

# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트(Adjacency List)를 초기화합니다.
graph = [[] for i in range(v+1)]

# 모든 간선 정보를 입력받아 그래프를 구성하고, 진입 차수를 1 증가시킵니다.
for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)  # 노드 A에서 B로 이동 가능
    indegree[b] += 1  # 진입 차수를 1 증가

# 위상 정렬 함수를 정의합니다.
def topology_sort():
    result = []  # 알고리즘 수행 결과를 담을 리스트
    q = deque()  # 큐 기능을 위한 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()

 

입력 예시

7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4

 

 

출력 예시

1 2 5 3 6 4 7