[알고리즘] 13. Graph Traversal, Edge의 종류

[알고리즘] 13. Graph Traversal, Edge의 종류

1. Any-Order Traversal

Anyorder Traversal: 어떤 노드 s에서 시작하고 s를 BOX에 넣는다. BOX가 비어있지 않으면 아래의 과정을 반복한다. 하나의 노드를 꺼내고 방문하지 않은 노드라면 방문한 뒤 어떤 계산을 수행한다. 그리고 노드와 인접한 모든 엣지들을 BOX에 넣는다. 이후 이 과정을 계속 반복한다.

AnyOrder Traversal이 Reachable한 노드는 모두 방문한다는 것을 증명하자. 노드 t가 s에서 reachable 하다고 가정하자. (Box에 들어가는 노드는 모두 reachable 하다는 것은 invariant 이다.)

$t=s$인 경우 s를 방문하는 것이 t를 방문하는 것이므로 성립한다. $s\rightarrow a_1 \rightarrow a_2 \rightarrow ... \rightarrow t$ 를 통해서 도달한다고 하자. 이 sequence에서 t보다 앞에 있는 노드 $a_i$까지만 방문해서, t를 방문하지 않는다고 가정하자. (귀류법) 따라서 $a_{i+1}$은 방문하지 않은 노드이다. 이때 $a_{i+1}$은 $a_i$와 인접한 노드이므로 Box에 들어간다. 알고리즘에 의해 $a_{i+1}$은 Box에서 꺼내지므로 방문하게 된다. 모순 발생!

알고리즘별 BOX의 종류

DFS: Stack

BFS: Queue

Prim: PQ with edge weight

Dijkstra: PQ with distance (from s)

A*: PQ with Arbitrary Function

2. Recursive DFS와 Edge의 종류

RDFS 는 시작노드로부터 인접한 노드로 방문하는데, 앞 노드가 방문되지 않았으면 그 노드에서 또 재귀적으로 호출한다. 각 노드들이 RDFS의 인자가 되는 것은 한번 뿐이므로 시간 복잡도는 $O(m+n)$이 걸린다.

DFS에서 전진한 edges로만 생성한 결과를 DFS Tree라 한다. 시작 노드가 루트이고, 전진하면서 방문한 노드들을 자식으로 하나씩 갖게 된다.

Tree Edges: DFS Tree에 들어간 모든 엣지들

Forward Edges: 조상에서 자손으로 연결되는 엣지 중 트리에 포함되지 않는 엣지들

Back edges: 자손에서 자기보다 조상들 중 하나로 연결되는 엣지 (DFS 과정에서 이미 방문한 노드로 향하는 엣지)

Cross Edges: 자손과 조상 관계가 아닌데 연결되는 엣지로 DFS Tree에는 이 엣지가 있으면 모순이 생겨서 존재하지 않는다.

3. Bipartite Graph Detection

Bipartite Graph는 이분 그래프로 두 개의 그룹으로 정점들을 나눴을 때 같은 집합끼리는 인접하지 않는 그래프를 의미한다. 이분 그래프인지 확인하는 방법은 DFS Tree를 만들었을 때 루트는 A, 레벨 1은 B, 레벨 2는 A, ... 이렇게 반복하면서 그룹 A B를 구분하는 것이다. 이때 서로 다른 그룹으로 가는 Back Edge는 존재할 수 있지만, 같은 그룹 내에서 이동하는 Back Edge는 존재하면 안된다.

from http://pongkijoa.tistory.com/20 by ccl(A) rewrite - 2021-12-27 12:26:38