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

🤔그래프 알고리즘

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

 

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

 

이번 포스팅에서는 DFS에 대해 알아보도록 하겠습니다.

 

 

 

👉이전 포스팅

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 Reachability

Reachability는 DFS알고리즘을 이해하기 위한 기반이 되는 알고리즘이므로 DFS를 공부하기전 알아보도록 하겠습니다. 

 

Undirected Graph G의 두 정점 u,v 에 대해 정점 u에서 정점 v로의 path가 존재한다고 할 떄, v는 u로부터 reachable이라고 합니다.

 

Graph G의 정점 v가 주어졌을 떄 어떻게 v에서 reachable한 모든 정점을 찾을 수 있는 지에 대한 알고리즘에 대해 알아보겠습니다.

 

해당 알고리즘을 수도코드로 나타내면 아래와 같습니다.

 

 

 

 

위의 수도코드가 올바르게 동작하는지 귀류법을 통해 증명하겠습니다

 

 

 

.

 

해당 알고리즘의 실행 과정은 아래와 같습니다.

 

 

 

해당 그래프의 모든 정점에는 preorder number과 postorder number 값을 가지고 있도록 합니다.

 

이후 counter 변수를 1로 초기화하여 선언한 후 previsit(v)를 할 때마다 preorder number, postvist(v)를 할 때마다 postorder(v)의 값을 counter로 설정한 다음 counter의 값을 1씩 증가시킵니다.

 

이를 그림을 나타내면 아래와 같습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 DFS(Depth First Search)

 

✍️ DFS의 정의

 

 

 

 

위의 그림과 같이 DFS tree의 root node는 처음 explore 를 시작하는 정점입니다.

 

explore(G, v) 수행 도중 explore(G, u)를 호출할 경우, u의 parent node는 v가 됩니다.

 

Graph G의 edge들 중 DFS tree에 있는 edge를 tree edge, DFS tree에 없는 edge를 back edge라고 하며 정자는 보통 실선, 후자는 점선으로 나타냅니다.

 

 

 

 

 

 

✍️ DFS알고리즘의 수행 시간

위에서 언급한 explore procedure을 이용하여 그래프 사엥 모든 정점을 한 번 씩 방문하는 방법은 아래와 같습니다.

 

1. 그래프의 모든 정점에 visited(v)를 false로 설정합니다.

2. 방문하지 않은 모든 정점에 대해 explore(v)를 진행합니다.

 

 

모든 정점에 대해 visted(v)를 초기화해야하므로 $O(n)$의 시간이 걸립니다.

 

모든 정점에 대해 explore을 해야 하는데 이때 같은 edge를 최대 두 번 접근할 수 있으므로 $O(2m)$의 시간이 걸립니다.

 

이는 $O(m)$에 dominate되기 때문에 총 

 

$$O(n+m)$$

 

시간이 소모됩니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 Connected Components

 

 

아래의 (a)와 같은 그래프를 DFS tree로 나타내면 (b)와 같습니다.

 

explore과정을 DFS 알고리즘의 경우 전체 과정을 DFS tree 들의 서로소 합집합, 즉 forest로 표현이 가능합니다.

 

 

 

 

DFS forest를 이루는 각각의 DFS tree는 그래프에서 Connected Component에 대응합니다.

 

 

 

 

 

 

 

✍️ Connected Component의 정의

 

그래프 G의 Connected Component인 G'은 G의 Maximal Connected Subgraph로 정의됩니다.

 

이때 Maximal은 최대는 아니지만 더 이상 추가할 수 없는 상태를 말합니다.

 

즉, 이의 그림에서 정점 A에서 explore(v)를 진행했을 때 { A, B, E, I, J }가 각각의 node로 존재하는 tree를 구성할 수 있는데 이 상태를 Maximal이라고 할 수 있습니다.

 

그러므로 DFS forest를 이루는 각각의 DFS tree는 그래프의 connected compnent에 대응합니다.

 

DFS알고리즘 중 한 번 explore를 호출할 때마다 새로운 connected componet에 속한 vetex들을 모두 방문합니다.

 

이에 대한 증명은 아래와 같습니다.

 

 

 

 

 

 

 

Articulation Point에 대한 자세한 설명이 나와있는 블로그는 아래의 참조에 링크를 걸어두었습니다.

 

 

 

 

 

 

 

 

 

 

 

🔎 Articulation Point(Cut Vertex)

 

 

✍️ Articulation Point의 정의

그래프 G가 connected undirected graph라고 하겠습니다.

 

이때 G의 어떤 정점 v와 v와 연결된 모든 edge들을 제거할 경우 G가 disconnected된다면 v를 G의 articulation point라고 합니다.

 

아래의 그림에서 정점 2, 6은 Articulation Point입니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 Biconnected Components

 

✍️ Biconnected Components의 정의

그래프 G가 biconnected(이중연결되어있다) 라는 뜻은 G는 connected 그래프이며 Articulation point를 가지고 있지 않다는 뜻입니다.

 

Biconnected Component G' of G는 그래프 G의 maximal biconnected subgraph라고 정의할 수 있습니다.

 

즉, 그래프 G의 biconnected compnent로 G의 edge들을 partitioning 할 수 있으며 서로 다른 두 biconnected component는 최대 한 개의 정점(articulation)을 공유합니다

 

이를 그림으로 살펴보면 아래와 같습니다.

 

 

 

 

 

$G'_1, G'_2, G'_3$은 각각 biconnected component로 $G'_1과 G'_2$가 Vertex2를 공유하고 $G'_2와 G'_3$가 Vertex6을 공유합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

✍️ Key Property

같은 bioconnected component에 속해있는 edge e와 e'이 있을 때

    i) e = e'이거나

    ii) e와 e'을 모두 포함하는 cycle이 같은 component 안에 속해 있다. (역도 성립)

 

 

 

 

 

 

 

 

 

👉 증명

 

 

 

 

 

 

 

 

 

 

다음 포스팅에 이어 작성을 DFS 알고리즘에 대한 정리를 마무리하겠습니다.

 

 

 

 

🔎 Reference

 

https://www.crocus.co.kr/1164

단절점(Articulation Point), 단절선(Articulation Bridge)