[알고리즘] Graph (2) - Depth-first search(DFS)

[2. Depth-first search 깊이우선탐색]

1. 깊이우선탐색 - 무방향그래프

  → 그래프의 탐색을 위해 Recursive call을 활용한다.

  → 가능한 연결되어 있는 노드들을 방문하며

  → 방문 순서는 특별한 지시가 없을 경우 오름차순을 따른다.

  → 각 vertex v에서 탐색을 시작할 경우

  → v는 이미 방문한 것으로 표시(visit[v]=1)

  → v에 연결된 vertex w중에서 아직 방문하지 않은(visit[w]=0인) vertex 방문

  → 더이상 방문할 vertex가 없으면 직전 노드로 return

Ex)

2. Spanning Tree (DFS Tree)

  → 주어진 그래프에서 방문되는 n-1개의 간선들로 모든 개체를 연결한 서브그래프

  → DFS tree에서 root node에 다른 노드보다 더 가깝게 위치한다고 해서, graph에서도 다른 노드에 비해 더 가까운 것은 아님

  → graph의 특성상 하나 이상의 DFS tree가 존재할 수 있음

 

3. Previsit과 Postvisit

  → 그래프 내의 개체를 어떠한 방식에 따라 방문할 때 표시

  → Previsit : 어느 개체에 처음 방문한 경우

  → Postvisit : 더 이상 연결된 다른 개체에 previsit으로 방문할 수 없어 그 개체를 떠나는 경우

  → 각 개체들의 previsit과 postvisit의 집합은 서로 포함되거나 아예 만나지 않는다.

● 구현

(개체 수, 간선 수 그리고 시작할 노드의 수를 입력한 후 개체의 연결관계를 입력하면 노드를 방문하는 순서를 출력함)

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> edge[1001];
bool visit[1001] = { false };

void dfs(int v) {
	if (visit[v] == true)
		return;
	printf("%d ", v);
	visit[v] = true;
	for (int i = 0; i < edge[v].size(); i++)
		dfs(edge[v][i]);
}

void main() {
	int v, e, s;		//개체 수, 간선 수, 시작할 노드(숫자) 입력
	scanf_s("%d %d %d", &v, &e, &s);
	int l, m;
	for (int i = 0; i < e; i++) {
		scanf_s("%d %d", &l, &m);	//간선이 연결하는 두 개체의 번호
		edge[l].push_back(m);
		edge[m].push_back(l);
	}
	for (int i = 1; i <= v; i++) {
		sort(edge[i].begin(), edge[i].end());
	}

	for (int i = s; i <= v; i++)
		if (visit[i] == false)
			dfs(i);
	printf("\n");
}

 

● 성능

  → 그래프에 존재하는 개체를 모두 방문해야 하므로 O(n)

  → 그래프에 존재하는 간선을 고려해야 하므로 O(m)

  → m은 n또는 n²

  → 따라서 O(n+m) (최대 O(n²))

 

4. 방향그래프의 깊이우선탐색

  → 정해진 방향대로 움직이며

  → 더이상 방문할 수 있는 개체가 없을 경우 역방향으로 돌아온다.

  → 방향 그래프 DFS tree의 네 가지 edge

       → Tree edge : DFS tree의 edge

       → Forward edge : 자녀노드가 아닌 후손노드로의 edge

       → Backward edge : 조상노드로의 edge

       → Cross node : 조상노드나 후손노드가 아닌 노드로의 edge

5. Directly Acyclic Graph, DAG 비순환그래프

  → cycle이 존재하지 않는 방향그래프

  → Source : 밖으로 나가는 방향의 간선만을 가지는 개체

  → Sink : 안으로 들어오는 방향의 간선만을 가지는 개체

  → 모든 dag는 적어도 한 개의 sink와 적어도 한 개의 source를 가진다.

  → Dag에서는 모든 간선들은 더 낮은 post를 가진 노드로 연결된다.  

  → DFS Tree에서 backdege가 나타날 경우, 그 방향그래프는 cycle을 가진다(Dag이 아니다).