DFS 와 BFS

그래프 순회 (graph traversal)

- 하나의 정점에서 시작하여 모든 정점들을 한번씩 방문하는 작업

- 많은 문제들이 그래프 순회를 이용하여 해결될 수 있음

> ex) 두 정점 사이의 연결 경로가 있는지 검사, 최단 거리 검사 등

- 대표적인 그래프 순회 방법

> 깊이 우선 탐색 (DFS : Depth First Search)

> 너비 우선 탐색 (BFS : Breadth First Search)

 

 

∙ 깊이 우선 탐색 (DFS : depth first serach)

- 현재 정점과 인접한 정점 중 하나를 선택하여 이동하는 과정을 반복하고, 더 이상 이동할 정점이 없을 경우 뒤쪽으로 백트래킹하여 다시 이동할 경로를 탐색

- 시작 정점으로부터 거리가 멀어지는 방식으로 정점을 탐색

- 보통 재귀 또는 스택을 이용하여 구현

 

∙ 재귀 이용 방법 

const int N = 6;
bool visited[N] = {};

void dfs_recursion(const vector<vector<int>>& adj_list, int s)
{
	//이미 s를 방문했으면 함수 종료
    if (visited[s])
    	return;
    
	// 그렇지 않으면 s를 방문
    visited[s] = true;
    cout << s << ", ";
    
	// s와 인접한 모든 노드에 대해 dfs_recursion()함수를 재귀 호출
    for (int v : adj_list[s])
    	dfs_recursion(adj_list, v);
}

int main()
{
	vector<vector<int>> adj_list = 
    { {1, 3, 4}, {0, 2, 4}, {1, 5}, {0, 4}, {0, 1, 3}, {2} };
    
    // 노드랑 시작위치를 지정해 함수를 호출한다.
    dfs_recursion(adj_list, 0);
    cout << endl;
}

 

∙ 스택 이용 방법

vector<int> dfs(const vector<vector<int>>& adj_list, int s)
{
	vector<bool> visited(adj_list.size(), false);
    vector<int> visited_order;
    
    // 비어 있는 스택을 생성하고, s를 삽입
    stack<int> stk;
    stk.push(s);
    
    while (!stk.empty()){
    	// 스택에서 정점 번호를 꺼내서 변수 v로 설정
        int v = stk.top();
        stk.pop();
        
        // 이미 v를 방문했으면 스택의 다음 정점 번호를 꺼냄
        if (visited[v])
        	continue; // 이미 방문헀으면 스킵
            
        // 그렇지 않으면 v를 방문
        visited[v] = true; // 정점 v를 방문
        visited_order.push_back(v);
        
        // v와 인접한 노드 중에서 아직 방문하지 않은 정점 번호를 스택에 삽입
        for (int a : adj_list[v]{
        	if (!visited[a])
            	stk.push(a);
        }
    }
    return visit_order;
}

 

∙ 너비 우선 탐색 (BFS : breadth first search)

- 현재 정점과 인접한 모든 정점을 방문한 후, 다시 이들 정점과 인접한 모든 정점을 찾아 방문하는 방식

- 시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문

- 보통 큐를 이용하여 구현

 

∙ 큐 이용 방법

vector<int> bsf(const vector<vector<int>>& adj_list, int s)
{
	vector<bool> visited(adj_list.size(), false);
    vector<int> visit_order;
    // 비어 있는 큐를 생성하고, s를 삽입
    queue<int> q;
    q.push(s);
    
    while (!q.empty()){
    	// 큐에서 정점 번호를 꺼내서 변수 v로 설정
        int v = q.front();
        q.pop();
        
        // 이미 v를 방문헀으면 큐의 다음 정점 번호를 꺼냄
        if (visited[v])
        	continue;
            
        // 그렇지 않으면 v를 방문
        visited[v] = true;
        visit_order.push_back(v);
        
        // v와 인접한 노드 중에서 아직 방문하지 않은 정점 번호를 큐에 삽입
        for (int a : adj_list[v]){
        	if (!visited[a])
            	q.push(a);
        }
    }
    return visit_order;
}

 

 

 

∙ DFS와 BSF 전체 코드

#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>

using namespace std;

const int N = 6;
bool gVisited[N] = {};

void dfs_recursion(const vector<vector<int>>& adj_list, int s)
{
    if (gVisited[s])
        return;

    gVisited[s] = true;
    cout << s << ", ";

    for (int v : adj_list[s])
        dfs_recursion(adj_list, v);
}

vector<int> dfs(const vector<vector<int>>& adj_list, int s)
{
    vector<bool> visited(adj_list.size(), false);
    vector<int> visit_order;
    stack<int> stk;
    stk.push(s);

    while (!stk.empty()) {
        int v = stk.top();
        stk.pop();

        if (visited[v])
            continue; // 이미 방문했으면 스킵!

        visited[v] = true; // 정점 v를 방문
        visit_order.push_back(v);

        for (int a : adj_list[v]) {
            if (!visited[a])
                stk.push(a);
        }
    }

    return visit_order;
}

vector<int> bfs(const vector<vector<int>>& adj_list, int s)
{
    vector<bool> visited(adj_list.size(), false);
    vector<int> visit_order;
    queue<int> q;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        if (visited[v])
            continue; // 이미 방문했으면 스킵!

        visited[v] = true; // 정점 v를 방문
        visit_order.push_back(v);

        for (int a : adj_list[v]) {
            if (!visited[a])
                q.push(a);
        }
    }

    return visit_order;
}

int main()
{
    vector<vector<int>> adj_list = {
        {1, 3, 4},
        {0, 2, 4},
        {1, 5},
        {0, 4},
        {0, 1, 3},
        {2}
    };

    cout << "dfs_recursion: ";
    dfs_recursion(adj_list, 0);
    cout << endl;

    auto dfs_order = dfs(adj_list, 0);
    auto bfs_order = bfs(adj_list, 0);

    cout << "dfs: ";
    for (auto n : dfs_order)
        cout << n << ", ";
    cout << endl;

    cout << "bfs: ";
    for (auto n : bfs_order)
        cout << n << ", ";
    cout << endl;
}