알고리즘 템플릿 : DFS와 BFS

앞으로 여기에 올릴 템플릿 코드는 Github에서도 볼 수 있고, 매우 중요한 내용이 아니면 최신 코드는 이 블로그가 아니라 Github에서만 유지할 예정이다!

그래프를 탐색하는 가장 기초적인 알고리즘인 DFS와 BFS이다!

DFS는 보통 재귀 함수로 구현되고, BFS는 보통 Queue 자료 구조를 통해서 구현되고, 이번에는 DFS와 BFS를 크게 4가지 경우로 나누어서 템플릿을 만들어 보았다. 내가 주로 지키려고 노력하는 코딩 스타일에 영어로 Comment를 달아놓았다...!

1. 그래프의 세부 구현이 정해지지 않은 경우
2. 그래프의 인접 행렬(adjacency matrix)이 2D array로 구현된 경우
3. 그래프의 인접 리스트(adjacency list)가 2D vector로 구현된 경우
4. 그래프의 정점(vertice)이 2D array로 구현된 경우

BFS에서, 탐색을 시작하는 정점으로부터의 거리를 알아야 하는 경우는 1번 파일의 BFS 함수에서 Comment 처리가 되어 있는 dist 변수와 num_remaining_vertices 변수를 사용하면 된다!

1. dfs-bfs-general.cpp

#include <iostream>
#include <vector>
#include <queue>

// A graph consists of one or more vertices.
// Usually int(in graph problems) or std::pair<int, int>(in board problems).
using Vertice = int;

// A graph can be an 2D array, 2D std::vector object, etc.
// It can be declared as either global or local variable.
class Graph {

};

// Returns true if the given vertice is already visited.
bool visited(Graph &g, Vertice i) {
    return false;
}

// Returns next vertices can be visited. 
std::vector<Vertice> next(Graph &g, Vertice i) {
    return std::vector<Vertice> {};
}

// Depth-first-search algorithm.
void DFS(Graph &g, Vertice v) {
    if (visited(g, v)) return;
    // Mark the vertice as visited and do something.
    // graph[v][v] = -1, visited[i] = true, etc...
    // std::cout << v << std::endl;
    for (auto i: next(g, v)) DFS(g, i);
}

// Breadth-first-search algorithm.
void BFS(Graph &g, Vertice v) {
    // Variables to keep track of the distances from inital vertex.
    // 'dist' is the distance from inital vertex.
    // int dist {1};
    // 'num_remaining_vertices' is the number of remaining vertex, 'dist' away from inital vertex.
    // int num_remaining_vertices {1};
    std::queue<int> q;
    // Mark the inital vertice as visited and push to the queue.
    // graph[v][v] = -1, visited[v] = true, etc...
    q.push(v);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        // num_remaining_vertices--;
        // Do something here.
        // std::cout << u << std::endl;
        for (auto i: next(g, u)) {
            if (!visited(g, i)) {
                // Mark the vertice as visited and push to the queue.
                // graph[i][i] = -1, visited[i] = true, etc...
                q.push(i);
            }
        }
        // std::cout << dist << std::endl;
        // if (num_dist == 0) {
        //     dist++;
        //     num_remaining_vertices = q.size();
        // }
    }
}

2. dfs-bfs-array.cpp

#include <iostream>
#include <vector>
#include <queue>

const int ARR_SIZE {1000};

// A 2D array representing an adjacency matrix of a graph.
int graph[ARR_SIZE][ARR_SIZE];
// An 1D array to check if a vertex is visited in O(1) time.
bool visited[ARR_SIZE];

// v is the index of vertice to visit, and n is the number of vertices.

// Depth-first-search algorithm.
void DFS(int v, int n) {
    if (visited[v]) return;
    // Mark the vertice as visited and do something.
    visited[v] = true;
    // std::cout << u << std::endl;
    for (int i=0; i<n; i++) {
        if (graph[v][i] == 1) DFS(i, n);
    }
}

// Breadth-first-search algorithm.
void BFS(int v, int n) {
    std::queue<int> q;
    // Mark the inital vertice as visited and push to the queue.
    visited[v] = true;
    q.push(v);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        // Do something here.
        // std::cout << u << std::endl;
        for (int i=1; i<=n; i++) {
            if (graph[u][i] == 1 && !visited[i]) {
                // Mark the vertice as visited and push to the queue.
                visited[i] = true;
                q.push(i);
            }
        }
    }
}

3. dfs-bfs-vector.cpp

#include <iostream>
#include <vector>
#include <queue>

// A 2D vector representing an adjacency list of a graph.
std::vector<std::vector<int, int>> graph;
// An 1D vector to check if a vertex is visited in O(1) time.
std::vector<bool> visited;

// v is the index of vertice to visit.

// Depth-first-search algorithm.
void DFS(int v) {
    if (visited[v]) return;
    // Mark the vertice as visited and do something.
    visited[v] = true;
    // std::cout << v << std::endl;
    for (auto i: graph[v]) DFS(i);
}

// Breadth-first-search algorithm.
void BFS(int v) {
    std::queue<int> q;
    // Mark the inital vertice as visited and push to the queue.
    visited[v] = true;
    q.push(v);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        // Do something here.
        // std::cout << u << std::endl;
        for (auto i: graph[v]) {
            if (!visited[i]) {
                // Mark the vertice as visited and push to the queue.
                visited[i] = true;
                q.push(i);
            }
        }
    }
}

4. dfs-bfs-board.cpp

#include <iostream>
#include <vector>
#include <queue>

const int BOARD_SIZE {1000};

// A 2D array representing board.
int board[BOARD_SIZE][BOARD_SIZE];
// An 2D array to check if a vertex is visited in O(1) time.
bool visited[BOARD_SIZE][BOARD_SIZE];

// Returns next vertices can be visited. 
std::vector<std::pair<int, int>> next(std::pair<int, int> v, int m, int n) {
    return std::vector<std::pair<int, int>> {};
}

// v is the position of vertice to visit, and m×n is the size of board.

// Depth-first-search algorithm.
void DFS(std::pair<int, int> v, int m, int n) {
    if (visited[v.first][v.second]) return;
    // Mark the vertice as visited and do something.
    visited[v.first][v.second] = true;
    // std::cout << v.first << " " << v.second << std::endl;
    for (auto p: next(v, m, n)) DFS(p, m, n);
}

// Breadth-first-search algorithm.
void BFS(std::pair<int, int> v, int m, int n) {
    std::queue<std::pair<int, int>> q;
    // Mark the inital vertice as visited and push to the queue.
    visited[v.first][v.second] = true;
    q.push(v);
    while (!q.empty()) {
        auto u = q.front();
        q.pop();
        // Do something here.
        // std::cout << u.first << " " << u.second << std::endl;
        for (auto p: next(u, m, n)) {
            if (!visited[p.first][p.second]) {
                // Mark the vertice as visited and push to the queue.
                visited[p.first][p.second] = true;
                q.push(p);
            }
        }
    }
}