[ Graph ] DFS Spanning Tree (DFS 스패닝 트리)

Spanning Tree

 

 

Spanning Tree는 그래프의 모든 정점이 연결되어 있는 트리로, $V$개의 정점이 $V-1$개의 간선으로 연결되어 있다. 트리의 성질에 의해 모든 정점이 연결되어 있으므로 사이클이 존재하지 않는다. 스패닝 트리를 활용한 개념으로 최소 스패닝 트리(Minimum Spanning Tree)가 존재한다. 이는 간선에 가중치가 존재하는 그래프에서 가중치의 합을 최소로 하면서 스패닝 트리를 구성하기 위해 선택해야 하는 간선들을 정하는 것으로, 간선들의 가중치를 정렬하여 가중치가 작은 간선부터 우선적으로 선택하는 Greedy한 알고리즘을 채택할 수 있다.

 

 

DFS를 이용해 일반적인 그래프를 트리의 형태로 표현하는 경우가 존재한다. 특정 시작 정점에서 시작하여 중복 방문을 허용하지 않는 DFS를 시행한다면 $V-1$개의 간선을 통해 탐색이 진행될 것이고, 지나온 간선들로 그래프를 새로 구성하면 이는 Tree가 될 것이다. 이를 이용하여 그래프를 Spanning Tree의 형태로 나타낼 수 있다.

 

 

---

 

Edge의 분류

 

 

 

DFS를 수행하는 과정에서 방문 여부, 정점 간 위치 관계에 따라 간선들을 분류할 수 있다. 간선들을 분류하는 이유는  일반 그래프의 트리화를 통해 SCC 알고리즘 혹은 그래프 내 사이클 판정 등 다양한 문제를 다항시간에 해결하기 위해서이다.( 일반적으로 $O(N)$, 일반 그래프를 트리의 성질을 활용할 수 있는 형태로 변형하는데 초점이 맞추어져 있다. ) 간선은 크게 4가지로 분류할 것이다. 트리 간선(Tree Edge), 순방향 간선(Forward Edge), 역방향 간선(Backward Edge), 교차 간선(Cross Edge)이다.

 

 

 

• 트리 간선 : DFS를 통해 구성한 스패닝 트리에 속하는 정점이다. 나머지 간선(순방향, ...)은 모두 트리 간선이 아니다.
• 순방향 간선 : DFS에서 사용하지 않은 간선 중, 선조에서 자손으로 연결되는 간선이다.
• 역방향 간선 : DFS에서 사용하지 않은 간선 중, 자손에서 선조로 연결되는 간선이다.
• 교차 간선 : DFS에서 사용하지 않은 간선 중, 순방향도, 역방향도 아닌 간선이다.

 

* 선조와 자손이란?

DFS를 통해 그래프에서 Tree Edge를 골라 트리를 구성했다고 하자.

그러면 Root Node를 중심으로 간선이 뻗쳐나가는 분기(Branch, 가지)가 존재할 것이다. (루트에서 시작한 경로)

 

 

이 때, 같은 분기 내에 존재하는 두 정점 $u$, $v$에 대해

$depth[u] < depth[v]$ 라면 $u$가 선조, $v$가 자손이다. ( 동일 분기에서만 정의되는 개념이다. )

 

$depth[u]$ : distance between root and u

 

 

 

다음 단방향 그래프에서 DFS spanning tree를 구성하는 코드를 구현해볼 것이다.

 

 

 

 

V = {1, 2, 3, 4, 5, 6, 7}

E = {(1, 2), (2, 3), (3, 1), (1, 4), (2, 4), (4, 3), (4, 5), (5, 6), (1, 7), (5, 7), (7, 6)}

 

 

 

 

#include <iostream>
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int MAX_N = 105;
 
int N, M;
vector<int> adj[MAX_N];
 
