DFS를 통한 간선의 분류
DFS 스패닝 트리
깊이 우선 탐색을 수행하면 그 과정에서 그래프의 모든 간선을 최소 한 번씩은 만나게 된다. 그 중 처음 만나는 정점과 연결되는 간선은 따라가게 되는데, 이러한 간선들을 모아서 보면 트리 형태를 띠게 된다. 이러한 트리는 당연히, 모든 정점을 지나치므로 스패닝 트리가 되고 이를 DFS 스패닝 트리라고 부른다
간선의 분류
- 트리 간선
DFS 스패닝 트리에 포함된 간선을 뜻한다.- 순방향 간선
DFS 스패닝 트리에 포함되지 않았고 간선의 방향이 선조에서 자손으로 이어진 경우를 말한다.- 역방향 간선
순방향 간선과 같지만 자손에서 선조로 이어진 간선을 말한다. 무향 그래프의 경우 주체가 되는 정점에 따라 같아지므로 역방향 간선과 순방향 간선의 구분이 없다.- 교차 간선
어느 경우도 속하지 않는 간선을 말한다. 무향 그래프의 경우 존재하지 않는다.
간선의 분류 응용
위상 정렬 증명
위상 정렬의 배열 역순으로 간선이 존재하면 위상 정렬은 유효하지 않게 되는데, 각 간선 분류 별로 그 경우를 가정해보면, 간선의 정의 또는 가정과 모순되게 되어 dfs를 통한 위상 정렬의 유효함을 증명할 수 있다.
사이클 존재 여부
역방향 간선의 존재와 동치이다. 사이클을 만드는 간선을 가지고 있는 정점에 도착했을 때를 생각해 보면 그 간선은 반드시 선소와 이어진 역방향 간선임을 알 수 있다.
간선 구분 구현
- 처음 발견하는 정점으로 가는 경우 -> 트리 간선
- 이미 발견했던 정점으로 가는 경우
- 이어진 정점보다 먼저 발견된 경우 -> 순방향 간선
- 이어진 정점보다 늦게 발견된 경우
이어진 정점의 탐색이 종료되지 않는 경우 -> 역방향 간선
이어진 정점의 탐색이 종료된 경우 -> 교차 간선
절단점 찾기
절단점 찾기란
절단점이란 그래프의 정점 중 그 정점과 연결된 간선을 모두 제거했을 때 그래프가 두개의 컴포넌트로 나누어 지는 경우를 말한다. 즉, 그래프를 두개로 절단하는 정점이다.
무향그래프에서 절단점 찾기 알고리즘은 간선 분류 알고리즘을 응용해서 만들 수 있다.
절단점이 되기 위해서는 DFS 스패닝 트리를 만들었을 때 그 정점을 기준으로 한 서브트리 밑에 있는 모든 정점에서 역방향 간선이 존재하지 않아야 한다. 만약 역방향 간선이 존재하게 된다면 이 정점을 통하지 않고서도 이 서브트리 밖으로 나갈 수 있는 경로가 존재한다는 뜻이기 때문에 절단점이 될 수 없는 것이다.
정점의 도착 순서를 기록함으로서 이를 구현할 수 있다. 서브 트리에 속한 정점들의 간선들 중 이 정점보다 빨리 도착한 정점과 연결된 간선이 있다면, 이는 반드시 역방향 간선이 되므로 이 정점은 절단점이 될 수 없다.
이를 확인하기 위해서 서브트리에 속한 간선과 닿는 정점들의 최소 도착 순서를 현재 보고 있는 정점의 도착 순서와 비교한다.
최소 도착 순서만을 따지는 이유는 어차피 최소 도착 순서만 확인하면 그 보다 늦게 도착한 선조들은 굳이 따지지 않아도 방문할 수 있게 되기 때문이다.
응용 - 다리 찾기
다리란 그래프의 간선 중 그 간선을 제거하면 그래프가 두개의 컴포넌트로 나뉘어지는 간선을 말한다. 절단점은 정점, 다리는 간선이다.
다리를 찾기 위한 과정은 절단점을 찾는 과정과 매우 유사하다. (u,v)가 다리가 되는지를 확인하기 위해서는 v의 서브 트리 중 u로 가는 역방향 간선을 제외한 역방향 간선들과 연결된 정점들 중 발견 순서가 최소가 되는 정점이 u보다 먼저 발견 되었다면 다리가 될 수 없다.
