[Algorithm] 그래프 알고리즘(3) - DFS(2), Biconnected Graph

🤔 그래프 알고리즘

그래프는 알고리즘 기법이라기 보다는 여러가지 효율적인 알고리즘을 적용하기 위한 자료구조입니다.

 

그래프는 정점과 간선으로 구성된 자료구조를 뜻합니다.

 

이번 시간은 저번 포스팅에 이어 DFS에 대해 조금 더 알아보고 Biconnected Graph에서 Articulation Point를 찾는 방법에 대해 집중적으로 알아보도록 하겠습니다.

 

 

 

👉 이전 포스팅

2022.10.04 - [Computer Science/Algorithm] - [Algorithm] 그래프 알고리즘(1) - 그래프의 기본 용어

[Algorithm] 그래프 알고리즘(1) - 그래프의 기본 용어

 

2022.10.08 - [Computer Science/Algorithm] - [Algorithm] 그래프 알고리즘(2) - DFS(깊이우선탐색)(1)

[Algorithm] 그래프 알고리즘(2) - DFS(깊이우선탐색)(1)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 Connected graph G에 대한 문제

 

✍️ DFS tree의 성질

 

Problem 1 : G의 모든 articulation point 찾기.

Problem 2 : Problem 1을 이용하여 G의 bioconnected component찾기

 

 

 

해당 문제를 해결하기 위해 DFS tree의 성질을 이용하기 때문에  Articulation Point와 관련된 DFS tree의 성질을 먼저 알아보도록 하겠습니다.

 

 

 

 

 

 

✍️ Lemma 1 

DFS tree 의 root node 의 child node가 두 개 이상이라면 root node는 articulation point이며, 역도 성립한다.

 

 

 

 

 

증명 1

 

이때 만약 $(r, a)와 (r, b)$를 포함하는 cycle이 존재하면 둘 중 하나는 back edge가 되어야 하므로 모순입니다.

 

 

 

 

 

 

 

 

증명 2

 

 

 

 

 

 

 

✍️ Lemma 2

DFS tree에서 (i) s 가 v의 child node이고 (ii) s의 descendant(s 포함)과 v의 proper ancestor(v 미포함)를 연결하는 back edge가 존재하지 않는 조건을 만족하는 두 non-root node v, s가 존재할 경우 v는 articulation point이다.

 

 

 

 

 

증명 1

 

만약 위 조건을 해당하는 node s가 있다고 하겠습니다.

 

그러면 v를 제거하면 s의 subtree상의 어떤 node도 해당 node 에서 v의 proper ancestor로 가는 path가 존재하지 않게 됩니다.

 

그러므로 v는 articulation point 입니다.

 

해당 path가 존재하려면 s에서 v의 proper ancestor로 가는 back edge가 필요합니다.

 

그러므로 v는 articulation point 입니다.

 

 

 

 

 

증명 2

 

 

 

 

 

✍️ Lemma 3

DFS tree 의 leaf node는 articulation point 가 아니다.

 

 

 

 

 

증명

Leaf node는 child node가 없기 때문에 node를 제거해도 나머지는 여전히 tree edge 만으로 tree 가 되며, tree의 정의에 의해 해당 그래프는 여전히 connected 합니다.

 

 

 

 

예제 문제를 풀며 articulation point와 biconnected component를 찾는 방법에 대해 이해해보겠습니다.

 

 

 

 

 

🔎 Problem 1 

Connected Graph G가 주어졌을 때 G의 모든 articulation point 찾기

 

 

✍️ Solution 1.

Vertex를 하나씩 제거하면서 DFS를 이용하여 connectivity check를 진행합니다.

 

Vertex v를 제거한 뒤 G가 disconnected이면 v는 articulation point입니다.

 

이를 수도 코드로 나타내면 아래와 같습니다.

 

 

for each vetex v:

	remove v;
    test resulting graph for connectivity;
    put back v;

 

 

해당 코드의 시간복잡도는 $O(n(n + m))$입니다.

 

 

 

 

 

 

✍️ Solution 2.

 

Connected Graph G가 주어졌을 때 오른쪽과 같은 Tree 형태의 그림을 그릴 수 있습니다.

 

결론부터 말하자면 위와 같은 그림이 주어졌을 때 Articulation Point는 Node 2와 Node 6입니다.

 

이는 DFS Tree 의 성질을 이용하여 Articulation Point를 찾을 수 있습니다.

 

 

 

 

 

이유

Node 2 : Lemma1에 의해 Child node가 두 개 이므로 articulation point 입니다.

 

Node 6: Lemma2에 의해 Node 6의 child Node인 Node 7의 descendant로 부터 Node 6의 proper ancestor로의 back edge가 없으므로 articulation point 입니다.

 

 

 

알고리즘적인 차원에서 접근하기

위의 Tree그래프를 DFS tree의 형태로 나타내겠습니다.

 

정점을 하나씩 제거하면서 DFS를 이용해 연결 되어있는지를 체크합니다.

 

