[알고리즘] 깊이 우선 탐색(DFS, Depth-First Search)

Goal

깊이 우선 탐색(DFS, Depth-First Search)의 개념
깊이 우선 탐색(DFS, Depth-First Search)의 특징
깊이 우선 탐색(DFS, Depth-First Search)의 구현

 

그래프 탐색이란?

 

• 그래프 탐색은 그래프의 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것입니다. 그래프의 탐색은 매우 중요합니다. 대부분의 문제들이 탐색하는 것 만으로 해결되기 때문입니다. 

• 예를 들어 다리 문제에서 A 도시와 B 도시가 연결돼있는지 확인하는 것은 단지 탐색을 하였을 때, A, B 도시가 한 연결 요소 안에 존재하는지만 판단하면 됩니다.

 

깊이 우선 탐색(DFS, Depth-First Search)

 

• 깊이 우선 탐색은 미로를 탐색하는 방법과 비슷하다. 한 방향으로 막힐 때까지 이동하다가 더 이상 이동할 수없게 되면 가장 가까운 갈림길로 돌아와 다시 막힐 때까지 한 방향으로 이동하는 것을 반복하는 것이다.

 

 

깊이 우선 탐색 특징

 

1. 단순 검색 속도는 너비 우선 탐색(BFS)에 비해서 느리다.
2. 재귀 호출 형태를 가지고 있다.
3. 방문 여부를 반드시 검사해야 한다.

 

깊이 우선 탐색의 과정

 

 

깊이 우선 탐색의 구현

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Graph {
public:
	int N; // 정점의 개수
	vector<vector<int>> adj; // 인접 리스트
	vector<bool> visited; // 방문 여부를 저장하는 배열

	// 생성자
	Graph() : N(0) {}
	Graph(int n) : N(n) {
		adj.resize(N);
		visited.resize(N);
	}

	// 간선 추가 함수
	void addEdge(int u, int v) {
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	// 모든 리스트의 인접한 정점 번호 정렬
	void sortList() {
		for (int i = 0; i < N; i++)
			sort(adj[i].begin(), adj[i].end());
	}

	// 깊이 우선 탐색
	void dfs() {
		fill(visited.begin(), visited.end(), false);
		dfs(0); //오버로딩
	}

private:
	void dfs(int curr) {
		visited[curr] = true;
		cout << "node " << curr << " visited" << endl;
		for (int next : adj[curr])
			if (!visited[next]) dfs(next);
	}
};

int main() {
	Graph G(9);
	G.addEdge(0, 1);
	G.addEdge(0, 2);
	G.addEdge(1, 3);
	G.addEdge(1, 5);
	G.addEdge(3, 4);
	G.addEdge(4, 5);
	G.addEdge(2, 6);
	G.addEdge(2, 8);
	G.addEdge(6, 7);
	G.addEdge(6, 8);
	G.sortList();
	G.dfs();
}