위상 정렬(Topological Sort) - 자바(JAVA)

위상 정렬(Topological Sort) - 자바(JAVA)

위상 정렬에 대해 알아보자.

여러 방법이 있지만,
여기서는 DFS와 Stack를 이용해서 구현해보겠다.

위상 정렬(Topological Sort) 란?

• 선행 조건들을 만족하는 일의 수행 순서.

• 특정 노드를 방문하려면, 조건으로 갖는 다른 노드들이 방문된 상태여야 함.

• 조건을 지키면서 노드 방문 순서를 짜는 것을 위상 정렬이라고 한다.

위상 정렬의 예

• 선수 과목
  (1) 과목 2의 선수 과목은 과목 1이다.
  (2) 과목 4의 선수 과목은 과목 1, 2, 3이다.
  (3) 과목 5의 선수 과목은 과목 3이다.
  (4) 과목 6의 선수 과목은 과목 2, 4, 5이다.
  (5) 과목 7의 선수 과목은 과목 5, 6이다.

  그림으로 그려보자.
  
  위와 같은 그림을 얻게 된다.

위상 정렬 과정

1. 진입 간선이 없는 노드 (3번) 부터 시작한다.
2. 진입 조건이 채워진 5를 방문한다.
3. 5에서는 갈 수 있는 노드가 없으므로, 1을 방문한다.
4. 4보다 2를 먼저 방문해야 하므로, 2를 방문한다.
5. 4를 방문한다.
6. 6을 방문한다.
7. 7을 방문한다.

• 이렇게 되면, 위상정렬 결과는,
  3 - 5 - 1 - 2 - 4 - 6 - 7 이 된다.

위상 정렬 구현 과정

1. 그래프를 구성한다. 단, 방향이 있는 간선이므로, 나가는 간선은 기록하되 들어오는 간선은 기록하지 않는다
   (예를 들어, 1에는 2로 가는 길을 저장하지만, 2에서 1로가는 길은 저장하지 않는다.)
2. 진입 간선이 없는 노드를 노드(S) 로 연결한다.
3. 노드(S)에서부터 DFS를 시작한다.
4. 방문할 수 있는 인접 노드가 없다면, 현재 노드를 stack에 저장한다.
5. DFS가 종료되면, stack에 들어있는 노드를 하나씩 꺼내서, 값을 출력한다.
6. 출력한 값이 위상 정렬의 결과가 된다.

코드

import java.util.*;

class Main {

    public static void main(String[] args) {

        Node[] node = new Node[8];
        for(int i=0; i<node.length; i++)
            node[i] = new Node(i);

        node[0].addNeighbours(node[1]);
        node[0].addNeighbours(node[3]);

        node[1].addNeighbours(node[2]);
        node[1].addNeighbours(node[4]);
        node[2].addNeighbours(node[4]);
        node[2].addNeighbours(node[6]);
        node[3].addNeighbours(node[4]);
        node[3].addNeighbours(node[5]);
        node[4].addNeighbours(node[6]);
        node[5].addNeighbours(node[6]);
        node[5].addNeighbours(node[7]);
        node[6].addNeighbours(node[7]);

        System.out.println("위상 정렬 순서");

        node[0].visited = true;

        topoSort(node[0]);

        while(!stack.empty())
            System.out.println(stack.pop()+" ");

    }

    static Stack<Node> stack = new Stack<>();

    static void topoSort(Node v) {
        List<Node> neighbours = v.getNeighbours();

        for(Node w : neighbours){
            if(!w.visited){
                w.visited=true;
                topoSort(w);
            }
        }
        stack.push(v);
    }

}



class Node {
    int info;
    boolean visited;
    List<Node> neighbours; //인접 목록

    Node(int info){ //생성자
        this.info = info;
        this.visited = false;
        this.neighbours = new ArrayList<>();
    }

    public void addNeighbours(Node neighbourNode) { //인접 목록 채우기
        this.neighbours.add(neighbourNode);
    }

    public List<Node> getNeighbours(){ //인접 목록 반환
        return neighbours;
    }

    public void setNeighbours(List<Node> neighbours) { // 인접 목록 세팅
        this.neighbours = neighbours;
    }

    @Override
    public String toString() { //출력 오버라이딩
        return "" + info;
    }
}

고찰

• DFS와 Stack으로 구현되는게 좀 이해가 안됐는데,
  진출 간선이 없는 노드부터 하나씩 빼서 stack에 저장한다고 생각하면 된다.

• 이렇게 생각하면 Queue로 구현하는 것의 역순으로 알고리즘이 진행된다는 것을 알 수 있다.

참고서적

• 자바로 쉽게 배우는 알고리즘 (이충기)