위상 정렬 : Topological Sorting

위상 정렬 : Topological Sorting

위상 정렬은 선후 관계가 정의된 DAG(Directed Acyclic Graph, 유향 비순환 그래프)에서 꼭지점들을 선후 관계를 거스리지 않도록 나열하는 정렬이다. (대표적인 예로 선수과목 구조가 있다.)

위상 정렬은 그래프의 구조에 따라 아래와 같이 여러 개의 종류가 나올 수 있다.
( 1 - 7 - 3 - 4 - 5 - 2 | 1 - 4 - 7 - 5 - 2 - 3 | ... )

* 위상 정렬이 성립하기 위해서는 반드시 그래프에 순환이 존재하지 않아야 한다.

위상 정렬의 과정

1. 자기 자신을 가리키는 변이 없는 꼭짓점을 찾는다.
2. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제한다.
3. 아직 출력되지 않은 꼭짓점이 있으면 위 과정을 반복한다.

코드 예시

public class 위상정렬 {
 
    public static void bfs(int x, int[] count, List<Integer>[] edge) {        
        System.out.print(x+" ");
        Queue<Integer> q = new ArrayDeque<Integer>();
        q.add(x);
        count[x]--;
        while(!q.isEmpty()) {
            int cur = q.poll();
            for(int i=0; i<edge[cur].size(); i++) {
                int next = edge[cur].get(i);
                count[next]--;
                if(count[next]==0) {
                    count[next]--;
                    System.out.print(next+" ");
                    q.add(next);
                }
            }
        }
    }
 
    // N = 정점의 개수, M = 간선의 개수
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] count = new int[N+1];
        List<Integer>[] edge = new List[N+1];
        for(int i=1; i<=N; i++) edge[i] = new ArrayList<>();
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            count[e]++;
            edge[s].add(e);
        }
        for(int i=1; i<=N; i++) {
            if(count[i]==0) {
                bfs(i, count, edge);
            }
        }
    }
}

관련 문제

developmentspace.tistory.com/96

[백준] 1766번 : 문제집