방향있는 그래프(directed graph)

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

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

방향있는 그래프의 예시

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

순환 그래프(cyclic graph)

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

순환그래프의 예시

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

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

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

DAG의 예시

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

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

Strongly Connected Components

위 그래프에는 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

정점 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. 반복

위 그래프에서 정점 내 숫자는 각 정점들의 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는 방향을 역으로 바꾼 간선들을 나타낸다.

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|)다.

출처

• 코세라 알고리즘 강의