코시라주 알고리즘과 SCC (python)

목적

방향그래프에서의 사이클들을 찾는다.

우리가 구할것은 사이클관계인 정점들의 집합(리스트)이 원소인 리스트이다.

(노드 1개도 하나의 사이클이 된다.)

 

 

사이클의 정의

방향그래프에서

a,b가 그래프에 포함되는 정점이라 하면 a -> b로가는 경로가 있고

b -> a로 가는 경로가 있는 경우이다.

X를 정점 집합이라 할때

a -> X -> b 란 경로가 있고 b ->a 로 가는 경로가 존재한다면

a -> X -> b -> a -> X -> b가 성립하므로

X에 속하는 정점 k에 대해

a -> k k-> a

k -> b b -> k가 성립한다.

따라서 {a X b}는 한 사이클 집합에 포함된다.

단 무향그래프(양방향그래프)의 경우엔

간선 a->b가 있다면 모든 간선을 a->b 간선이 있고 b->a간선이 있다고 정의하고 그래프를 만드므로 

모든 정점이 한 사이클에 속할 것이다.

따라서 방향그래프에서만 생각해본다.

 

코사라주 알고리즘 

O(V+E)에 사이클들을 찾을 수 있다.

0. DFS를 사용할 것이다. DFS는 정점을 방문하면 방문처리를 하고 이는 다시 방문하지 않는다.

1. 원래 그래프 origin와 모든 간선방향을 반전시킨 역방향그래프 rvs를 준비한다.

2. stack1을 준비한다. origin에서 방문하지 않은 정점에 대해 DFS를 수행하고 방문처리한다.

2-1. DFS수행 후 탐색한 순서에 역순으로 stack1에 정점을 삽입한다.

예를들면 1 3  2 4 순서로 탐색했다면 

```

stack1.push(4)

stack1.push(2)

stack1.push(3)

stack1.push(1)

```

3. rvs의 사이클과 origin의 사이클은 같다는 것이 직관적으로 이해된다.

방문처리를 초기화하고

stack1을 pop()하며

그 순대로 rvs에서 DFS를 수행하고 방문처리한다.

특정 정점 n에서 시작해 rvs그래프에서 DFS를 수행한 정점들의 집합이 X일때,

X안에 있는 원소들은 서로 한 사이클관계이다.

 

코드

https://github.com/nayounsang/pythonAlgorithm/blob/master/graph/SCC/kosaraju.py

GitHub - nayounsang/pythonAlgorithm: Algorithm template code with python.

 

대표문제

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

 

응용

SCC 문제에 많이 응용되는 것이 있다.

새로운 인접리스트(그래프)를 정의하고

각 사이클을을 하나의 정점으로 압축하고 정점으로 생각한다.

그리고 특정 방향으로 사이클1 -> 사이클2로 갈 수 있다면

그것을 정점1 -> 정점2로 가는 간선으로 생각한다.

즉 사이클끼리 관계를 새로운 그래프로 정의하는 것이다.

이것을 어떻게 구현할지 고민해보자...

 

응용문제

https://www.acmicpc.net/problem/4013

4013번: ATM

 

더 나아가서

2-SAT 문제는 SCC에 기반을 둔 문제유형이다.