[알고리즘] 깊이 우선 탐색, 너비 우선 탐색 (DFS, BFS)

DFS, BFS

깊이 우선 탐색 (DFS)

그래프 탐색 알고리즘 중 하나로, 깊이를 우선으로 탐색하는 방법이다. 시작 노드에서 한 방향으로 갈 수 있는 만큼 깊이 들어가며 탐색한다. 주로 스택이나 재귀를 사용해서 구현하며, 모든 경로를 탐색하는 완전 탐색이다.

너비 우선 탐색 (BFS)

그래프 탐색 알고리즘 중 하나로, 너비를 우선으로 탐색하는 방법이다. 한 노드에 연결된 하위 노드를 모두 탐색한 뒤 다음 레벨로 넘어가 탐색한다. 큐를 사용해서 구현하며, 모든 경로를 탐색하는 완전 탐색이다.

DFS BFS비교

공통점	차이점	DFS	BFS
그래프 탐색 알고리즘	탐색 방법	깊이 우선	너비 우선
완전탐색 알고리즘	데이터 구조	스택 또는 재귀	큐
반드시 찾을 수 있지만 느림	최단 경로	불리	유리
경로 탐색에 사용할 수 있음	활용	미로찾기, 사이클 탐색 등	최단 경로, 최소 비용 경로 등

BFS는 가까운 노드를 먼저 방문하기 때문에 제일 먼저 발견한 경로가 가장 최단거리이다. 간선이 많을 경우 DFS가 유리하고, 적을 경우 BFS가 유리하다. 백트래킹 적용 가능하나 DFS가 더 유리하다.

[알고리즘] 백 트래킹 (Back Tracking)

구현

그래프 adj는 인접 리스트로 구현하였다.

[CS] AdjacentMatrix&AdjacentList

DFS 알고리즘


void DFS(const int& now, vector<bool>& visited) const {
    visited[now] = true;
    cout << now << " ";
    for (auto i : adj[now]) {
        if (!visited[i]) {
            DFS(i, visited);
        }
    }
}

BFS 알고리즘


void BFS(const int& start) const{
    int tmp;
    vector<bool> visited(vNum, false);
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        tmp = q.front();
        q.pop();
        cout << tmp << " ";
        for (auto i : adj[tmp]) { //adj는 인접행렬
            if (!visited[i]) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
}