[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);
}