DFS tree의 각 node v에 대해, v의 어떤 descendant u (u = v일 수 있음)와 incident한 back edge (u, w)가 존재한다면

 

$$low(v) = min(pre(v), pre(w))$$

 

로 정의하겠습니다.

 

 

KEY LEMMA Non Root Node v가 low(u) ≥ pre(v)를 만족하는 child node u를 가지고 있다면, v는 articulation point 이며, 역도 성립한다. KEY LEMMA 증명 low(u) ≥ pre(v)라 하자.(u는 v의 child node) v의 proper ancestor 는 v보다 pre-order number가 항상 작거나 같으므로 child node u에서 v의 proper ancestor로의 backedge가 존재하지 않는다. 이는 " Lemma 2 " 에 의해 v는 articulation point 이다. 아래의 그림에서 Node 6의 경우 child node 7의 low는 8이므로 low(7) ≥ pre(6)을 만족합니다. 역도 성립함을 증명

 

 

 

 

 

 

 

 

위의 그림을 바탕으로 DFS tree를 이용하여 articulation point를 찾는 방법을 알아보도록 하겠습니다.

 

가장 중요한 생각의 흐름은 "DFS 를 한 번 수행하면서 모든 articulation point들을 return한다"입니다.

 

 

 

해당 알고리즘은 아래의 순서대로 진행됩니다.

 

 

1. Root node를 먼저 탐색하는데 child가 두 개 이상 있는지 확인만 하면 되므로 쉽게 판별 가능합니다.

2. Non root node의 경우 두 가지를 고려해야합니다.     i) DFS 에서 low값을 계속 update해 나가며, low(v)값은 postvisit(v) 시점에서 완전히 결정됩니다.     ii) 따라서 vertex v의 child node u에 대한 explore가 끝난 뒤, pre(v)와 low(u)를 비교하여, low(u) ≥ pre(v)이면          v는 articulation point입니다.

 

DFS 도중 low(v)는 어떻게 update 하나요?

 

초기값은 pre(v) ← previsit(v) 때 결정됩니다.

 

Back edge(v, u)가 있다면 low(v) = min (low(v), pre(u)) 로 update 됩니다.

 

v의 child u에 대한 explore가 끝나면 low(v) = min (low(v), low(u)) 로 update합니다.

 

 

 

 

이를 수도코드로 나타내면 아래와 같습니다.

 

 

 

예제를 통해 수도코드를 실행하면 아래와 같습니다.

 

 

 

 

 

 

 

 

 

 

 

✍️ 시간 복잡도

DFS를 이용하여 articulation point를 찾는 알고리즘의 시간복잡도는

 

1) DFS를 통해 low, pre, post값을 찾으며 tree를 구성하는 데에 $O(n+m)$

2) 모든 정점을 탐색하며 low와 pre값을 비교하는 데에 $O(n)$

 

$$O(n + m)$$

 

의 시간복잡도를 가지게 됩니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 Problem 2

Problem 1을 이용하여 G의 biconnected component 찾기

 

 

여기서 Graph는 connected 라 가정하며, 아닌 경우 graph의 각 connected component에 대해 biconnected component를 c찾습니다.

 

Biconnected component는 edge를 partitioning하므로 biconnected component를 하나 return 할 때마다 해당 component에 속해있는 edge들을 return 합니다.

 

이 또한 DFS를 이용합니다.

 

DFS를 하면서 거쳐가는 edge를 저장하는 stack을 이용하여 biconnected component를 찾습니다.

 

Vertex v를 explore하면서 edge(v, u)를 check 할 때마다 해당 edge를 stack에 push합니다.

 

만약 v를 explore 하면서 v의 child node u에 의해 v가 articulation point임이 밝혀지거나(low(u) ≥ pre(v)) root node에 대한 explore가 끝나면 edge(u, v)가 나올 때까지 stack 상의 모든 edge들을 pop하며, 이것이 하나의 biconnected component가 됩니다.

 

Articulation point를 찾을 때와는 달리 root node case를 따로 처리해줄 필요는 없습니다.

 

 

 

이를 수도코드로 나타내면 아래와 같습니다.

 

 

 

해당 수도코드를 분석해보겠습니다.

 

임의로 지정한 v부터 시작하여 DFS를 진행합니다.

 

articulation point를 찾는 알고리즘과 동일한 방식으로 진행되지만 stack을 생성하여 각 vertex의 값을 stack에 저장합니다.

 

articulation을 찾게 되면 low(u)와 pre(v)를 비교하여 stack에 저장된 값들을 pop해줍니다.

 

그때 pop되어져 나온 값들의 집합이 biconnected component입니다.

 

 

 

 

 

 

 

✍️ 시간복잡도

1) DFS를 진행하는 데에 $O(n + m)$

2) push와 pop을 각 m번 진행하여 $O(m)$

 

해당 알고리즘의 시간 복잡도는

 

$$O(n + m)$$

 

입니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

다음 포스팅에서는Directed Graph에서 DFS를 알아보도록 하겠습니다.