[Java] 위상정렬 알고리즘

개요

위상정렬은 의존성이 있는 작업들이 주어질 때 어떤 순서로 수행해야 하는지 계산하는 알고리즘이다.

예를 들어서 A, C 가 끝나야 B를 작업한다고 하자.
이 경우에 탐색 순서를 A->C->B or C->A->B 순으로 해야한다.

위상정렬을 이용할 그래프

위상 정렬의 특징은
그래프 내 사이클이 없는 방향그래프라는 점이다.

위상 정렬을 구현하는 방법은

1. 깊이 우선 탐색의 응용
2. 들어오는 간선이 하나도 없는 정점을 하나씩 찾아서 지우는 방식

2가지가 있다.

구현

1. 깊이 우선 탐색의 응용

import java.util.Vector;

public class 깊이_우선_탐색 {
    // 그래프의 인접 리스트 표현
    static Vector<Vector<Integer>> adj;
    // 각 정점을 방문했는지 여부를 나타낸다.
    static Vector<Boolean> visited;

    // 결과를 뒤집어 주기 위한 스트링 버퍼
    static StringBuffer st = new StringBuffer();

    // 깊이 우선 탐색의 구현
    public static void dfs(int here) {
        System.out.println(here + ": 방문");
        visited.set(here, true);

        for (int i = 0; i < adj.get(here).size(); i++) {
            int there = adj.get(here).get(i);
            // 아직 방문한 적이 없다면 방문한다
            if (!visited.get(there)) {
                dfs(there);
            }
        }

        // dfs()가 종료할 때 마다 현재 정점의 번호를 기록
        st.append(here+" ");
    }

    // 모든 정점을 방문한다
    public static void dfsAll() {
        // visited를 모두 false로 초기화
        for (int i = 0; i < adj.size(); i++) {
            visited.add(false);
        }

        // 모든 정점을 순회하면서, 아직 방문한 적 없으면 방문한다.
        for (int i = 0; i < adj.size(); i++) {
            if (!visited.get(i)) {
                dfs(i);
            }
        }

        // 결과를 뒤집은 값을 출력
        System.out.println(st.reverse().toString());
    }

    public static void main(String[] args) {
        adj = new Vector<>();
        visited = new Vector<>();

        for (int i = 0; i < 10; i++) {
            adj.add(new Vector<>());
        }

        adj.get(0).add(1);

        adj.get(1).add(2);

        adj.get(2).add(3);

        adj.get(3).add(4);

        adj.get(5).add(6);
        adj.get(5).add(7);
        adj.get(5).add(8);

        adj.get(6).add(0);

        adj.get(7).add(1);

        adj.get(8).add(3);

        adj.get(9).add(2);

        dfsAll();
    }
}

결과

0: 방문
1: 방문
2: 방문
3: 방문
4: 방문
5: 방문
6: 방문
7: 방문
8: 방문
9: 방문
 9 5 8 7 6 0 1 2 3 4

그림과 같은 그래프를 삽입한 뒤 깊이우선 탐색을 하는 코드이다.
여기서 중요하게 볼 부분은

        dfs(){
            ...
            // dfs()가 종료할 때 마다 현재 정점의 번호를 기록
            st.append(here+" ");
        }

        ...

        dfsAll(){

            ...

        // 결과를 뒤집은 값을 출력
        System.out.println(st.reverse().toString());
        }

dfs()가 종료할 때마다 현재 정점의 번호를 기록하고
마지막에 이를 뒤집은 결과를 출력한다.

이게 위상정렬의 조건을 만족하는지 살펴보자

시각화된 그래프를 보면 당연하게도 4번노드가 가장 마지막에 탐색되어야 한다.

만약 위 알고리즘이 위상정렬을 만족하지 않는다고 하자.

결과 값이 다음과 같다고 했을 때
v ... ... ... ... u

u->v 로 가는 간선이 있다고 하자
이 경우에는 위상정렬이 제대로 되지 않았다는 의미이다.

이 경우에 dfs(u)가 종료하기 전, visited[v] 가 참인지 거짓인지 살펴보자

1. visited[v] 가 참인경우
   dfs(v)가 한 번 호출 됐어야 한다. (visited[v] 처리를 위해..)
   이 경우에 dfs(v)가 dfs(u)보다 나중에 호출됐어야 한다. (호출 역순으로 출력하므로...)그러나, 이 경우에 u->v로 가는 간선이 있으므로 사이클이 생기므로 사이클이 없는 방향그래프가 아니게 되어 모순이된다.
