위상 정렬

위상 정렬

• 유향 그래프의 정점들을 변의 방향을 거스르지 않도록 나열하는 것
• 순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해주는 알고리즘
• 선수과목 구조를 예로 들 수 있음 -> 선후 관계가 정의된 상황
• 유향 그래프의 구조에 따라 여러 종류의 순서가 나올 수 있음
• 그래프 내에서 순환이 존재하면 안됨
• 비순환 유향 그래프에서 사용 가능

구현

1. 진입 차수가 0인 정점(시작 포함)을 큐에 모드 넣는다.
2. 큐에서 진입 차수가 0인 정점을 꺼내어 자신과 인접한 정점의 간선을 제거한다.
   • 인접한 정점의 진입 차수를 1 감소시킨다.
3. 간선 제거 후 진입 차수가 0이 된 정점을 큐에 넣는다.

• 큐가 공백이 될 때까지 2 - 3 작업 반복
  • 모든 노드가 다 처리되었다면 위상 정렬 완성
  • 모든 노드가 처리되지 않았다면 사이클 발생

package algo0828;

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class TopologicalSorting {
    static int V, E; // 정점의 수, 간선의 수
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        for (int t = 1; t <= 10; t++) {
            sb.append("#").append(t).append(" ");
            StringTokenizer st = new StringTokenizer(br.readLine());

            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());
           
            // 각 정점이 가지는 간선의 수 카운트하는 배열 
            // 0은 안쓰는 인덱스 
            int[] edgeCount = new int[V + 1];
            ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
            // 그래프 생성 
            for (int i = 0; i < V + 1; i++) {
                graph.add(new ArrayList<>());
            }
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < E; i++) {
            	// 그래프에 간선의 정보를 입력하면서, 정점별 간선의 수를 체크한다.
                int to = Integer.parseInt(st.nextToken());
                int from = Integer.parseInt(st.nextToken());
                graph.get(to).add(from);
                edgeCount[from]++;
            }
            Queue<Integer> q = new LinkedList<>(); 
            // 진입 차수(오는 간선이 없는 노드) 0인 값 큐에 넣기
            for(int i = 1; i < edgeCount.length; i++) {
                if(edgeCount[i] == 0) {
                    q.offer(i);
                }
            }
            // 진입 차수가 없는 노드부터 시작.
            while(!q.isEmpty()) {
            	
                int nodeNo = q.poll();
                sb.append(nodeNo).append(" ");
                 
                // 꺼낸 노드의 인접한 노드들 찾아서 큐에 넣기 
                List<Integer> list = graph.get(nodeNo);
                for(int i = 0; i < list.size(); i++) {
                	// 큐에 들어간 정점들의 간선의 수를 정산 
                    edgeCount[list.get(i)]--;
                    
                    // 정산 후 진입 차수가 없는 정점이라면 큐에 담는다.
                    if(edgeCount[list.get(i)] == 0) {
                        q.offer(list.get(i));
                    }
                }
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

ref : https://codingnojam.tistory.com/66