int main()
{
    N = 7, M = 11;
    adj[1].push_back(2);
    adj[2].push_back(3);
    adj[3].push_back(1);
    adj[1].push_back(4);
    adj[2].push_back(4);
    adj[4].push_back(3);
    adj[4].push_back(5);
    adj[5].push_back(6);
    adj[1].push_back(7);
    adj[5].push_back(7);
    adj[7].push_back(6);
    return 0;
}
 

 

 

이제 인접 리스트로 표현된 해당 그래프에서 dfs를 시행할 것이다. dfs를 시행할 때 필요한 변수들이 존재하는데 이는 다음과 같다.

 

 

 

 

 

• discovered : DFS를 하면서 정점들이 발견되는 순서를 기록한다. 예를 들어 3번 정점이 5번째로 방문되면 discovered[3] = 5이다. 본 글에서는 num이라는 배열이다.
• finished : 해당 정점에 대한 탐색이 끝났는지에 대한 bool 배열이다. 

 

 

 

 

 

DFS를 진행하면서 방문한 정점에서 num 배열에 번호를 새롭게 지정해주고(방문한 순서대로) 해당 정점에 대한 탐색이 끝나면(해당 정점과 인접한 정점들에 대한 방문이 모두 종료되면) finished의 값이 1이 된다. 따라서 탐색을 시작하는 정점에서 가장 늦게 finished의 값이 1이 될 것이다.

 

 

 

 

 

이제 정점 u에서 인접한 정점 v에 대해 간선 분류를 진행하는 것을 살펴보자.

1. num[v]가 0이라면 v를 아직 방문하지 않은 것이므로 (u, v) 간선은 트리 간선이다.
2. 그 외의 경우에는 (u, v)는 순방향 or 역방향 or 교차 간선이다.
3. 만약 num[u] < num[v]라면 인접한 정점이 더 나중에 방문되었다는 뜻이므로 이는 순방향 간선임을 알 수 있다.
4. 만약 3이 아니고 인접한 정점 v의 DFS가 아직 종료되지 않았다면(finished==0) v가 먼저 방문되었는데 DFS가 끝나지 않은 것이므로 (u, v)는 역방향 간선이다.
5. 3, 4가 아니면 (u, v)는 교차 간선이다.

 

 

 

 

3에 대해 자세히 살펴보자. DFS는 그래프에서 한 분기(가지)를 전부 탐색하고, 그 다음 분기를 탐색하고를 반복한다. 그런데 v는 인접한 정점인데, u보다 나중에 방문되었다는 것은 한 분기 내에서 u가 v보다 위에 있다(선조 노드)는 사실을 알 수 있다. 하지만 이러한 경우를 생각할 수 있다.

 

 

 

 

해당 그래프에서 하얀색 간선은 방문 번호(num)가 3인 정점에서 4인 정점으로 가므로 순방향 간선이라고 판단할 수 있다. 하지만 위 경우에 (3, 4)는 교차 간선이다. 이러한 경우는 어떻게 된 것일까? 사실 이러한 경우는 있을 수 없다. 왜냐하면 DFS(3)을 진행할 때, 4번 정점으로 갈 수 있었기 때문에 (3, 4)가 트리 간선으로 선택되어 그래프는 다음과 같았을 것이기 때문이다.

 

 

 

 

위 설명들을 코드로 구현하면 아래와 같다.

 

 

int num[MAX_N], cnt;
int finished[MAX_N];
 
void dfs(int x)
{
    num[x] = ++cnt;
    for(int nxt : adj[x]){
        if(num[nxt]==0){
            printf("(%d, %d)는 트리 간선\n", x, nxt);
            dfs(nxt);
        }
        else{
            if(num[x] < num[nxt]){
                printf("(%d, %d)는 순방향 간선\n", x, nxt);
            }
            else if(!finished[nxt]){
                printf("(%d, %d)는 역방향 간선\n", x, nxt);
            }
            else{
                printf("(%d, %d)는 교차 간선\n", x, nxt);
            }
        }
    }
    finished[x] = 1;
}

 

 

 

출력 결과