[알고리즘] 위상정렬

[알고리즘] 위상정렬

• 위상정렬: 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용 가능한 알고리즘
  • 다시 말하면, 방향 그래프의 모든 노드를 *방향성에 거스르지 않도록 순서대로 나열하는 것

---

• 위상 정렬 동작 과정
  1. 진입차수가 0인 노드를 큐에 넣는다.
  2. 큐가 빌 때까지 다음의 과정을 반복한다.
     1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거
     2. 새롭게 진입차수가 0이 된 노드를 큐에 삽입
• 주의할 점
  • 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단
    • 다시 말해, 원소가 V(노드의 개수)번 추출되기 전에 큐가 비어버리면 사이클이 발생한 것임
  • 위상 정렬의 답안은 여러 가지가 될 수 있다.

---

• 위상 정렬 소스코드

  • 입력 예시

    # 노드 및 간선 개수
    7 8
    # a 노드에서 b로 이동 가능
    1 2
    1 5
    2 3
    2 6
    3 4
    4 7
    5 6
    6 4

  • 소스코드

    from collections import deque
    
    # 노드의 개수와 간선의 개수 입력 받기
    v, e = map(int, input().split())
    # 모든 노드에 대한 진입 차수는 0으로 초기화
    indegree = [0] * (v+1)
    # 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
    graph = [[] for i in range(v+1)]
    
    for _ in range(e):
        a, b = map(int, input().split())
        # 노드 a에서 b로 이동 가능
        graph[a].append(b)
        # 진입차수 1 증가
        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()
```

• 출력

  1 2 5 3 6 4 7