깊이 우선 탐색( Depth First Search )이란?
- DFS는 그래프를 탐색할 때 쓰는 알고리즘이며 특정 노드에서 인접한 노드들을 방문하며 방문한 정점은 다시 방문하지 않으며 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘입니다.
DFS 구현 방법 두 가지
재귀를 이용한 DFS
#include <iostream>
#include <vector>
using namespace std;
constexpr int n = 6;
vector<bool> visited(n);
vector<int> adj[n];
void dfs(int node) {
cout << node << "\n";
visited[node] = true;
for (auto v : adj[node]) {
if (visited[v]) {
continue;
}
dfs(v);
}
return;
}
int main()
{
adj[1].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
adj[2].push_back(5);
adj[4].push_back(2);
dfs(1);
return 0;
}
스택을 이용한 DFS 구현
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
constexpr int n = 6;
stack<int> s;
vector<bool> visited(n);
vector<int> adj[n];
void dfs(int node) {
visited[node] = true;
s.push(node);
while (!s.empty()) {
int top = s.top();
s.pop();
cout << top << "\n";
for (auto v : adj[top]) {
if (visited[v]) {
continue;
}
visited[v] = true;
s.push(v);
}
}
return;
}
int main()
{
adj[1].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
adj[2].push_back(5);
adj[4].push_back(2);
dfs(1);
return 0;
}
너비 우선 탐색( Breadth First Search )이란?
- BFS는 그래프를 탐색하는 알고리즘이며 어떤 정점에서 시작해 주변 노드들을 순차적으로 탐색하며 방문한 정점은 다시 방문하지 않는 알고리즘입니다. 같은 가중치를 가진 그래프에서 최단거리를 구할 때 사용할 수 있습니다.
BFS 구현 방법
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
constexpr int n = 6;
queue<int> q;
vector<bool> visited(n);
vector<int> adj[n];
void bfs(int node) {
visited[node] = true;
q.push(node);
while (!q.empty()) {
int top = q.front();
q.pop();
cout << top << "\n";
for (auto v : adj[top]) {
if (visited[v]) {
continue;
}
visited[v] = true;
q.push(v);
}
}
return;
}
int main()
{
adj[1].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
adj[2].push_back(5);
adj[4].push_back(2);
bfs(1);
return 0;
}
BFS로 각 경로마다의 최단 거리
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
constexpr int n = 6;
queue<pair<int,int>> q;
vector<bool> visited(n);
vector<int> adj[n];
void bfs(int node) {
visited[node] = true;
q.push({ node, 0});
while (!q.empty()) {
auto top = q.front();
q.pop();
cout << "노드 : " << top.first << ", 거리 : " << top.second << "\n";
for (auto v : adj[top.first]) {
if (visited[v]) {
continue;
}
visited[v] = true;
q.push({ v, top.second + 1});
}
}
return;
}
int main()
{
adj[1].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
adj[2].push_back(5);
adj[4].push_back(2);
bfs(1);
return 0;
}
