[ 개념 ] 31. Graph - 위상정렬(Topological Sort) 알고리즘

> 위상정렬(Topological Sort)

어떤 일을 하는 순서를 찾는 알고리즘

=> 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

위상정렬의 특징

• 하나의 방향 그래프에는 여러 위상 정렬이 가능하다.
• 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서(Toplogical Order)라 한다.
• 위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리즘은 중단되고 이러한 그래프로 표현된 문제는 실행이 불가능한 문제가 된다.

=> 위상정렬이 가능하려면 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프)여야 한다.

1. 말 그대로 두 노드 A, B 사이에 A->B 같은 관계가 성립되어야 하며
2. A->B, B<-A 처럼 그래프들 사이에 사이클이 없어야 한다.

=> 위상정렬은 DFS를 사용하여 구현하거나 indegree배열을 사용하여 구현할 수 있다.(indegree가 가장 많이 쓰이고 간단하다)

• List<List<Integer>> array : 그래프의 관계를 표현하기 위한 2차원 인접 리스트
• int[] indegree : 해당 노드를 가리키는 간선 갯수를 담기 위한 배열
• Queue<Integer> q : indegree 값이 0이 된 노드들을 담기 위한 Queue
• Queue<Integer> result : Queue에서 꺼내져 결과로 출력하기 위해 담는 결과 Queue

위상정렬의 동작방식

1. 진입차수가 0인 정점(즉, 들어오는 간선의 수가 0)을 선택
   • 진입차수가 0인 정점이 여러개 존재할 경우 어느 정점을 선택해도 무방하다.
   • 초기에 간선의 수가 0인 모든 정점을 큐에 삽입
2. 선택된 정점과 여기에 부속된 모든 간선을 삭제
   • 선택된 정점을 큐에서 삭제
   • 선택된 정점에 부속된 모든 간선에 대해 간선의 수를 감소
3. 위의 과정을 반복해서 모든 정점이 선택, 삭제되면 알고리즘 종료

• 위상 정렬은 정해진 결과 값이 없다. 중요한 점은 화살표가 가리키는 순서는 꼭 지켜져야 한다는 것!

1 - 2 - 5 - 4 - 6
1 - 2 - 4 - 6
1 - 3 - 4 - 6
1 - 3 - 7

이 순서는 어떤 정렬 결과가 나오더라도 변하지 않을 것이다.

코드

import java.util.*;
public class TopologicalSort{
    static int n;
    static int e;

    public static void main(String[] args){
        n = 7;    // 정점 갯수
        e = 9;    // 간선 갯수
        int[] indegree = new int[n+1];
        List<List<Integer>> array = new ArrayList<List<Integer>>();

        for(int i=0; i<n+1; i++){
            array.add(new ArrayList<Intger>());
        }

        // 간선목록 v1 -> v2
        int[] v1 = {1, 1, 2, 4, 3, 3, 5, 2, 5};
        int[] v2 = {2, 3, 5, 6, 4, 7, 6, 4, 4};

        /*
        1. v1 -> v2 인접리스트 생성
        2. v2를 가리키는 노드 갯수 indegree 증가
        */
        for(int i=0; i<e; i++){
            int c1 = v1[i];
            int c2 = v2[i];

            array.get(c1).add(c2);
            indegree[c2]++;
        }
        topologicalSort(indegree, array);
    }

    public static void topologicalSort(int[] indegree, List<List<Integer>> graph){
        Queue<Integer> q = new LinkedList<Integer>();
        Queue<Integer> result = new LinkedList<Integer>();

        // 큐에 indegree가 0인 노드 담기
        for(int i=1; i<n; i++){
            if(indegree[i]==0){
                q.offer(i);
            }
        }

        /*
        1. 큐에서 값을 꺼내며 해당 노드가 가리키는 노드의 indegree를 1 감소
        2. 만약 indegree가 0이 된다면 큐에 넣기
        3. 큐가 빌때까지 반복
        */
        while(!q.isEmpty()){
            int node = q.poll();
            result.offer(node);
            for(Integer i : graph.get(node)){
                indegree[i]--;

                if(indegree[i] == 0){
                    q.offer(i);
                }
            }
        }
        System.out.println(result);
    }
}

위상정렬과 관련된 예시

1. 각각의 작업이 완료되어야만 끝나는 프로젝트

2. 선수 과목

   • 큐를 이용한 위상정렬

     줄 세우기 - 백준 2252번

   • 우선순위 큐를 이용한 위상정렬

     문제집 - 백준 1766번

   • 여러 위상순서 중 가장 짧게 걸리는 위상 정렬 방법 구하기

     작업 - 백준 2056번

     게임개발 - 백준 1516번

참고

https://bcp0109.tistory.com/entry/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC-Topological-Sort-Java?category=848939

https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html