[알고리즘] 위상 정렬 (Topological Sorting)

위상 정렬 (Topological Sorting)

• 사이클이 없는 유향 그래프의 모든 정점을 정렬하는 알고리즘
• 간선 (i, j) 가 존재하면 정점 i는 반드시 정점 j보다 앞에 위치해야한다. → 사이클이 있으면 이 성질을 만족할 수 없다.
• 시간 복잡도 : O(V+E)

 

알고리즘

1. 각 노드마다의 진입 간선을 보관하는 배열 in_edge 생성
2. 맨 처음, 진입 간선이 없는 노드들을 queue에 추가
3. queue가 빌 때까지 반복문 실행
   1. 현재 노드 now 출력 
   2. now에 연결된 진출 노드들 탐색
      1. 진출 노드 next의 진입 간선 줄이기
      2. next의 진입 간선이 0이면 next 앞에 있는 노드들이 모두 출력되었다는 의미이므로 next를 queue에 추가

예시 그래프

import java.util.*;

public class Main {

    public static void topologicalSort(ArrayList<ArrayList<Integer>> graph, int in_edge[])
    {
        Queue<Integer> queue = new LinkedList<>();

        //진입 간선이 없는 노드 추가
        for(int i = 0;i < in_edge.length;i++)
        {
            if(in_edge[i] == 0)
                queue.offer(i);
        }

        while (!queue.isEmpty())
        {
            int now = queue.poll();

            //출력
            System.out.println(now);

            for(int next : graph.get(now))
            {
                in_edge[next] --;

                //진입 간선 없는 노드 추가
                if(in_edge[next] <= 0)
                    queue.offer(next);
            }
        }

    }

    public static void main(String[] args) {

        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

        int in_edge[] = new int[5];

        for(int i = 0;i <= 4;i++)
            graph.add(new ArrayList<>());

        graph.get(0).add(1);
        graph.get(0).add(2);
        graph.get(1).add(3);
        graph.get(2).add(3);
        graph.get(2).add(4);

        in_edge[1] = 1;
        in_edge[2] = 1;
        in_edge[3] = 2;
        in_edge[4] = 1;

        topologicalSort(graph, in_edge);

        /*
            결과 :
            0
            1
            2
            3
            4
         */
    }



}

 1과 2는 어느 것이 먼저 출력되어도 상관 없음