그래프 이론 - DFS와 BFS

선형 구조가 아닌 비선형 구조 탐색 위해선 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 사용한다.

너비 우선 탐색은 브루트 포스와 관련이 깊고 깊이 우선 탐색은 백트래킹과 관련이 깊다.

 

DFS

그래프의 모든 정점 방문

막힌 정점에 도달하지 않는 한 뒤로 돌아가지 않는다 즉 더 따라갈 간선이 없을 경우 이전으로 돌아간다. 이를 구현하기 위해 지금까지 거쳐 온 정점 모두 저장 해 둬야 하는데 재귀 호출 이용하면 이 같은 일을 간단하게 할 수 있다. 재귀 호출한 함수가 종료하면 호출한 위치로 다시 돌아가기 때문이다.

 

DFS 특징

1. 방문한 정점을 알아야 한다. 따라서 각 정점의 방문 여부를 저장하는 자료구조가 필요
2. 더이상 방문할 정점이 없으면 이전 정점으로 돌아가야 한다 -> 재귀, stack 이용
3. 그래프가 분리되어 있을 수도 있다는 사실 고려하지 않는다.

알고리즘 순서

1. 시작 노드 방문 (with 방문 표시)
2. 시작 노드와 인접한 노드 방문
3. 시작 노드와 인접한 노드 b 방문 시 b의 이웃 노드 방문
1. b 노드에 대해 dfs 하여 b의 이웃 노드 모두 방문
4. b 노드 이웃 노드 다 방문했다면 다시 a에 인접한 정점들 중 방문이 안된 노드 방문
1. 다 방문시 종료
2. 아직 방문이 안된 정점이 있으면 그 정점을 시작 정점을 dfs

 

• 인접 행렬로 표현된 그래프 : O(N^2)
• 인접 리스트로 표현된 그래프 : O(N+E)

 

---

 

 

BFS

그래프 탐색

루트 노드에서 인접한 노드를 먼저 탐색하는 방법, 가까운 정점 먼저 방문하고 멀리 떨어진 정점 나중에 방문

두 노드 사이 최단 경로, 임의의 경로 찾고 싶을 때  사용

재귀적으로 동작하지 않는다.

어떤 노드 방문했었는지 여부를 반드시 검사해야 한다 그렇지 않을 경우 무한 루프에 빠질 위험성을 가진다.

방문한 노드 차례로 저장한 후 꺼낼 수있는 자료구조 큐 사용한다.

다익스트라, 프림 알고리즘과 유사하다

 

알고리즘 순서

1. 시작 노드 방문 + 방문 노드 체크
1. 큐에 방문한 노드 삽입
2. 초기 상태 큐는 시작 노드만 저장
2. 큐에서 꺼낸 노드와 인접 노드 차례로 방문
1. 큐에서 꺼낸 노드 방문
2. 큐에서 꺼낸 노드와 인접 노드 방문  - 인접 노드 없으면 큐에서 노드 꺼냄
3. 큐에서 방문된 노드 삽입
3. 큐 소진때까지 반복

 

• 인접 리스트로 표현된 그래프 : O(N+E)
• 인접 행렬로 표현된 그래프 : O(N^2)

 

1) BFS를 사용하는 목적은 최단경로를 구할때 (단, 모든 간선의 가중치가 1일때)

2) DFS을 사용하는 목적은 시작점에서 끝점까지 도달하는 경로로 무언가를 얻고 싶을 때

 

 

c++ 예제

백준 1260번 문제

//
//  1260_bfs_dfs.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/02/13.
//

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


using namespace std;
// dfs 에 들어오면 방문한 것으로 판단 방문 판단 여부가 반드시 들어가야 한다.

//recursion used
/*void dfs(int start, vector<int> graph[], bool check[]){
    check [start] = true;
    cout << start;
    for(int i=0; i< graph[start].size(); i++){
        int next = graph[start][i];
        if(check[next] == false){
            dfs(next, graph, check); //recursion used
        }
    }
}
*/

//queue used
void bfs(int start, vector<int> bgraph[], bool bcheck[]){
    queue<int> q;
    q.push(start);
    bcheck[start] = true;
    while(!q.empty()){
        int tmp = q.front();
        q.pop();
        cout << tmp << ' ';
        for(int i=0; i<bgraph[tmp].size(); i++){
            // 방문하지 않았다면
            if(bcheck[bgraph[tmp][i]] == false){
                // 큐에 넣어주고 방문했음을 표시한다.
                q.push(bgraph[tmp][i]);
                bcheck[bgraph[tmp][i]] = true;
            }
        }
    }
}

//stack used
void dfs(int start, vector<int> graph[], bool check[]){
    stack<int> s;
    s.push(start);
    check[start] = true;
    cout << start<< ' ';
    while(!s.empty()){
        int current_node = s.top();
        s.pop();
        for(int i =0; i<graph[current_node].size();i++){
            int next_node = graph[current_node][i];
            if(check[next_node] == false){
                cout <<next_node << ' ';
                check[next_node] = true;
                //pop 했으므로 current_node 를 넣어주여아 햔다.
                s.push(current_node);
                s.push(next_node);
                break;
            }
        }
    }
}


int main(){
    int n, m, start;
    cin >> n >> m >> start;
    vector<int> graph[n+1];
    vector<int> regraph[n+1];
    bool check [n+1];
    bool recheck [n+1];
    
     // fill check ~ check+n index fill to check array
     fill(check, check+n+1, false);
     fill(recheck, recheck+n+1, false);
     for (int i =0; i< m; i++){
         int u,v;
         cin >> u >> v;
         graph[u].push_back(v);
         graph[v].push_back(u);
         regraph[u].push_back(v);
         regraph[v].push_back(u);
     }
     
     for(int i = 1; i<=n; i++){
         sort(graph[i].begin(), graph[i].end());
         sort(regraph[i].begin(), regraph[i].end());
     }
    
    dfs(start, graph, check);
    cout << '\n';
    int restart;
    restart = start;
    bfs(restart, regraph, recheck);
}