[자료구조] 16. 방향 그래프(Directed Graph = Digraph)

Directed graph란 유방향 간선으로 이루어진 그래프를 의미합니다. 이에 대치되는 개념은 앞선 시간에서 살펴보았던 undireced graph, 즉 무방향 간선으로 이루어진 그래프입니다.

Directed graph에서 간선 정리

Undirected graph에서 그래프 탐색을 할 때는 DFS의 경우 unvisited, discovery, back edge의 3가지 간선 종류가 있었고, BFS의 경우에는 unexplored, discovery, cross edge의 3가지 간선 종류가 있었습니다. Directed graph의 탐색된 간선은 4가지가 있는데, 이를 정리해 보도록 하겠습니다.

정점 v에서 시작하여 DFS와 BFS 등으로 탐색된 경로가 정점 v를 루트로 하는 트리와 같은 형식이라는 것을 염두에 둔다면 다음 내용을 이해하기 쉽습니다.

• Discovery edge: 이전에 방문하지 않았던 정점으로 성공적으로 방문한 간선입니다.
• Back edge: 이전에 방문했던 정점으로 이어지는 간선으로, 방문한 정점이 출발 정점의 조상인 간선입니다.
• Forward edge: 이전에 방문했던 정점으로 이어지는 간선으로, 방문한 정점이 출발 정점의 후손인 간선입니다. 특성상 BFS에서는 존재하지 않는데, BFS는 단계별로 탐색을 하기에 방문한 정점이 후손이 되기 전에 이미 방문을 했을 것이기 때문입니다.
• Cross edge(교차 간선): 이전에 방문했던 정점으로 이어지는 간선으로, 방문한 정점이 출발 정점의 조상도 후손도 아닌 간선입니다.

Directed DFS

Directed BFS

Rechability와 Strong connectivity

DFS, BFS 경로로 만들어진 트리에서 정점 u, v에 대해 u -> v로 갈 수 있는 경로가 있다면 v가 u에서 reachable 하다고 합니다. 이때 모든 정점에 대하여 서로 reachable 하다면 strongly connected 되었다고 합니다.

이러한 strong connectivity를 검증하기 위한 방법으로 DFS를 사용할 수 있습니다. 그렇다면 모든 정점에 대하여 rechable한지 확인해야 하니 모든 정점에 대하여 O(n+m) 시간이 걸리는 DFS를 시행하여 총 O(n*(n+m))시간에 검증을 해야 할까요? 실제로는 모든 정점에 대한 검증이 필요하지 않고, 단 2번의 DFS를 통하여 strong connectivity를 검증할 수 있습니다. 과정은 다음과 같습니다.

1. 그래프 G의 임의의 정점 v에서 DFS를 시행합니다. 이때 방문이 안된 정점이 있다면 strong connected 되지 않은것입니다.

2. 그래프 G의 모든 간선방향을 역전시킨 그래프 G'에 대하여 정점 v에서 DFS를 시행합니다. 이때 방문이 안된 정점이 있다면 strong connected 되지 않은 것입니다.

3. 모든 과정을 거쳤으면 그래프 G는 strongly connected 된 것입니다.

어째서 이렇게 2번의 DFS로 검증이 가능한 걸까요? 우선 1번 과정에서 v에서 출발했을 때 모든 정점을 방문할 수 있음을 보였습니다. 그리고 2번 과정에서 반전된 그래프를 검증하는 것은 그래프의 모든 정점에서 v로 가는 경로가 있다는 것을 보여줍니다. 그렇다면 어느 정점에서 출발해도 v로 갈 수 있고, v에서 어디로든 갈 수 있으니, 그래프의 모든 정점은 reachable 하다는 증명이 가능합니다.

DAG와 Topological ordering

Topological sorting(위상 정렬)

DFS로 위상 정렬 구현