[C/C++] DFS, BFS

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

(1) 깊이 우선 탐색이란? : 여러 개의 노드(node)가 간선(edge)으로 연결되어 있는 그래프(graph)에서 탐색을 진행하고자 할 때, 처음 탐색을 시작할 노드와 가장 가까운 노드를 방문한 후, 새로 방문한 노드와 가장 가까운 노드로 깊이 들어가는 방식이다. 한 노드에서 이동할 수 있는 여러 가지 노드를 한번씩 방문하는 것이 아니라, 가장 가까운 노드가 있다면 그 노드로 이동한 후 또 그 노드와 가장 가까운 노드로 또 이동하는 과정을 반복하는 것이다. 한 번 방문한 노드는 방문 표시를 하며 후에 거쳐갈 수는 있어도 다시 방문하지는 않는다. 탐색 시작 위치와 방향이 정해지지 않았다면 일반적으로 오름차순으로 이동하면 된다.

(2) 기본 원리 : 자료구조 중 스택(stack)을 사용한다. 스택이란 선입후출(FILO)방식으로 데이터를 관리하며 데이터의 입력을 push, 삭제를 pop으로 표현한다. 한 그래프의 노드간 연결관계를 인접 행렬(Adjacency matrix)와 인접 리스트(Adjacency list)로 표현할 수 있는데, 프로그래밍에서는 리스트를 사용하는 것이 훨씬 효율적이다. 또한 스택 구조를 사용하기 때문에 재귀함수를 활용하는 것이 구현하기에 편리하다.

(3) 시간 복잡도 : 노드의 개수가 N개, 그리고 하나의 노드에 연결된 노드의 개수가 M개일 때, 인접 리스트를 활용한다면  O(N+M)이고 인접 행렬을 활용하면 O(N²)이다.

(4) 구현 - 재귀함수

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> edge[1000];
bool visited[1000];

void dfs(int vertex) {
	if (visited[vertex])
		return;
	visited[vertex] = true;
	cout << vertex << " ";

	for (int i = 0; i < edge[vertex].size(); i++)
		dfs(edge[vertex][i]);
}

int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int x, y;
		cin >> x >> y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}

	for (int i = 0; i < N; i++)
		sort(edge[i].begin(), edge[i].end());

	for (int i = 1; i <= N; i++)
		if (!visited[i])
			dfs(i);
}

 

 

2. BFS(Breadth First Search, 너비 우선 탐색)

(1) 너비 우선 탐색이란? : 그래프에서 탐색을 진행하고자 할 때, 처음 탐색을 시작할 노드와 직접 연결된 모든 노드를 순서대로 방문한 후 다음 노드로 넘어가는 방식이다.

(2) 기본 원리 : 자료구조 중 우선순위 큐(priority queue)를 사용한다. 우선순위 큐는 선입선출 방식으로 데이터를 관리하며 데이터의 입력을 push, 삭제를 pop으로 표현한다.

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

vector<int> edge[1000];
bool visited[1000];

void bfs(int vertex) {
	queue<int> q;
	int u;

	q.push(vertex);
	visited[vertex] = 1;
	while (!q.empty()) {
		u = q.front();
		q.pop();
		cout << u << " ";
		for (int i = 0; i < edge[u].size(); i++)
			if (visited[edge[u][i]] == 0) {
				visited[edge[u][i]] = 1;
				q.push(edge[u][i]);
			}
	}
}

int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int x, y;
		cin >> x >> y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}

	for (int i = 0; i < N; i++)
		sort(edge[i].begin(), edge[i].end());

	for (int i = 1; i <= N; i++)
		if (!visited[i])
			bfs(i);
}