CHAPTER 6 -번외 정렬 - 위상 정렬(Topology Sort) - Python(파이썬)

참고 자료 : https://m.blog.naver.com/ndb796/221236874984

 

위상 정렬

: 순서가 정해져 있는 작업을 수행해야 할 때 그 순서를 정해주기 위해서 사용하는 알고리즘

ex ]

0번 -> 1번 ->3번 -> 5번 순으로 이어진 후에  4번이 나오기 전에 2번 만족

이런식으로 그래프의 흐름이 있고 다양한 조건들이 얽혀있을 때 일렬로 그래프의 순서를 나열할 수 있어야함

ex]  0 -> 1 -> 3 -> 5 -> 2 -> 4 -> 6 

 

1. 위상 정렬의 특징

- 여러개의 답이 존재 할 수 있다 

- DAG(Directed Acyclic Graph)에만 존재(방향그래프이지만 사이클이 존재하지 않는 그래프)

  -> 사이클이 발생하는 경우 위상 정렬을 수행할 수 없다. Why? 위상 정렬은 시작점이 존재해야만 사용할 수 있는 알고리즘

- 위상 정렬 문제 : ① 현재 그래프는 위상 정렬이 가능한지 ② 위상 정렬이 가능하다면 그 결과는 무엇인지

2. 큐를 이용한 위상 정렬 수행

   ① 진입차수가 0인 정점을 큐에 삽입 ( 진입차수 : 노드로 들어오는 다른 노드의 개수 ) 

   ② 큐에서 원소를 꺼내 연결된 모든 간선 제거

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

   ④ 큐가 빌 때까지 2번 - 3번 과정을 반복. (모든 원소를 방문하기 전에 큐가 제거될 경우 사이클이 존재)

   ⑤ 큐에서 꺼낸 순서가 위상 정렬의 결과

정점	0	1	2	3	4	5	6
진입차수	0	1	1	1	2	1	1

이므로 진입차수가 0인 0부터 큐에 삽입

1. 진입차수가 0인 0부터 큐에 삽입

2. 큐에서 0을 꺼내 연결된 간선 제거 ( 꺼낸 수 : 0 )

정점	0	1	2	3	4	5	6
진입차수	0	1-1 = 0	1-1 = 0	1	2	1	1

3. 진입차수 표(2번,3번) 변경

4.진입차수가 0인 1,2 큐에 삽입

5. 큐에서 꺼낸 1을 꺼낸 후 간선을 제거(꺼낸 수: 0 -> 1 )

 

정점	0	1	2	3	4	5	6
진입차수	0	0	0	1-1=0	2	1	1

6. 진입차수표(3번) 변경

7. 진입차수가 0인 3이 큐에 삽입

8. 큐에서 2를 꺼낸 후에 간선을 제거(꺼낸 수 : 0 -> 1 -> 2 )

정점	0	1	2	3	4	5	6
진입차수	0	0	0	0	2-1 = 1	1	1

9. 진입차수표 (4번) 변경

 

10. 큐에는 이제 3만이 남아 있음

 

11. 큐에서 3을 꺼내서 간선 제거(꺼낸 수: 0 -> 1- > 2 -> 3)

정점	0	1	2	3	4	5	6
진입차수	0	0	0	0	1	1-1=0	1

12. 진입차수표 (5번) 변경

13. 진입차수가 0인 5를 큐에 삽입

14. 큐에서 5를 꺼내서 간선 제거(꺼낸 수 : 0 -> 1-> 2-> 3 -> 5)

 

정점	0	1	2	3	4	5	6
진입차수	0	0	0	0	1-1=0	0	1

15. 진입차수표 (4번) 변경

16.진입차수표가 0인 4를 큐에 삽입

17. 큐에서 4를 꺼내서 간선 제거( 꺼낸수: 0 -> 1-> 2-> 3-> 5-> 4 )

 

정점	0	1	2	3	4	5	6
진입차수	0	0	0	0	0	0	1-1=0

19. 진입차수표 (6번) 변경

20. 진입차수표가 0인 6를 큐에 삽입

21. 큐에서 6을 꺼내서 간선을 제거해야하지만 없으므로 끝 (꺼낸 수 : 0 -> 1-> 2-> 3-> 5-> 4 ->6)

---

참고 자료 : https://freedeveloper.tistory.com/390

입력 예시  7 7 ( 노드의 수 | 간선의 개수 ) 1 2 ( 1-> 2 ) 1 3 ( 1 ->3 ) 2 4 ( 2 ->4 ) 3 5 ( 3 ->5 ) 4 6 ( 4 ->6 ) 5 7 ( 5 ->7 ) 6 5 ( 6 ->5 )

출력 예시 1 2 3 4 6 5 7

💻 Python(파이썬)

import sys
from collections import deque

#노드의 개수, 간선의 개수 입력 받기
v,e = map(int,sys.stdin.readline().split())
#진입차수표( 노드의 수 +1 )
table = [0]*(v+1)
#노드 연결 정보 리스트( 노드의 수 +1 )
graph = [[] for _ in range(v+1)]

#간선 개수만큼 간선 정보를 입력 받기
for _ in range(e):
    a,b = map(int, sys.stdin.readline().split())
    graph[a].append(b)#A -> B
    table[b]+=1 #진입차수표도 하나씩 증가

#위상 정렬 함수
def toplogy_sort():
    #큐 구현
    q = deque()

    #처음 시작 시 진입차수가 0인 노드를 큐에 삽입
    for i in range(1,v+1):
        if table[i]==0:
            q.append(i)

    #큐가 빌때까지 수행
    while q:
        #제일 왼쪽에 있는 큐를 pop
        now = q.popleft()
        #now와 연결된 그래프
        for i in graph[now]:
            table[i]-=1#1씩 제거
            #진입차수가 0인 값은 큐에 다시 삽입
            if table[i]==0:
                q.append(i)
        #now 값 print
        print(now,end=" ")

toplogy_sort()

💻 Java(자바)

import java.util.*;

public class Main {
    // 노드의 개수(V)와 간선의 개수(E)
    public static int v, e;
    // 모든 노드에 대한 진입차수는 0으로 초기화
    public static int[] table;
    // 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    // 위상 정렬 함수
    public static void topologySort() {
        Queue<Integer> q = new LinkedList<>(); // 큐 라이브러리 사용

        // 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
        for (int i = 1; i <= v; i++) {
            if (table[i] == 0) {
                q.offer(i);
            }
        }

        // 큐가 빌 때까지 반복
        while (!q.isEmpty()) {
            // 큐에서 원소 꺼내기
            int now = q.poll();
            // 해당 원소와 연결된 노드들
            for (int i = 0; i < graph.get(now).size(); i++) {
                //진입차수 1씩 제거
                table[graph.get(now).get(i)] -= 1;
                // 진입차수가 0인 값은 큐에 삽입
                if (table[graph.get(now).get(i)] == 0) {
                    q.offer(graph.get(now).get(i));
                }
            }
            System.out.print(now+" ");
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        v = sc.nextInt();
        e = sc.nextInt();

        // 그래프 초기화
        for (int i = 0; i <= v; i++) {
            graph.add(new ArrayList<Integer>());
        }

        table = new int[v+1];

        // 방향 그래프의 모든 간선 정보를 입력 받기
        for (int i = 0; i < e; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b); // 정점 A에서 B로 이동 가능
            // 진입 차수를 1 증가
            table[b] += 1;
        }

        topologySort();
    }
}