CS/알고리즘_개념

SCC-코사라주 알고리즘(Kosaraju's Algorithm)

Jedy_Kim 2021. 6. 9. 14:12
728x90

방향 그래프(Directed Graph) 에서 SCC (Strongly Connected Component) 를 코사라주 알고리즘을 이용해 구하는 방법이다.

 

① 주어지는 방향 그래프있다.

② 주어지는 방향 그래프와 역방향을 가지는 역방향 그래프를 만든다.

③ 정점을 담을 스택을 만든다. 

코사라주는 위상정렬을 이용하고, 방향그래프와 역방향그래프가 동일한 SCC를 구성하는 것을 이용한다.

①-③ 까지 방향그래프, 역방향그래프, 스택을 준비한다.

 

순서는 아래와 같다. 

①② ③

1) ①방향그래프에 임의의 정점부터 DFS를 수행한다. DFS가 끝나는 순서대로 ③스택에 삽입한다. 

     1-1) DFS를 수행한 후 아직 방문하지 않은 정점이 있는 경우, 해당 정점부터 다시 DFS를 수행한다. 

     1-2) 모든 정점을 방문하여 DFS를 완료하여 스택에 모든 정점을 담는다.

2) 스택의 top 에서부터 pop을 하여 순서대로 ②역방향 그래프에서부터 DFS를 수행한다. 

     2-1) 이때 탐색되는 모든 정점을 SCC로 묶는다.

     2-2) 이 과정은 스택이 비어있을 때까지 진행한다.

     2-3) 만약 스택의 top에 위치한 정점이 이미 방문했다면 pop만 한다.

 

위 과정을 수행하면 주어진 그래프에서 SCC를 구할 수 있다.  

위와 같은 방향그래프가 있다고 할 때, SCC를 구해보자.

 

설명된 순서와 동일하게 ①방향그래프 ②역방향그래프 ③스택을 준비하자.

 

1) ①방향그래프에 임의의 정점부터 DFS를 수행한다. DFS 가 끝나는 순서대로 ③스택에 삽입한다.

[탐색조건] 여기서 방문하지 않은 정점을 찾는 조건을 둔다. 방문하지 않은 정점을 찾는 순서는 오름차순으로 번호가 낮은 정점부터 탐색한다.

그러면 1번 정점부터 탐색을 시작한다. 

이후 인접한 정점인 3번을 탐색한다.

 

3번 정점에서 인접한 정점은 5번, 6번 정점이 있는데 [탐색조건] 에 맞춰 5번정점부터 탐색한다.

 

그리고 5번정점에서 인접한 3번정점은 방문한 상태이므로, 6번 정점을 방문한다.

이후 6번정점에서 인접한 4번정점을 방문한다.

다음 4번정점에 인접한 2번정점을 방문한다.

 

이제 더이상 방문할 정점이 없으므로 DFS가 끝난 순서대로 스택에 삽입한다. 

 

 

과정 1)을 완료하였고, 이제 과정 2)를 진행한다.

 

2) 스택의 top 에서부터 pop을 하여 순서대로 ②역방향 그래프에서부터 DFS를 수행한다. 

     2-1) 이때 탐색되는 모든 정점을 SCC로 묶는다.

     2-2) 이 과정은 스택이 비어있을 때까지 진행한다.

     2-3) 만약 스택의 top에 위치한 정점이 이미 방문했다면 pop만 한다.

 

먼저 스택 TOP 에 위치한 1번 정점부터 ②역방향 그래프에서 DFS 탐색을 진행한다.

1번 정점에서는 다른 정점으로 DFS를 진행할 수 없으므로 1번 정점이 하나의 SCC가 된다.

 

 

다음으로 스택 TOP에 위치한 3번정점부터 DFS 탐색을 한다.

3번정점에 인접한 정점은 모두 같은 SCC가 된다. 

[탐색조건]에 따라 낮은 정점부터 DFS를 진행한다. 

1번정점은 이미 방문한 정점이므로 방문할 수 없다. 

2번정점을 방문한다. 

다음 4번정점을 방문한다.

다음 6번정점을 방문한다.

