DFS( Depth Firsth Search )와 BFS( Breadth First Search )

깊이 우선 탐색( 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;
}