DFS 스패닝 트리
- DFS 스패닝 트리는 그래프에서 DFS를 어느 정점 u에 대해 실행하였을 때, u를 루트로 하는 트리
그래프의 사이클
-
정점 u에서 시작하여 자기 자신으로 돌아오는 경로가 있는 것을 Cyclic이라 하며, 그 경로를 Cycle이라 한다.
- Cycle이 존재할 경우 그 그래프는 Cyclic Graph가 된다.
<방향 그래프에서 사이클의 존재 여부 확인하기>
-
모든 정점에 대해 DFS를 돌려 자기 자신으로 돌아오는 경로가 있다면 사이클이 존재하는 것이다.
- 다만, 이 경우 시간복잡도가 O(V(V + E))로 높게 나온다.
-
두번째 방법은 역방향 간선을 찾으면서 DFS를 하는 것이다.
- 이 경우 일반적인 DFS의 시간복잡도인 O(V + E)가 나온다.
vector<vector<int>> adj;
vector<bool> vis, finished;
bool hasCycle;
void DFS(int node)
{
vis[node] = true;
for (int i = 0; i < adj[node].size(); ++i) {
int next = adj[node][i];
if (!vis[next])
DFS(next);
else if (finished[next] == false) { // next가 이미 방문했지만, 종료되지 않는 정점이면
hasCycle = true;
}
}
finished[node] = true;
}
<무방향 그래프에서 사이클의 존재 여부 확인하기>
-
무방향 그래프에서는 간선의 방향이 정해져있지 않다.
- 따라서 정점의 방문 순서를 비교함으로써 사이클을 판단할 수 있다.
-
부모를 제외한 정점들 중 이미 방문했고, 방문순서가 더 빠른 정점이 존재하게 되면 사이클이 있다고 판단할 수 있다.
void go(int u, int p) {
for (int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
if (p != v) {
if (d[v] == 0) {
d[v] = d[u] + 1;
go(v, u);
}
else if (d[u] > d[v]) {
printf("벡에지입니다");
}
}
}
}
<사이클 내의 정점들을 표시>
-
이를 위해
parents라는 부모 배열을 만들어 정점의 부모를 저장.- 예를 들어
parents[node]는node정점의 부모를 담는다.
- 예를 들어
-
부모를 찾다가 부모와 사이클의 시작점(역방향 간선이 가리키는 정점)에 도달하게 되면 멈춘다.
-
사이클에 속한 정점들은
isCycle배열에 표시해준다.
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> adj;
vector<int> parent;
vector<bool> vis, finished, isCycle;
bool isGraphCyclic;
int countCyclicVertices;
void denoteCycle(int node, int next)
{
isCycle[node] = true;
countCyclicVertices++;
if (node == next)
return;
denoteCycle(parent[node], next);
}
void DFS(int node)
{
vis[node] = true;
for (int i = 0; i < adj[node].size(); ++i) {
int next = adj[node][i];
if (!vis[next]) {
parent[next] = node;
DFS(next);
}
else if (finished[next] == false) {
isGraphCyclic = true; // 그래프가 사이클을 갖는지 체크해준다.
denoteCycle(node, next); // 사이클에 포함된 정점들을 표시해준다.
}
}
finished[node] = true;
}
그래프 간선의 종류
-
간선은 트리 간선, 역행 간선, 순행 간선, 교차 간선 총 4개로 분류된다.
- 역행 간선과 순행 간선은 개인마다 역방향, 순방향 간선으로 부르기도 한다.
-
그래프의 간선은 DFS를 어떤 정점에서 시작하는지, 어떤 순서로 방문할것인지에 따라 다른 트리가 생성되고, 따라서 간선의 구분이 달라질 수 있다.
-
트리 간선(Tree edge)
-
정점 v가 간선 (u, v)를 통해 처음 발견되었다면, (u, v)는 트리간선이다.
-
간단하게는, 스패닝 트리에 포함된 간선을 말한다.
-
-
역행 간선(Back edge)
-
스패닝 트리의 자손에서 선조로 연결되는 간선을 말한다.
-
방향 그래프에서의 자기 순환 간선들은 역행 간선으로 간주한다.
-
-
순행 간선(Forward edge)
- 트리간선이 아닌 선조에서 자손으로 연결되는 간선을 말한다.
-
교차 간선(Cross edge)
-
위 세 분류를 제외한 나머지 간선이다.
-
선조와 자손 관계가 아닌(위계 관계가 없는) 정점들 간에 연결된 간선들을 말한다.
-
하나의 정점이 다른 정점의 조상이 아니어야 한다.
-
서로 다른 스패닝트리에 있는 두 정점 사이에 있을수도 있다.
-
🛑 무방향 그래프의 DFS 스패닝 트리에서 모든 간선은 트리 간선이거나 역행 간선이다.
간선을 구분하는 DFS 코드
-
(u, v)가 순방향 간선이라면 v는 u의 자손이어야 하고, 따라서 v가 u보다 더 늦게 발견되어야 한다.
- 또한, (u, v)가 트리 간선이 아니어야 한다.
-
(u, v)가 역방향 간선이라면, v는 u의 선조이어야 한다. 따라서 v가 u보다 먼저 발견되어야 한다.
-
(u, v)가 교차 간선이라면, DFS(v)가 종료된 후 DFS(u)가 호출되어야 한다. 따라서 v는 u보다 일찍 발견되어야 한다.
vector<vector<int>> adj;
vector<int> discovered, finished;
int counter;
void DFS(int node)
{
discovered[node] = counter++;
for (int i = 0; i < adj[node].size(); ++i) {
int next = adj[node][i];
cout << "(" << node << "," << next << ") : ";
// 아직 방문하지 않았다면
if (discovered[next] == -1) {
cout << "tree edge" << endl;
DFS(next);
}
// next를 방문했지만 순서가 node보다 늦다면
else if (discovered[node] < discovered[next])
cout << "forward edge" << endl;
// next를 방문했지만 순서가 node보다 빠르다면
// next가 종료하지 않았다면 => next는 node의 선조가 됨.
else if (finished[next] == 0)
cout << "back edge" << endl;
// 이 외에는 모두 교차 간선
else
cout << "cross edge" << endl;
}
finished[node] = 1;
}
-
discovered라는 배열에counter변수를 이용하여 발견 순서를 저장한다. -
이 배열은 정점이 방문되었는지 여부도 한번에 알려준다. 기존 DFS에서의 visited 배열과 유사하다.
-
이 배열을 통해 선조와 자손, 혹은 아무것도 아닌 관계를 밝혀낼 수 있다.
-
또한, 정점 u에서의 인접한 모든 정점으로의 DFS가 종료되었는지를 저장하는 배열
finished를 이용한다.
