# 방향있는 그래프(directed graph)

### 방향있는 그래프의 선형 순서

방향이 있는 그래프에는 정점 `v`에서 정점 `u`으로 이동이 가능하지만 `u`에서는 `v`로 이동할 수 없는 간선이 있다. 따라서 어떤 정점에서 다른 정점으로 이동하기 위한 선형 순서(linear order)가 그래프에 존재할 수 있다.

![방향있는 그래프의 예시](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-LxaLneyOHRajFzoCGX6%2F-LxaNfVOYa2kMpAhQReI%2Fdirected_graph.png?alt=media\&token=88697715-5c5a-4e92-b06a-6cc74c93b50f)

위 그래프의 경우 정점 `4`에 도착하기 위해서는 정점 `2`를 거쳐야 하고, 정점 `2`를 거치려면 정점 `1`에서 출발해야 한다. `1 -> 2 -> 4` 와 같이 경로에 정점의 순서가 선형적으로 있는 것이다.

### 순환 그래프(cyclic graph)

순환 그래프는 아래와 같은 형태를 한다.

![순환그래프의 예시](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-LxaOg-vmRn2zAWK0inL%2F-LxaPVIoNKPmWTQTDph2%2Fcycled_graph.png?alt=media\&token=fc109d9d-587d-46b0-a157-4a4e5a0f566b)

**모든 정점 또는 일부가 하나의 사이클을 이루는 그래프를 순환그래프(cycled graph)**라고 한다. 위 그래프의 경우 `A -> B -> C -> E -> D -> B -> C ...` 와 같이 정점 B, C, E, D가 사이클을 이루고 있다. 어느 정점이 다른 정점에 우선하는지 순서를 결정할 수 없기 때문에 **순환그래프에는 선형적 순서가 존재하지 않는다.** 

### 방향있는 비순환 그래프(DAG, Directed Acyclic Graph)

DAG(Directed Acyclic Graph)는 두 정점 사이의 간선에 방향이 있으며 그래프 내 사이클이 존재하지 않는 그래프다. DAG에는 선형적 순서가 존재한다.

![DAG의 예시](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-LxaOg-vmRn2zAWK0inL%2F-LxaQyBxY5RSu4n8CUCj%2Fdag.png?alt=media\&token=7144b175-be80-4821-8c6c-6d008d60b8a7)

### 강하게 연결된 성분(SCC, Strongly Connected Component)

방향있는 그래프에서 **SCC이란 정점 `v`에서 정점 `u` 로 향하는 경로가 있으면서 `u`에서 `v`로 향하는 경로도 있는 서브그래프**를 뜻한다. 

![Strongly Connected Components](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-LxfHfccV3tfUmQacI45%2F-LxfRGiL1xpxLw6LIu30%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-01-03%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%209.45.33.png?alt=media\&token=11de66e2-a0a0-4627-890d-f5a485ed2b9a)

위 그래프에는 SCC 총 5개다.

* 정점 `D`, `G`, `F`는 self-loop 경로가 있어서 SCC에 포함된다.
* 정점 `H`에서 `I`로 이동가능한 경로가 있고 `I`에서도 `H`로 향하는 경로가 있으므로 `H`, `I`는 SCC에 포함된다.
* 정점 `A`, `B`, `C`, `E` 에도 두 정점에서 서로 이동가능한 경로가 모두 존재한다. (`A`에서 `C`로 가는 경로가 있으면서 `C`에서 `A`로 가는 경로가 존재한다.)

이러한 **SCC들을 뭉뚱그려서 하나의 정점으로 표현할 수 있는데, 이렇게 표현된 그래프를 메타그래프(metagraph)**라고 한다. 위 SCC들을 메타그래프로 나타내면 아래와 같다.

![metagraph](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-LxfU9sldzdsT2hck7RQ%2F-LxfVQpAXIoCKBD5BiUm%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-01-03%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%2010.01.20.png?alt=media\&token=96f4a92c-bc60-4817-a98b-83a042e64772)

정점 `D`에서 정점 `A`로 향하는 경로가 있고 정점 `A`의 connected component는 `B`, `C`, `E` 이다. 따라서 `D`에서 `B`, `C`, `E`로 향하는 경로도 있다.

이 때 **메타그래프는 항상 DAG(Directed Acyclic Graph)형태를 하고 있다**. 그래프 내에서 SCC는 항상 사이클을 이루고, 사이클을 이루는 이 connected component들은 메타그래프에서 항상 하나의 정점으로 추상화되기 때문이다. 

#### 그래프에서 SCC를 찾는 방법

