14. 방향그래프 (Directed Graph)

방향 그래프는 그래프 G 안의 모든 간선이 유향 간선인 그래프를 말한다. 유향 그래프라고도 한다.
항공 노선, 작업 스케줄링 등을 구성하는데 쓰인다.

방향 그래프에서, 각 노드의 진입 간선과 진출 간선을 별도의 리스트로 관리하면 각각의 집합을 각각의 크기에 비례한 시간에 조사할 수 있다.

방향 DFS

DFS와 BFS 알고리즘이 간선의 방향에 따라서만 탐색하도록 하면 방향 그래프에 특화시킬 수 있다.
방향 DFS 알고리즘에선 아래 네 종류의 간선이 발생한다.

• 트리 간선: DFS 트리에 사용된 간선
• 후향 간선: DFS 트리에서, 아래에서 위로 향하는 간선
• 전향 간선: DFS 트리에서, $i$ 레벨 노드에서 $i+n (n>2)$ 노드로 향하는 간선
• 교차 간선: DFS 트리에서, 같은 레벨 노드로 향하는 간선

연결성

노드 $s$에서 시작하는 방향 DFS는, 노드 $s$에서 도달 가능한 노드들을 결정한다.
노드 $u$에서 $v$로의 경로가 존재하면 $u$는 $v$에 도달한다, $v$는 $u$에서 도달 가능하다 라고 표현한다.

만약 그래프 $G$ 안의 모든 노드쌍 $(u,v)$가 서로 도달 가능하면, 해당 그래프는 강연결이라고 한다.

방향 DFS를 이용하여, 강연결이 성립하는 최대의 부그래프인 강연결요소를 얻을 수 있다.

이행적폐쇄

어떤 그래프 $G$에서, 노드 $a$부터 $c$로 향하는 경로가 존재할 때, 간선 $(a,c)$가 존재하고 그래프 $G$의 모든 간선과 노드를 가진 그래프 $G*$를 이행적폐쇄라 한다.

즉, 이행적폐쇄 그래프는 그래프의 도달 가능성 정보를 제공한다.

이행적폐쇄는 DFS로 $O(n(n+m))$ 시간에 계산할 수 있는데, 대안으로 플로이드-워셜 알고리즘을 사용할 수도 있다.

플로이드-워셜 알고리즘^{Floyd-Warshall}

1. 정점들을 $1, 2, \cdots, n$으로 번호를 매긴다.
2. $1, 2, \cdots, k$까지의 정점만을 경로로 사용하는 경로들을 탐색하여 G에 추가
3. $k$ 단계에서, $G_{k-1}$에 기반하여 $G_k$를 계산한다.
4. 마지막 $G_n$이 이행적폐쇄 그래프가 된다.

def FW(G):
    G[0] = G
    for k in range(1, n+1): # 1 to n
        G[k] = G[k-1]
        for i in range(1, n+1): # start vertex
            if i == k:  # i != k
                continue
            for j in range(1, n+1): # end vertex
                if j == i or j == k:  # j != i, j!= k
                    continue
                if G[k-1].areAbjacent(v[i], v[k]) and G[k-1].areAbjacent(v[k], v[j]): # i->k->j 경로 존재하면
                    if !G[k-1].areAbjacent(v[i], v[j]): # i->j 경로 없으면
                        G[k].insertDirectedEdge(v[i], v[j]) # 만들기
    return G[n]

areAbjacent 함수가 $O(1)$시간에 수행된다면 (즉, 인접 행렬) 이 알고리즘은 $O(n^3)$의 시간 복잡도를 갖는다.

동적 프로그래밍

알고리즘 설계 기법 중 하나로, 많은 시간이 소요되지만 아래 조건에 해당하는 부문제들로 이루어진 문제 해결에 적용 가능하다.

• 부문제 단순성: 부문제들이 몇 개의 변수로 정의될 수 있는 경우
• 부문제 최적성: 전체 최적치가 최적의 부문제들에 의해 정의될 수 있는 경우
• 부문제 중복성: 부문제들이 독립적이지 않고 중복될 경우