[JAVA]위상정렬 알고리즘

[바킹독의 실전 알고리즘] 0x1A강 - 위상 정렬을 정리 했습니다.

위상정렬 설명

A에서 C로 가는 간선이 있으니 위상 정렬을 했을 때 A는 C보다 앞에 등장해야 해요.

 

올바른 위상 정렬 결과 예시) ABCDEF, ACEDBF, BADCEF, BADFCD 

잘못된 위상 정렬 예시)

1. BFACED는 F가 D보다 먼저 나오기 때문에 X

2. 그래프 안에 사이클이 존재한다면 X -> 선후관계 모순 발생

 

 

위상정렬 구현

 

제일 앞에 오기 위해서는 자신에게 들어오는 간선이 없어야 한다. = indegree 0인 것

A, G, C가 후보군

첫번째 정점은 A

 

계속 이어가서 A는 B로 가는 간선만 있습니다다. 제약조건이 A는 B보다 먼저 와야하는데 자연스럽게 지켜집니다.

A를 위상정렬을 추가한 이후로는 A에서 다른 정점으로 나가는 간선이 의미가 없다는 뜻이에요.

주어진 그래프에서 정점 A와 A에서 뻗어나가는 간선을 모두 지웁니다.

 

정점 A가 제거된 후 B, C, D, E, F, G로 이루어진 그래프에서 제일 앞에 위치할 수 있는 간선은 C, G입니다.  

어느 것을 선택해도 상관없지만 C를  택하겠습니다. 

정점 C와 C에서 뻗어나가는 간선을 모두 지웁니다.

자신에게 들어는 간선이 없는 정점은 D, G입니다.  어느 것을 택해도 상관없지만 임의로 D를 택하겠습다.

 

정점 D와 D에서 뻗어나가는 간선을 모두 지웁니다.

자신에게 들어는 간선이 없는 정점은 B, G입니다.  어느 것을 택해도 상관없지만 임의로 G를 택하겠습다.

 

정점 G와 G에서 뻗어나가는 간선을 모두 지웁니다.

자신에게 들어는 간선이 없는 정점은 B, E입니다. 어느 것을 택해도 상관없지만 임의로 E를 택하겠습다.

 

정점 E와 E에서 뻗어나가는 간선을 모두 지웁니다.

자신에게 들어는 간선이 없는 정점은 B, F입니다. 어느 것을 택해도 상관없지만 임의로 B를 택하겠습다.

 

정점 B와 B에서 뻗어나가는 간선을 모두 지우고 남은 건 F 입니다.

 

과정

1. 맨 처음 모든 간선을 읽으며 indegree 테이블을 채움

2. indegree가 0인 정점들을 모두 큐에 넣음

3. 큐에서 정점을 꺼내어 위상 정렬 결과에 추가

4. 해당 정점으로부터 연결된 모든 정점의 indegree 값을 1 감소시킴 이 때 indegree가 0이 되었다면 그 정점을 큐에 추가

5. 큐이 빌 때까지 3, 4번 과정을 반복

 

 

BFS, DFS처럼 visited 방문 체크는 할 필요가 없다. 

0이면 큐에 넣는다. 

 

A로부터 연결된 정점 B의 Indegree가 1 감소해요. 

큐의 front에 있는 C를 가져와 위상정렬 결과에 추가합니다. C로 부터 연결된 정점 B, D의 Indegree가 1로 감소해요.

정점 D가 0이 되었기 때문에 큐에 추가합니다. 

 

큐의 front에 있는 G를 가져와 위상정렬 결과에 추가합니다. G로 부터 연결된 정점 E의 Indegree가 1로 감소해요.

큐의 front에 있는 D를 가져와 위상정렬 결과에 추가합니다. D로 부터 연결된 정점 E의 Indegree가 1로 감소해요.

정점 B, E가 0이 되었기 때문에 큐에 추가합니다.  

 

큐의 front에 있는 B를 가져와 위상정렬 결과에 추가합니다. B로 부터 연결된 정점은 없다. 

 

큐의 front에 있는 E를 가져와 위상정렬 결과에 추가합니다. E로 부터 연결된 정점 F의 Indegree가 1로 감소해요.

정점 F가 0이 되었기 때문에 큐에 추가합니다.  

 

큐의 front에 있는 F를 가져와 위상정렬 결과에 추가합니다. F 로 부터 연결된 정점은 없다. 

큐가 비어서 위상정렬 결과 끝!

 

백준 2252번 줄세우기(JAVA)

import java.util.*;
import java.io.*;

class Main {
    static int n, m;
    static List<Integer>[] graph;
    static int[] indegree;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new ArrayList[n + 1];
        indegree = new int[n + 1];  
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph[a].add(b);
            indegree[b]++;
        }
        System.out.println(topologicalSort());
    }
    static String topologicalSort() {
        StringBuilder sb = new StringBuilder();
        Queue<Integer> que = new LinkedList<>();


        for(int i = 1; i <= n; i++) { //차수가 0인 노드 큐에 넣기
            if (indegree[i] == 0) {
                que.add(i);
            }
        }
        
         while(!que.isEmpty()) {
             int current = que.poll();
             sb.append(current).append(' ');

             for(int next : graph[current]) {
                 indegree[next]--;
                 if (indegree[next] == 0) {
                      que.add(next);
                }
             }
         }
        return sb.toString();
    }
}