dfs - 절단점

[1. 개요]

DFS 를 응용해서 해결 할 수 있는 문제 중 하나로,

어떤 무방향 그래프에서 절단점이란

• 이 점을 제거함으로 인해 edge 가 제거되고
• 이로 인해, 컴포넌트가 두개 이상으로 나뉘어지는 정점을 말한다.

최초 그래프가 하나의 컴포넌트로 이루어 졌는데,

어떤 정점을 제거하여, 그래프가 두개 이상의 컴포넌트로 나뉘어지면

전체 그래프는 연결되어 있지 않을 수 있다.

 

이러한 절단점을 찾기 위한 가장 단순한 방법은 아래와 같은데

• 모든 정점에 대해서, 정점을 제거하고
• dfsAll() 을 수행해서 컴포넌트 개수의 변화가 있는지 확인한다.

탐색 과정에서 얻는 정보를 이용하면, 한번의 dfs 로 모든 절단점을 찾아 낼 수 있다.

• 참조) https://testkernelv2.tistory.com/441

---

[2. 알고리즘]

• 임의의 정점에서 dfs 를 수행하는데,
• 무방향 그래프에서는 교차 간선이 존재하지 않으므로
• 어떤 정점 u 에 연결된 정점들은 모두 u 의 조상이거나 자손이 된다.
  # 무방향 그래프이지만, 방문 순서를 통해, 이를 판별 할 수 있다.
• 여기서 u 의 자손들을 루트로 하는 서브 트리는 서로 연결되지 않는다.
  # u 를 통해서만 연결이 된다.
• 그래서 u 가 절단점이 되지 않으려면,
  # u 의 조상과 자손들이 전부 역방향 간선으로 연결되어 있을 때 뿐이다.
• 여기서 u 가 root 인 경우 (최초 dfs 를 시작한 정점)
  # u 의 자식 노드가 없거나, 하나인 경우는 u 는 절단점이 되지 않는다.
  # root 는 둘 이상의 자식을 갖는 경우에만 절단점이 된다.

 

즉, 각 정점을 루트로 하는 서브트리에서 역방향 간선을 통해 갈 수 있는 정점의 최소 깊이(=최소 방문순서)를 반환하면,

위와 같은 상황을 확인 할 수 있다.

---

[3. 구현]

	#include <iostream>
	#include <vector>
	#include <algorithm>
	// 연결 리스트로 그래프 구현
	std::vector<std::vector<int>> adj;
	// discovered: 각 노드별 방문 순서 저장
	std::vector<int> discovered;
	// 각 노드 별, 절단점 여부를 저장
	std::vector<bool> isCutVertex;
	int dfs(const int u, const bool isRoot, int &counter)
	{
	// 방문한 자식 노드 개수
	// root 인 경우, 절단점 판별을 위해 필요함.
	int children = 0;
	// 방문 순서 기록
	discovered[u] = counter++;
	int ret = discovered[u];
	// 인접한 정점에 대해서
	for (const int v : adj[u]) {
	if (discovered[v] == -1) {
	// 방문한 적이 없으로 방문한다.
	children++;
	int subtree = dfs(v, false, counter);
	// u : root 가 아닌 경우
	// 자식 노드를 루트로 하는 서브트리에서
	// u 보다 먼저 발견 된 정점으로 갈 수 없는 경우,
	// u 는 절단점이 된다.
	if (!isRoot && subtree >= discovered[u]) {
	isCutVertex[u] = true;
	ret = std::min(ret, subtree);
	}
	}
	else {
	// v 가 이미 방문된 경우
	ret = std::min(ret, discovered[v]);
	}
	}
	if (isRoot) {
	// root 인 경우
	isCutVertex[u] = (children >= 2);
	}
	return ret;
	}

view raw cut_vertex.cpp hosted with ❤ by GitHub

---

[4. 기타]

방향 그래프에서 어떤 edge 를 삭제 했을 때, 두 개의 컴포넌트로 쪼개지는 경우,

이 edge 를 bridge 라고 한다.

 

이 bridge 는 트리 간선 일 수 밖에 없다.

• 트리 간선: 트리에 속한 edge 를 구성하는 정점은 모두 연결 된다. 
• 순방향/역방향 간선: 트리 간선들을 통해 연결 된다.
• 교차 간선: 역시 트리 간선들을 통해 연결 된다.
• 그래서, 트리 간선 만이 bridge 후보가 될 수 있다.

절단점을 구할 때 처럼, u 가 v 의 부모일 때,

• v 를 루트로 하는 서브트리에서
• 역방향 간선 중 자신의 부모로 가는 역방향 간선을 제외한 것 중
• 최소 발견 순서가 u 이후인 경우,
  # u 보다 먼저 발견 된 정점으로 갈 수 없는 경우
• 트리 간선 u -> v 는 bridge 가 된다.