그래프 간선의 분류

다음과 같이 어떤 방향 그래프가 주어졌을 때

그래프를 깊이 우선 탐색하면서 따라가는 간선들만 모으면 트리 형태를 띠게 됩니다. 

0번 정점에서 dfs함수를 호출해서 dfs함수가 따라가는 간선들을 오렌지 색으로 나타내고 각 정점의 방문 순서를 괄호로 표시했습니다.

이런 트리를 주어진 그래프의 DFS 스패닝 트리(DFS Spanning Tree)라고 합니다. 

그래프의 DFS 스패닝 트리를 생성하고 나면 그래프의 모든 간선을 네가지 중 하나로 분류할 수 있습니다.

1. 트리 간선(tree edge) : 스패닝 트리에 포함된 간선

2. 순방향 간선(forward edge) : 스패닝 트레에서 선조에서 자손으로 연결되지만 트리 간선이 아닌 간선

3. 역방향 간선(backward edge) : 스패닝트리에서 자손에서 선조로 연결되는 간선

4. 교차 간선(cross edge) : 위 세가지 분류를 제외한 간선으로 트리에서 선조와 자손 관계가 아닌 정점들간에 연결된 간선을 의미

cf) 저는 이 정의를 보고 트리에서 선조와 자손의 정확한 정의를 몰라서 간선을 구분하는것이 헷갈렸었는데 정의를 한번 확인해 보세요!

선조 노드(Ancestor Node) : 루트 노드에서 어떤 노드에 이르는 경로에 포함된 모든 노드 

예시) 위 DFS스패닝 트리에서 5번 노드의 선조 노드 :  1, 3, 4번 노드 

자손 노드(Descendant Node) : 어떤 노드에서 잎 노드(Leaf Node)에 이르는 경로에 포함된 모든 노드(잎 노드는 자손이 없는 노드를 의미합니다.)

예시) 위 DFS스패닝 트리에서 3번 노드의 자손 노드 : 2, 4, 5, 7번 노드

이제 위 DFS스패닝 트리에 대해서 1. 트리 간선, 2. 순방향 간선, 3. 역방향 간선, 4. 교차간선으로 분류 해 보겠습니다.

지금까지 방향 그래프의 간선의 분류에 대해서 살펴보았습니다. 

그러면 무향 그래프에서는 간선을 어떻게 분류할 수 있을까요? 

무향그래프에서 간선은 항상 양방향 통행이 가능하므로 역방향간선과 순방향간선의 구분이 없으며 교차 간선이 있을 수 없습니다. 

저는 처음에 그래프 간선의 분류를 접할 때 어디에 이 개념이 사용되는지 몰라서 이러한 분류가 무의미하고 형식적이라고 생각했지만

나중에 보니 그래프를 다루는 알고리즘을 서술하는데 중요하게 사용된다는 것을 알게됬습니다.

예로 그래프에서 사이클 존재 여부가 역방향 간선의 존재여부와 동치인 것을 이용해 판단하는 것과

절단점 알고리즘과  SCC Tarjan 알고리즘에서 역방향 간선과 교차 간선의 개념이 중요하게 사용되는 것을 들 수 있습니다.

이제 이를 코드상으로 분류해봅시다. 어떤 특징들이 그래프에서 네가지 간선을 분류할 수 있게 할까요?

정점 A, B사이의 간선 (A, B)를 살펴봅시다.

따라서 위 조건을 이용하면

발견된 순서를 기록하는 배열(int discovered[MAXV])과 각 정점에서의 dfs함수 종류 상태를 기록하는 배열(bool finished[MAXV])를 도입하여 dfs 탐색을 진행하면서 모든 간선을 분류할 수 있습니다.

[알고리즘 문제해결전략 책을 참고해서 작성했습니다]