[알고리즘] 그래프에서의 BFS와 DFS

https://ashtonsw.tistory.com/26

[자료구조] 그래프 총 정리

 

이전 글에서 그래프에 대한 내용을 정리했다.

이번에는 그래프에서 BFS와 DFS를 통해서 순회를 해보는 알고리즘을 구현해 보자.

 

 그래프에서도 시작점에서 다른 모든 점으로의 최단 경로를 찾을 때 BFS를 활용할 수가 있다. BFS의 과정 중에서 현재 보는 정점으로부터 추가되는 인접한 정점은 시작점으로부터 1만큼 떨어져 있다고 가정한다. 즉, 모든 간선의 길이가 동일할 때 두 지점 사이의 거리를 찾는 문제는 BFS로 해결할 수 있다.

 하지만 edge의 길이가 다른 경우 플로이드나 다익스트라 알고리즘을 사용해야 한다.

 

// 연결 그래프에서의 순회

vector <int> adj[10];
bool vis[10];

void bfs(){
    queue <int> Q;
    Q.push(1);
    vis[1] = true;
    while(!Q.empty()){
    	int cur = Q.front();
        Q.pop();
        cout << cur << ' ';
        for(auto nxt : adj[cur]){
            if (vis[nxt]) continue;
            Q.push(nxt);
            vis[nxt] = true;
        }
    }
}

 

 실제로 인접 리스트 방식으로 저장된 그래프를 확인해 보자. 정점은 1번부터 V번까지 순서대로 번호가 매겨져 있다고 가정했다. Queue에 넣어준 후에 vis값을 true로 방문했다고 표시해야 한다. 인접 행렬로 BFS를 구현한다고 하면 시간복잡도는 O(V²)으로 비효율적이다.

 

// 연결 그래프에서 1번 정점과의 거리

vector <int> adj[10];
int dist[10];

void bfs(){
    fill(dist, dist+10, -1);
    queue <int> Q;
    Q.push(1);
    dist[1] = 0 ;
    while(!Q.empty()){
    	int cur = Q.front();
        Q.pop();
        for(auto nxt : adj){
            if (dist[nxt] != -1) continue;
            Q.push(nxt);
            dist[nxt] = dist[cur] + 1;
        }
    }
}

 

BFS의 마지막으로 연결 그래프가 아닐 때의 순회이다.

 

// 연결 그래프가 아닐 때의 순회

vector <int> adj[10];
bool vis[10];
int vertex = 9;

void bfs(){
    queue <int> Q;
    for(int i = 1; i <= vertex; i++){
    	if(vis[i]) continue;
        Q.push(i);
        vis[i] = true;
    	while(!Q.empty()){
            int cur = Q.front();
            Q.pop();
            for(auto nxt : adj[cur]){
            	if(vis[nxt]) continue;
                Q.push(nxt);
                vis[nxt] = true;
            }
        }
    }
}

 

 

---

DFS

 

 다음은 DFS이다. DFS는 BFS에서의 큐를 스택으로만 대체하면 된다. 따라서 구현은 어려운 부분이 없는데.. 사실 DFS는 재귀를 사용해서 구현할 수 있다. 재귀적으로 함수를 호출하는 상황이 가장 늦게 호출된 함수를 먼저 처리하는 LIFO, 즉 자연스럽게 Stack을 이용하는 모양새가 되기 때문이다.

 

우선 연결 그래프에서의 순회(비재귀)이다.

// 연결 그래프에서의 순회

vector <int> adj[10];
bool vis[10];

void bfs(){
    stack <int> S;
    S.push(1);
    vis[1] = true;
    while(!S.empty()){
    	int cur = S.top();
        S.pop();
        cout << cur << ' ';
        for(auto nxt : adj[cur]){
            if (vis[nxt]) continue;
            S.push(nxt);
            vis[nxt] = true;
        }
    }
}

 

 

 DFS를 재귀적으로 코드를 구현하면, 코드가 알아보기 쉬워지고, 길이도 짧아진다. 그런데 스택 메모리의 제한이 작은 경우에는 사용하기 어려울 수 있다.

 

연결 그래프에서의 순회(재귀) 코드를 확인해보자.

vector <int> adj[10];
bool vis[10];

void dfs(int cur){
    vis[cur] = true;
    cout << cur << ' ';
    for(auto nxt : adj[cur]){
    	if(vis[nxt]) continue;
        dfs(nxt);
    }
}

 

 위와 같이 재귀로 DFS를 구현하면, 스택 영역에 값이 쌓인다. 간혹 스택 영역 메모리를 1MB나 10MB로 작게 제한을 걸면, 사용하기 힘들어서 비재귀(스택)을 사용해서 DFS를 구현해야 한다.

 

바킹독님 유튜브 참고 사진

 재귀적인 방식은 실제 방문할 때 방문 표시를 남기지만, 비재귀적 방식은 방문하기 전에 아직 방문하지 않은 곳을 발견하면 그 때 방문 표시를 남기기 때문에 위와 같은 차이가 발생한다.