위상 정렬(Topological Sort)

위상 정렬

• 방향이 있는 그래프의 순서 정렬
• 위상 정렬이 가능하려면 DAG(Directed Acycle Graph, 방향성이 있으며 사이클이 없는 그래프)이여야 한다.
• 위상 정렬을 구현하는 방법에는 DFS를 사용하거나 indegree 배열을 사용하여 구현하는 방법이 있다. 본 포스팅에서는 후자를 선택하여 구현하는 방법을 알아볼 것이다.

 

필요한 자료구조 & 변수

변수	설명
List<List<Integer>> graph	그래프 관계 표현을 위한 2차원 인접 리스트
int[] indegree	해당 노드를 가리키는 간선의 갯수를 담기 위한 배열
Queue<Integer> q	indegree 값이 0이 된 노드를 담기 위한 Queue
List<Integer> result	결과를 담기 위한 리스트

 

 

Flow

1. indegree가 0인(=나를 가리키는 노드가 없는) 노드들을 q에 담고 시작

 

2. q에서 Node(1)을 빼고 result에 추가, 그리고 Node(1)이 가리키고 있던 다른 노드의 값 1씩 감소

 

3. q가 빌 때 까지 위 과정 반복

 

소스 코드

 

package algorithm;
 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
 
public class TopologicalSort {
    /*
    algorithm - 위상 정렬
    */
    static int n, m;
    static int[] indegree;
    static List<List<Integer>> graph;
    static List<Integer> result;
 
    public static void main(String[] args) {
        n = 7; // 노드 수
        m = 7; // 간선 수
 
        graph = new ArrayList<>();
        result = new ArrayList<>();
        indegree = new int[n + 1];
 
        // 간선
        int[] n1 = {1, 2, 5, 1, 3, 4, 3};
        int[] n2 = {2, 5, 6, 3, 4, 6, 7};
 
        
        for (int i = 0; i < n + 1; i++) {
            graph.add(new ArrayList<>());
        }
 
        // 그래프 만들기 & indegree 정보 넣기
        for (int i = 0; i < m; i++) {
            graph.get(n1[i]).add(n2[i]);
            indegree[n2[i]]++;
        }
 
        topologicalSort();
 
        // 위상 정렬 결과 출력
        for(int i : result){
            System.out.print(i + " ");
        }
        System.out.println();
    }
 
    private static void topologicalSort() {
        Queue<Integer> q = new LinkedList<>();
 
        for (int i = 1; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                q.offer(i);
            }
        }
 
        while (!q.isEmpty()) {
            int node = q.poll();
            result.add(node);
 
            for(int i : graph.get(node)){
                indegree[i]--;
 
                if(indegree[i] == 0){
                    q.offer(i);
                }
            }
        }
    }
}
 

 

결과

 

4와 7의 순서가 바껴 출력 되었어도 전체적인 그래프의 위상 순서에는 차이가 없다.

 

 

 

 

 

참고자료

bcp0109.tistory.com/21