BFS(너비 우선 탐색) 알고리즘

 

BFS(Breadth-First Search)란?

그래프 순회 방법이 대표적으로 DFS와 BFS가 있는데 이번 시간에는 BFS를 알아보도록 하겠다!

BFS 알고리즘은 출발 노드로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

 

그래프 순회 문제 중 최단 경로를 구하는 문제에 많이 쓰이는 알고리즘이다.

 

BFS 예시 - 출처: commons.wikimedia

 

DFS 알고리즘은 다음 글을 참고하면 된다.

https://yhoons.tistory.com/8

DFS(깊이 우선 탐색) 알고리즘

 

---

 

BFS 이해하기

 

BFS 알고리즘을 구현하는 방법에는 DFS와 마찬가지로 인접 리스트를 이용하는 방법, 인접 행렬을 이용한 방법이 있는데 각각 장단점이 존재한다.

 

인접리스트를 이용했을 때

장점: 모든 노드를 순환하려 할 때 O(N) 시간밖에 걸리지 않는다. 빈 공간이 생기지 않는다.

단점: 인접한 특정 노드를 알고싶을 때 리스트 안에 일일이 찾아봐야 한다.

 

인접 행렬을 이용했을 때

장점: 인접한 특정 노드를 알고 싶을 때 2차원 배열에 정보가 저장돼있기 때문에 한 번에 찾을 수 있다.

단점: 모든 노드를 순환하려 할 때 O(N^2) 시간이 걸린다. 빈 공간이 많이 남을 수도 있다.

 

 

어떤 그래프냐에 따라 리스트를 사용할지, 행렬을 사용할 지 선택하면 된다.

 

---

DFS와 BFS의 차이 

 

DFS는 스택을 이용해 한 방향으로 가면서 방문한 노드를 스택에 쌓고 인접한 노드가 없는 지점까지 왔다면

스택에 있는 원소를 pop을 해주어 되돌아오며 그래프를 순회하는 방법이고

 

BFS는 큐를 이용해  이웃한 노드를 모두 큐에 넣고, 큐에 가장 먼저 들어왔던 노드를 빼면서 이웃한 노드를 큐에 넣는 과정을 반복하며 그래프를 순회하는 방법이다.

 

 

---

 

먼저 인접 행렬로 BFS를 구현해보자. 아래와 같은 그래프로 예시를 들겠다.

그래프 예시

 

 

각 노드와의 관계를 나타낸 인접 행렬은 이러하다.

인접 행렬

 

1. 노드 v를 시작 노드로 지정하고 BFS 알고리즘을 돌리게 되면 가장 먼저 노드 v가 큐에 삽입된다.

2. 큐 제일 앞에 있는 노드 v를 pop 해주면서 노드 v와 이웃한 방문하지 않은 노드가 있다면 큐에 삽입한다. 그리고 방문 표시를 한다.

3. 2번을 반복한다.

 

#include <iostream>
#include <queue>

using namespace std;

int adjArray[11][11]; //10*10행렬 생성
int visited[11]; //1~10노드 방문 여부 배열

void AddEdge(int start, int end) { //입력 할 때 양방향으로 저장하는 함수
	adjArray[start][end]=1;
	adjArray[end][start]=1;
}

void bfs(int v) {
    queue<int> q; //큐 생성
    q.push(v); //현재 노드 큐에 삽입
    visited[v] = 1; //방문 표시
    while (!q.empty()) { //큐가 빌 때까지 반복
       
        int x = q.front(); //큐 맨 앞에 있는 노드를 변수 x에 저장
        q.pop(); //그 노드 큐에서 제거
        cout << x << ' ';
       
        for (int i = 1; i <= 10; i++) { //x노드와 이웃한 노드 탐색
            if (adjArray[x][i]==1 && visited[i]==0) { //이웃해있고 방문하지 않았다면
                q.push(i); //큐에 삽입
                visited[i] = 1; // 방문표시
            }
        }
    }
}

int main(void) {
     
    //노드 관계 저장
    AddEdge(1,3);
    AddEdge(1,7);
    AddEdge(1,8);
    AddEdge(2,3);
    AddEdge(4,5);
    AddEdge(4,10);
    AddEdge(5,8);
    AddEdge(6,8);
    AddEdge(6,9);

	//시작 노드를  8로 지정
    bfs(8);
}

---

출력

인접행렬을 이용한 BFS 출력값

 

---

다음은 인접 리스트로 BFS를 구현해보겠다.

 

인접 리스트

#include <iostream>
#include <queue>

using namespace std;


vector<vector<int> > adjArray; //이중 벡터 생성
vector<int> visited; //방문 여부 표시 벡터


void AddEdge(int start, int end) { //입력할 때 자동으로 양방향으로 저장할 수 있게 하는 함수
	adjArray[start].push_back(end);
	adjArray[end].push_back(start);
}


void bfs(int v) {
    queue<int> q; //큐 생성
    q.push(v); //해당 노드를 큐에 삽입
    visited[v] = 1; // 방문 처리
    while (!q.empty()) { //큐가 빌 때까지 반복
       
        int x = q.front(); //큐의 맨 앞 노드를 변수 x에 저장
        q.pop(); //그 노드를 제거
        cout << x << ' '; //출력
       
        for (int i = 0; i < adjArray[x].size(); i++) { //이웃한 노드가 있을 때까지 반복
            int y = adjArray[x][i]; //이웃한 노드를 변수 y에 저장
            if(visited[y]==0) { //그 이웃한 노드가 이미 방문이 안된 노드라면
            q.push(y); //그 노드를 큐에 삽입
            visited[y] = 1; //방문 처리
            }
        }
    }
}

int main(void) {
     
     int n=10; //노드 개수
   
   //인접리스트와 방문여부 벡터 초기화
	adjArray.resize(n + 1);
	visited.resize(n + 1);

    //노드 관계 저장
    AddEdge(1,3);
    AddEdge(1,7);
    AddEdge(1,8);
    AddEdge(2,3);
    AddEdge(4,5);
    AddEdge(4,10);
    AddEdge(5,8);
    AddEdge(6,8);
    AddEdge(6,9);


    bfs(8);
}

---

 

출력

 

인접 리스트를 이용한 BFS 출력값

---