DAG를 정렬하는 방법은 아래와 같았다.

1. 그래프에서 싱크를 찾는다.
2. 찾은 싱크를 결과리스트에 삽입한다.
3. 싱크와 간선을 그래프에서 삭제한다.
4. 1 \~ 3을 반복한다.

그래프에서도 SCC들을 탐색하기 위해서는 sink SCC를 찾아야 한다.

1. 그래프 `G`의 간선 방향을 모두 역으로 바꾼다. 간선방향을 바꾼 그래프를 `rG`라고 하자. `G`와 `rG`의 SCC는 동일하다.
2. `rG`에서 DFS를 실행하여 각 정점들의 post time(어떤 정점 `v`에서 호출한 서브루틴들이 완전히 종료되어 `v`를 파라미터로 갖는 함수가 완전히 종료되는 시간)을 내림차순 정렬한다. `rG`에서 post time이 가장 높은 정점은 `rG`의 source이면서 `G`의 sink에 해당한다. 
3. post time이 가장 큰 정점을 `v`라고 하자. `v`를 시작으로 DFS를 실행한다. DFS를 통해 찾아낸 정점들은 `v`의 connected component들이며 `G`의 sink SCC이다.
4. `v`와 `v`의 connected component들을 G에서 삭제한다.
5. `v` 다음으로 post time이 큰 정점을 시작으로 DFS를 실행한다.
6. 반복

![](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-Lxfg92Md4cfM_nN7tQQ%2F-Lxfmke4UqTtnhv3-9Vc%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-01-03%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%2011.24.05.png?alt=media\&token=30e4dd6d-dc59-4444-925b-c3f128c75b30)

위 그래프에서 정점 내 숫자는 각 정점들의 post time을 나타낸다. post time이 가장높은 18에 해당하는 정점 `F`에서 DFS를 실행했을 때 `F`에서 이동가능한 경로가 없으므로 `F`가 sink SCC이다. `F`를 그래프에서 삭제한다.

`F` 다음으로 post time이 17인 정점 `I`에서 DFS를 실행했을 때 `H`로 이동가능하며 `H`에서도 `I`로 이동가능하다. `H`와 `I`가 하나의 sink SCC이므로 `H`와 `I`를 그래프에서 삭제한다.  

아래 코드는 그래프에서 그래프 내 SCC의 갯수를 구하는 `distinguish_scc()`를 구현한 것이다. `reverse_adjacent_list`는 방향을 역으로 바꾼 간선들을 나타낸다.

```python
def distinguish_scc():
    tag = 0
    sorted_reversed_graph = topological_sort_reverse()
    
    # 정렬한 정점들을 시작으로 하여 DFS를 실행한다. 
    # 한번의 DFS가 종료되었을 때 SCC 한개를 탐색한 것과 같으므로 갯수를 +1 한다.
    for v in sorted_reversed_graph:
        if not visited[v]:
            explore(v)
            tag += 1
    return tag


# post_time을 기준으로 내림차순 정렬한 정점들을 리턴한다.
def topological_sort_reverse():
    for i in range(n):
        if not post_time[i]:
            explore_reversed_graph(i)

    sorted_result = sorted(post_time, key=lambda x: x[1], reverse=True)
    return [x[0] for x in sorted_result]


# 간선 방향이 바뀐 그래프를 대상으로 DFS를 한다. 각 정점의 post_time도 기록한다.
def explore_reversed_graph(v):
    global pre_time_cnt
    pre_time_cnt += 1
    pre_time[v] = pre_time_cnt

    for adj_v in reverse_adjacent_list[v]:
        if not pre_time[adj_v]:
            explore_reversed_graph(adj_v)

    global post_time_cnt
    post_time_cnt += 1
    post_time[v] = (v, post_time_cnt)


def explore(v):
    visited[v] = True

    for adj_v in adjacent_list[v]:
        if not visited[adj_v]:
            explore(adj_v)


print(distinguish_scc())
```

#### 시간복잡도

DFS의 시간복잡도는 `O(|V| + |E|)`이다. `distinguish_scc()`는 그래프 `G`에서 DFS를 1번 실행하고 간선의 방향을 바꾼 `rG`에서 DFS를 1번 실행한다. `post_time`을 기준으로 정렬된 각 정점들을 가지고 DFS를 또 실행하기 때문에 시간 복잡도는 `O(3 * (|V| + |E|))` = `O(|V| + |E|)`다.

출처

* [코세라 알고리즘 강의](https://www.coursera.org/learn/algorithms-on-graphs?specialization=data-structures-algorithms)