2. 즉 dfs(v) 가 먼저 호출되고 재귀로 dfs(u)가 호출되어 반환한 뒤 dfs(v)가 반환한다. v->u로 가는 간선이 있다는 의미이다.
3. visited[v] 가 거짓인 경우
   dfs(u)가 dfs(v)를 호출했을 것이다.이는 전제와 다르므로 거짓이다.
4. 그러면 출력되는 결과가 종료되는 역순이므로
   u .. ... v가 되어야 한다.

따라서 모든 경우에 u->v로 가는 간선이 존재할 수 없으므로
해당 알고리즘은 제대로 동작한다는 것을 알 수 있다.

2. 들어오는 간선이 하나도 없는 정점을 하나씩 찾아서 지우는 방식

import java.util.Vector;

public class 위상_정렬_2 {
    // 인접 리스트
    static Vector<Vector<Integer>> adj;
    // 방문 체크
    static boolean[] visited;
    // [노드] = 연결 받는 경로 수
    static int[] matrixInfo;

    public static void topologicalSort() {
        while (true) {

            int nowNode = -1;

            for (int i = 0; i < adj.size(); i++) {
                if (matrixInfo[i] == 0) {
                    matrixInfo[i] = -1;
                    nowNode = i;
                    break;
                }
            }

            // 모두 방문 했다면 종료
            if (nowNode == -1) {
                break;
            }

            System.out.print(nowNode + ">");

            // i 노드 지우기
            for (int j = 0; j < adj.get(nowNode).size(); j++) {
                matrixInfo[adj.get(nowNode).get(j)] -= 1;
            }
        }
    }

    public static void main(String[] args) {
        // matrix = new int[10][10];
        adj = new Vector<>();
        for (int i = 0; i < 10; i++) {
            adj.add(new Vector<>());
        }
        visited = new boolean[10];
        matrixInfo = new int[10];

        adj.get(0).add(1);
        matrixInfo[1] += 1;

        adj.get(1).add(2);
        matrixInfo[2] += 1;

        adj.get(2).add(3);
        matrixInfo[3] += 1;

        adj.get(3).add(4);
        matrixInfo[4] += 1;

        adj.get(5).add(6);
        matrixInfo[6] += 1;
        adj.get(5).add(7);
        matrixInfo[7] += 1;
        adj.get(5).add(8);
        matrixInfo[8] += 1;

        adj.get(6).add(0);
        matrixInfo[0] += 1;

        adj.get(7).add(1);
        matrixInfo[1] += 1;

        adj.get(8).add(3);
        matrixInfo[3] += 1;

        adj.get(9).add(2);
        matrixInfo[2] += 1;

        topologicalSort();
    }
}

결과

5> 6> 0> 7> 1> 8> 9> 2> 3> 4> 

matrixInfo[i]는 i노드에 연결을 받는 경로(노드)의 수를 저장한다.

그림에서 보면
5은 0
3은 2
가 저장되는 형식이다.

여기서 matrixInfo[i] 가 0인 노드를 찾는다고 하자.
단순히 matrixInfo.length 반복하면서 0인 노드를 찾으면 된다.

0인 노드를 찾으면 일단 탐색을 하고
이 노드와 연결된 정보를 지우는 작업을 한다.

adj.get(i) 는 i노드가 연결하는 노드가 저장되어 있다.
그 adj.get(i)의 배열을 탐색(j)하면서 연결 정보를 1개씩 지워준다.

matrixInfo[adj.get(i).get(j)] -=1;

위 작업을 계속 반복 하면서 모든 matrixInfo가 0모다 작아지면
종료한다.

결론

1번 방식, 2번 방식 어떤 방법을 써도 잘 동작한다.

1번 방식, 2번 방식의 출력 결과가 다른데,

그래프에서 5, 9 노드 둘 중 어떤 노드가 먼저 와도 위상 정렬의 조건에 위배되지 않는다.

따라서 1번 방식, 2번 방식 둘 다 맞는 위상정렬 결과이다.

만약 노드를 내림차순, 오름차순으로 정렬해야한다면 2번 방식이 좀 더 쉬울 것이다.

내림차순의 경우
단순히 matrixInfo[i] 가 0인 노드를 matrixInfo.length-1 부터 0까지 거꾸로 탐색하면 되기 때문이다.