Topology sort

1. Problem

- 제시된 그래프를 보고 노드의 순서를 정해보자.

- 위상 정렬은 순서가 있는 작업을 차례대로 수행해야 할 때 그 순서를 결정하기 위해 사용하는 알고리즘이다.

- 위상 정렬에 이용되는 그래프는 싸이클이 없는 방향 있는 그래프(Directed Acyclic Graph, DAG)이다.

 

2. Input

1) int[][] graph

- 그래프의 간선을 표시한 2차원 배열

- graph[i][j]: i번에서 j번으로 연결되어있다는 뜻이다.

 

3. Output

1) 그래프의 노드들이 위상 정렬된 결과를 출력

 

4. Example

// 각 노드들의 연결을 확인한 후, 노드별로 진입차수를 계산한다.
// 진입차수란 노드로 들어오는 간선의 개수를 말한다. indegree=[0, 1, 1, 1, 1, 2, 1]
// 진입차수가 0인 노드를 큐에 넣는다. q=[0]
// 큐에서 노드 하나를 뺀 뒤 그 노드와 연결된 간선을 모두 지운다. indegree=[0, 0, 1, 1, 0, 2, 1], q=[]
  이때 새로 1,4번의 진입차수가 0이 됐다. q=[1,4]
// 큐에서 노드 하나를 뺀 뒤 그 노드와 연결된 간선을 모두 지운다. indegree=[0, 0, 0, 1, 0, 2, 1], q=[4]
  이때 새로 2번의 진입차수가 0이 됐다. q=[4,2]
// 큐에서 노드 하나를 뺀 뒤 그 노드와 연결된 간선을 모두 지운다. indegree=[0, 0, 0, 1, 0, 1, 1], q=[2]
  이때 새로 진입차수가 0이 된 노드는 없다. q=[2]
// 큐에서 노드 하나를 뺀 뒤 그 노드와 연결된 간선을 모두 지운다. indegree=[0, 0, 0, 0, 0, 1, 1], q=[]
  이때 새로 3번의 진입차수가 0이 됐다. q=[3]
// 큐에서 노드 하나를 뺀 뒤 그 노드와 연결된 간선을 모두 지운다. indegree=[0, 0, 0, 0, 0, 0, 1], q=[]
  이때 새로 5번의 진입차수가 0이 됐다. q=[5]
// 큐에서 노드 하나를 뺀 뒤 그 노드와 연결된 간선을 모두 지운다. indegree=[0, 0, 0, 0, 0, 0, 0], q=[]
  이때 새로 6번의 진입차수가 0이 됐다. q=[6]
// 큐에서 노드 하나를 뺀 뒤 그 노드와 연결된 간선을 모두 지운다. indegree=[0, 0, 0, 0, 0, 0, 0], q=[]
// 위상 정렬은 끝났고, 그 결과는 큐에서 뺀 노드의 순서와 같다.
// 0 -> 1-> 4 -> 2 -> 3 -> 5 -> 6

 

5. Code

// 클래스 변수
static int vertex = 7; // 주어진 그래프의 정점의 개수
static int[] indegree = new int[vertex]; // 진입차수

// main()
int[][] graph = {{0,1},{1,2},{2,3},{3,5},{0,4},{4,5},{5,6}}; // 간선의 정보
for(int i=0 ; i<graph.length ; i++)
    indegree[graph[i][1]]++; // 간선이 향하는 방향의 노드의 진입차수 증가
topologySort(graph);

static void topologySort(int[][] graph) {
    int[] result = new int[vertex];
    Queue<Integer> q = new LinkedList<>();
    
    for(int i=0 ; i<vertex ; i++) // 진입차수가 0인 노드를 큐에 넣는다.
        if(indegree[i]==0)
            q.add(i);
    
    for(int i=0 ; i<vertex ; i++) { // 정렬이 완전히 수행되려면 vertex개의 노드를 방문해야한다.
        if(q.isEmpty()) { // vertex개를 방문하기 전에 큐가 비면 사이클이 생긴 것이다.
            System.out.println("사이클 발생");
            return;
        }
        int node = q.remove(); // 큐에서 노드를 꺼낸 후
        result[i] = node;
        for(int j=0 ; j<graph.length ; j++) { // 노드와 연결된 간선을 찾는다.
            if(graph[j][0]==node) {
                int y = graph[j][1];
                if(--indegree[y]==0) // 그 노드의 진입차수를 줄이고, 0이 된다면
                    q.add(y); // 큐에 넣는다.
            }
        }
    }
    
    for(int i : result) // 위상 정렬 결과 확인
        System.out.print(i+","); // 0,1,4,2,3,5,6,
}

- 시간 복잡도는 O(V+E)이다.

- V는 정점(vertex)의 개수, E는 간선(edge)의 개수이다.