다음 5번정점을 방문한다.

3번정점부터 시작한 DFS 이 더 이상 방문할 정점이 없으므로 이것을 하나의 SCC로 묶는다.

스택에 있는 정점을 top부터 꺼내어 보면서 방문하지 않은 정점이 있는지 확인한다. 

이제 ②역방향 그래프 에서 모든 정점을 방문하였다.

 

그러면 ①방향그래프  2개의 SCC로 구성되어있음을 볼 수 있다.

 

 

BOJ-2150 : https://www.acmicpc.net/problem/2150

Strongly Connected Component 문제를 풀어보면 될 것 같다. 

 

코사라주로 구현한 BOJ-2150 코드는 http://wondy1128.tistory.com/28 을 참고하면 된다. 



출처: https://wondy1128.tistory.com/130 [잡블로그]

 


https://www.cs.usfca.edu/~galles/visualization/ConnectedComponent.html

 

Connected Component Visualization

 

www.cs.usfca.edu

#코드(너무 어렵다...)

결과그래프가 요렇게 나와야된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import sys
 
def get_time(node): 
  global myGraph, time, clock, order, order_len, n, m
  # node부터 시작해서 DFS를 하면서, 빠져나오는 순서대로 시간을 기록
  check[node] = True
  for i in rangelen(myGraph[node]) ):
    node2 = myGraph[node][i]
    
    if check[node2] == False:
      get_time(node2)
      
  # 나와 인접한 요소들 모두 방문
  # 빠져나갈 때 시간을 기록해야됨.
  time[node] = clock 
  clock += 1 
  order[order_len] = node
  order_len += 1
 
# node에서부터 DFS, 하지만 거꾸로된 그래프 대해서.
def get_my_group(node):
  global reverseGraph, check2, group, group_cnt
  check2[node] = True
  group[node] = group_cnt
  
  for i in range(len(reverseGraph[node])):
    node2 = reverseGraph[node][i]
    if check2[node2] == False:
      get_my_group(node2)
  
 
if __name__ == "__main__":
  input = sys.stdin.readline
  
  n,m = map(int, input().split())
  # 입력받은 그래프
  myGraph          = [[] for _ in range(n+1)] 
  # 간선의 방향을 바꾼 그래프
  reverseGraph     = [[] for _ in range(n+1)] 
  # 빠져나오는 시간을 순서대로 기록,  clock을 1씩 증가시켜 나감.
  time, clock = [0]*(n+1), 1
  # 방문체크
  check, check2 = [False]*(n+1), [False]*(n+1)
  # 빠져나오는 순서대로 노드를 기억 : order[0]에는 빠져나오는 시간이 제일 빠른 노드
  order, order_len = [-1]*(n+1), 0
  # group[i] : 정점 i가 속한 그룹 번호
  group, group_cnt = [0]*(n+1), 1 
  
  
  for i in range(m):
    a, b = map(int, input().split())
    
    myGraph[a].append(b) # 방향성 그래프
    reverseGraph[b].append(a)
   
  # DFS를 하면서 빠져나오는 순서대로 시간을 기록
  for i in range(1, n+1):
    if check[i]==False
      get_time(i)
  
  # 빠져나오는 순서대로 시간이 기록됨.
  # 뒤집은 그래프에 대해서 빠져나오는 시간이 큰 노드부터 순회
  # 이 때 만나는 노드들이 모두 같은 그룹임.
  for i in range(order_len-1-1-1):
    node = order[i]
    if check2[node] == False:
      get_my_group(node) # node와 똑같은 그룹을 가지는 모든 정점을 알 수 있다.
      group_cnt += 1
      
  
  for i in range(1, n+1):
    print(i, group[i])
  print(group_cnt-1)
cs

 

입력
12 18
1 2 
2 3
2 4
3 1
3 7
3 9
4 6
4 11
5 4
6 5
7 8
7 9
8 10
8 12
9 10
10 7
11 12
12 11

출력
1 1
2 1
3 1
4 2
5 2
6 2
7 3
8 3
9 3
10 3
11 4
12 4
4

 

반응형