[그래프] 위상정렬

위상정렬 (Topological sort)

 

방향 그래프에서 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 정렬

 

그래프 안에서 사이클이 존재하는 경우엔, 위상정렬을 적용할 수 없다.

 

근데, 사이클이 존재한다는 뜻이 무슨 뜻일까?

 

 

위와 같은 그래프가 존재한다고 가정할 떄, A->B->C->A... 이런식으로 다시 돌아올 때를 사이클이 존재한다고 한다.

 

즉, 한 노드에서 다른 노드들을 거쳐 처음 노드로 돌아오는 경우, 사이클이 존재한다고 얘기할 수 있다.

 

 

위상정렬

위와 같은 그래프가 주어졌을 때, 어떤 노드를 먼저 우선적으로 방문해야 할까?

 

우선적으로, indegree 배열을 만들어서 각 노드의 indegree 개수를 확인해보자.

 

A	B	C	D	E	F	G
0	3	0	1	2	1	0

 

indegree가 0인 정점을 살펴보면 A,C,G 노드가 해당한다. 

 

큐를 선언해서 A를 먼저 넣고, 정점 A를 제거했을 때 indegree가 0인것은 C,G인데 이중에서 C를 먼저 선택하면 정점 C가 삭제되고, 또 이 때 indegree가 0인것을 살펴보면 D와 G가 된다.

 

이 때, D의 Indegree가 0이 되는 것은 정점 C를 삭제하며 간선이 사라졌기 때문이다.

 

이런식으로 결과를 출력한다면,

A C D G E B F

 

이런식으로 순서가 정해지게 된다.

 

이 과정을 코드로 나타내면,

 

A B 이런식으로 입력값이 주어진다면 A <- B 이런식으로 관계가 성립한다고 가정하자.

순서

1. 그래프를 입력받을 때 idg 배열의 count를 1 증가시켜준다. (이 때, 두번째로 받는 입력값의 count를 증가시켜줘야 함. 문제 요구 사항에 따라 확인)
2. 큐를 선언하여 idg 값이 0인 정점들을 큐에 담아준다.
3. 큐를 순회하며, 현재 보고있는 노드를 제거해주고, 근처 노드의 idg 값을 1 빼준다.
4. 이 떄, 근처 노드의 idg 값이 0이라면, 큐에 다시 넣어준다.

 

1.

for(int i = 0; i < m; i++) {
    st = new StringTokenizer(br.readLine());
    int u = Integer.parseInt(st.nextToken());
    int v = Integer.parseInt(st.nextToken());
    graph.get(u).add(v);
    deg[v]++;
}

 

2.

Queue<Integer> q = new LinkedList<>(); // degree가 0인 정점을 먼저 queue에 넣는다.

for(int i = 1; i <= n; i++) {
    if (deg[i] == 0) {
        q.add(i);
    }
}

 

3 & 4.

while(!q.isEmpty()){
    int cur = q.poll();
    System.out.println(cur);
    for(int nxt : graph.get(cur)) {
        deg[nxt]--;
        if (deg[nxt] == 0) q.add(nxt);
        // System.out.println("nxt: " + nxt);
    }
}