[ 알고리즘 ] Graph Traversal : Recursive DFS

1. Recursive DFS

 

RDFS 는 시작노드로부터 인접한 노드로 방문하는데,

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

 

1.1 DFS tree

DFS에서 전진한 edges로만 생성한 결과를 DFS Tree라 한다.

시작 노드가 루트이고, 전진하면서 방문한 노드들을 자식으로 하나씩 갖게 된다.

 

1.2 edge 종류

• Tree Edges: DFS Tree에 들어간 모든 엣지들
• Forward Edges: 조상에서 자손으로 연결되는 엣지 중 트리에 포함되지 않는 엣지들
• Back edges: 자손에서 자기보다 조상들 중 하나로 연결되는 엣지 (DFS 과정에서 이미 방문한 노드로 향하는 엣지)
• Cross Edges: 자손과 조상 관계가 아닌데 연결되는 엣지로 DFS Tree에는 이 엣지가 있으면 모순이 생겨서 존재하지 않는다.

*cross edge가 존재할 수 없는 이유

 

2. Bipartite Graph Detection

 

Bipartite Graph는 이분 그래프로 두 개의 그룹으로 정점들을 나눴을 때 같은 집합끼리는 인접하지 않는 그래프를 의미한다.

Bipartite Graph

Bipartite Graph인지 확인하는 방법은 DFS tree를 만들었을 때  루트는 A, 레벨 1은 B, 레벨 2는 A, ... 이렇게 반복하면서 그룹 A B를 구분하는 것이다.

Bipartite Graph DFS tree

이때 서로 다른 그룹으로 가는 Back Edge는 존재할 수 있지만, 같은 그룹 내에서 이동하는 Back Edge는 존재하면 안된다.