[알고리즘] 위상 정렬 (Topological sort) 동작 과정, 예제

위상 정렬(Topological Sorting)

정의

방향 그래프에서 각 정점들이 어떤 순서로 방문되어야 하는지를 결정하는 알고리즘.
그래프에서 어떤 정점이 다른 정점에 의존하는 관계가 있을 때, 그래프를 순서대로 방문하기 위해 위상 정렬을 사용할 수 있다.

위상 정렬은 다양한 분야에서 사용된다. 예를 들어, 컴파일러에서는 소스 코드의 의존성을 파악하기 위해 위상 정렬을 사용한다. 그 외에도 작업 스케줄링, 프로젝트 관리, 그래프 이론 등 다양한 분야에서 유용하게 사용된다.

 

예제

https://www.acmicpc.net/problem/14567

선수과목처럼 어떤 상태에 도달하기 위해 우선적으로 도달해야 할 상태가 있고, 이것을 준수한 채 모든 정점을 방문할 수 있는 순서를 구하는 것이다. 해당 문제에서는 그래프의 깊이만 구하면 된다.

 

Indegree 방식

⬇️ 아래 사이트를 참고하면 천천히 확인할 수 있다. (dfs로 구하는 방법도 있음)

 

Indegree(진입차수) VS Outdegree(진출차수)

• Indegree: 방향 그래프에서 다른 노드에서 기준 노드로 들어오는 엣지의 개수
• Outdegree: 방향 그래프에서 기준 노드에서 다른 노드로 나가는엣지의 개수

위상 정렬에서는 Indegree가 0인 곳에서부터 탐색을 시작하기 때문에 Indegree가 중요하다.

 

동작 과정

1. 그래프를 구성한다.
2. Indegree == 0인 정점을 모두 찾아 스택(또는 큐)에 기록한다.
3. 스택에서 정점을 하나씩 꺼내며, 해당 정점에서 갈 수 있는 모든 정점 Vn에 대해 아래를 수행한다.
   1. Vn의 Indegree를 1 감소
   2. 만약 Vn의 Indegree가 0이 될 경우 스택에 추가
4. 스택이 빌 때까지 3을 반복한다.

 

구현

int[] indegrees = {모든 정점의 indegree 저장}
Stack<Integer> zeroIndegreeVertex;

for(int indegree: indegrees) {
    if(indegree == 0) {
    	// zeroIndegreeVertex에 정점 추가
    }
}

while(zeroIndegreeVertex.size() > 0) {
    // 진입차수가 0인 정점 아무거나 선택
    int vertex = zeroIndegreeVertex.pop();
    // 해당 정점에서 탐색
    for(int v: graph(vertex)) {
        // indegree 차감
        indegrees[v]--;
        // 0이면 스택에 추가
        if(indegrees[v] == 0) {
        	zeroIndegreeVertex.push(v);
    	}
    }
}

 

DFS 방식

후위 순회 (post-order traversal)

나 • 왼쪽 자식 • 오른쪽 자식이 있을 경우, 왼쪽 자식 ➡️ 오른쪽 자식 ➡️ 나 순으로 탐색하는 것을 의미한다. (본인이 제일 마지막에 오므로 POST-order라고 불림)

 

동작 과정

1. 모든 노드를 방문하지 않은 상태로 초기화한다.
2. 각 노드를 반복하며, 방문하지 않은 노드에서 DFS를 시작한다.
3. DFS 탐색 중 인접한 노드를 방문한다.
4. 탐색이 끝난 노드를 스택에 추가한다.
5. 모든 노드를 탐색한 후, 스택을 역순으로 읽어 위상 정렬 순서를 완성한다.

 

구현

// 위상 정렬 메서드
public void dfsTopologicalSort() {
    boolean[] visited = new boolean[V]; // 방문 여부를 확인하는 배열
    Stack<Integer> stack = new Stack<>(); // 위상 정렬 순서를 저장할 스택

    // 모든 노드를 방문하며 DFS 실행
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            dfsTopologicalSortUtil(i, visited, stack);
        }
    }

    // 스택에서 노드를 하나씩 꺼내어 출력 (역순으로 위상 정렬)
    System.out.println("DFS 기반 위상 정렬 결과:");
    while (!stack.isEmpty()) {
        System.out.print(stack.pop() + " ");
    }
}

// DFS를 이용한 위상 정렬을 수행하는 재귀 함수
private void dfsTopologicalSortUtil(int v, boolean[] visited, Stack<Integer> stack) {
    visited[v] = true; // 현재 노드를 방문 처리

    // 현재 노드의 인접한 노드들을 방문
    for (int neighbor : adj[v]) {
        if (!visited[neighbor]) {
            dfsTopologicalSortUtil(neighbor, visited, stack);
        }
    }

    // 모든 인접 노드를 방문한 후, 스택에 현재 노드를 추가
    stack.push(v);
}