[1. 개요]
DFS 를 응용해서 해결 할 수 있는 문제 중 하나로,
어떤 무방향 그래프에서 절단점이란
- 이 점을 제거함으로 인해 edge 가 제거되고
- 이로 인해, 컴포넌트가 두개 이상으로 나뉘어지는 정점을 말한다.
최초 그래프가 하나의 컴포넌트로 이루어 졌는데,
어떤 정점을 제거하여, 그래프가 두개 이상의 컴포넌트로 나뉘어지면
전체 그래프는 연결되어 있지 않을 수 있다.
이러한 절단점을 찾기 위한 가장 단순한 방법은 아래와 같은데
- 모든 정점에 대해서, 정점을 제거하고
- dfsAll() 을 수행해서 컴포넌트 개수의 변화가 있는지 확인한다.
탐색 과정에서 얻는 정보를 이용하면, 한번의 dfs 로 모든 절단점을 찾아 낼 수 있다.
[2. 알고리즘]
- 임의의 정점에서 dfs 를 수행하는데,
- 무방향 그래프에서는 교차 간선이 존재하지 않으므로
- 어떤 정점 u 에 연결된 정점들은 모두 u 의 조상이거나 자손이 된다.
# 무방향 그래프이지만, 방문 순서를 통해, 이를 판별 할 수 있다. - 여기서 u 의 자손들을 루트로 하는 서브 트리는 서로 연결되지 않는다.
# u 를 통해서만 연결이 된다. - 그래서 u 가 절단점이 되지 않으려면,
# u 의 조상과 자손들이 전부 역방향 간선으로 연결되어 있을 때 뿐이다. - 여기서 u 가 root 인 경우 (최초 dfs 를 시작한 정점)
# u 의 자식 노드가 없거나, 하나인 경우는 u 는 절단점이 되지 않는다.
# root 는 둘 이상의 자식을 갖는 경우에만 절단점이 된다.
즉, 각 정점을 루트로 하는 서브트리에서 역방향 간선을 통해 갈 수 있는 정점의 최소 깊이(=최소 방문순서)를 반환하면,
위와 같은 상황을 확인 할 수 있다.
[3. 구현]
[4. 기타]
방향 그래프에서 어떤 edge 를 삭제 했을 때, 두 개의 컴포넌트로 쪼개지는 경우,
이 edge 를 bridge 라고 한다.
이 bridge 는 트리 간선 일 수 밖에 없다.
- 트리 간선: 트리에 속한 edge 를 구성하는 정점은 모두 연결 된다.
- 순방향/역방향 간선: 트리 간선들을 통해 연결 된다.
- 교차 간선: 역시 트리 간선들을 통해 연결 된다.
- 그래서, 트리 간선 만이 bridge 후보가 될 수 있다.
절단점을 구할 때 처럼, u 가 v 의 부모일 때,
- v 를 루트로 하는 서브트리에서
- 역방향 간선 중 자신의 부모로 가는 역방향 간선을 제외한 것 중
- 최소 발견 순서가 u 이후인 경우,
# u 보다 먼저 발견 된 정점으로 갈 수 없는 경우 - 트리 간선 u -> v 는 bridge 가 된다.
