[Algorithm / C++] 인접행렬과 BFS (너비 우선 탐색) 알고리즘 및 구현

이번 포스팅에서는 탐색 알고리즘에서 가장 중요하게 활용되는 BFS 알고리즘과 인접 행렬에 대해 다루도록 하겠습니다.

 

 

인접행렬

 

 

인접행렬에 대한 설명은 다른 사이트에서 워낙 많이 다뤄 온 주제이기 때문에 본 포스팅에서 구체적으로 설명하지 않겠습니다. 그럼에도 불구하고 본 포스팅에서 인접행렬을 다루는 가장 큰 이유는 BFS 알고리즘과 관련이 많기 때문입니다. 보통 경로 탐색 알고리즘을 사용하는 경우, 예를 들어 A->Z로 가는 방향에 대해 최적의 경로를 찾고자 하는 경우, 다양한 방식으로 경로를 계산하고 이를 표현할 수 있습니다. 어떠한 알고리즘을 사용하느냐에 따라 경로가 달라지는데, 이러한 경로에 대한 정보를 행렬로 표현할 수 있습니다. 흔히 사용되는 행렬이 인접행렬입니다. 인접 행렬에는 다음과 같이 몇 가지 요소가 있습니다.

 

- 정점, 혹은 노드 (vertex, node): 경로에 사용될 수 있는 모든 거점들.

- 간선, 혹은 엣지 (edge): 정점과 정점을 잇는 루트.

- 방향 (direction): 정점 A와 B 간의 경로 방향. 양방향이 될 수도 있고 일방향이 될 수 도 있으며, 방향이 A->B 혹은 B->A가 될 수도 있다.

 

앞서 언급한 바와 같이 인접행렬에는 방향 개념이 존재하는데, 방향성이 존재하는 경우 유향 그래프(일방향 그래프), 존재하지 않는 경우 무향 그래프(양방향 그래프)라고 부릅니다. 아래 그림은 무향 그래프에 대한 간선과 정점을 그래프와 인접행렬 예시를 보여줍니다. 인접 행렬에서 값이 1로 표현된 경우, 정점간 간선이 서로 연결된 경우를 의미합니다. 반대로 0인 경우에는 서로 연결되지 않음을 의미합니다. 참고로 대각선의 경우 자기 자신을 의미하므로 0입니다.

예) 1열 2행: 정점 1과 2간에 서로 연결됨. 4열 3행: 정점 4와 3간에 서로 연결되지 않음

 

보시다시피 무향 그래프는 양방향이기 때문에 대각선을 기준으로 좌우가 서로 대칭임을 알 수 있습니다. 반대로 유향 그래프의 경우에는 서로 대칭적이지 않습니다.

 

좌: 정점과 간선 정보를 토대로 그린 무향(양방향) 그래프. 우: 정점과 간선 정보를 나타낸 인접행렬

 

 

BFS (Breadth First Search, 너비 우선 탐색) 알고리즘

 

 

BFS는 최적의 경로를 탐색하기 위해 주로 사용되는 탐색 기법입니다. 'BFS' 라는 단어 자체가 의미하는 것과 같이, DFS(깊이 우선 탐색)와 달리 정점 A가 향할 수 있는 모드 경로를 우선 탐색해 나가는 방식입니다. 예를 들어 위에서 예로 들었던 그래프를 토대로 볼 때, 정점 '1'이 향할 수 있는 경로는 '2'와 '3'이 있습니다. 그 다음에는 순서에 의해 '2'를 토대로 다시 또 가능한 경로를 찾습니다. '4'와 '5로 향할 수 있으며, 연결된 '1'은 이미 탐색을 마쳤기 때문에 또 다시 방문하지 않습니다. 

 

이러한 루틴으로 전체 경로 탐색 방법을 이미지로 표현해 보면 아래 그림과 같으며, 각 단계 별로 아래의 순서로 탐색을 반복합니다.

1. queue push: 방문한 정점들을 queue에 저장

2. 간선으로 연결된 정점 탐색: 현재 정점을 기준으로 간선으로 연결된 정점들의 정보를 탐색

 

 

3. queue pop: 모든 간선 정보를 파악 후 queue에서 정점 1개를 pop.

4. 다음 정점(방금 queue에서 pop한 다음에 저장되어 있는 값)  방문하여 1번부터 다시 반복합니다.

5. 모든 간선 방문을 마치면 루틴을 마칩니다.

 

(참고: 파란색 정점: queue에 push 하거나 이미 저장되어 있는 정점. 빨간색 정점: pop 된 정점)

 

BFS 탐색 알고리즘

 

위의 순서를 거쳐 최종적으로 탐색된 경로를 그래프로 표현하면 다음과 같습니다.

 

순서: 1 -> 2 -> 3 -> 4 -> 5 ->7 -> 6

 

 

C++ 기반의 코드 구현

 

앞서 다룬 BFS 알고리즘과 인접행렬 개념을 바탕으로 C++로 구현할 수 있습니다. 물론 여기에도 개발자마다 다양한 방식으로 구현하고, 또 구현해야 하는 개발 목표에 따라 수정이 불가피 할 수 있습니다. 하지만 본 포스팅에서는 위에서 다뤘던 개념들을 바탕으로 최대한 심플하게 구현해 보도록 하겠습니다.

 

아래 코드를 참고할 때 유념해야 할 사항이 몇 가지 있습니다.

- 간선(edge) 정보: 인접행렬 정보를 이중 벡터로 구성.

- 방문한 노드 리스트(vertices): 우리는 위에서 다룬 것과 같이 이미 방문한 적이 있는 노드의 경우, 어딘가에 기록해 둬야 합니다. 예를 들어, 위의 3단계의 경우, 정점 2는 1과 연결이 되어있지만, 1은 이전에 이미 방문했기 때문에 1로 탐색하는 경우는 막아야 합니다. 이를 위해 방문한 정점은 전부 vertices 벡터에 저장해 둘 것입니다.

- 방문한 노드 표시(Visited): 임시로 방문했음을 표시.

- 방문하지 않은 노드 표시(Unvisited): 아직 방문하지 않은 값. 특히 간선으로 연결되어 있는 경우에만 유효.

- queue: 방문한 정점을 push 하고 pop.

- BFS(): 실제 BFS 탐색을 위한 함수. 주의할 점은 첫 정점은 반드시 일단 queue에 push하고 시작한다.

 

위의 정보를 바탕으로 구현한 결과는 다음과 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
 
#define VISITED 1
#define UNVISITED 0
#define CONNECTED 1
using namespace std;

// 행과 열 사이즈가 동일해야 함.
vector<vector<int> > edge =
{
    {0, 1, 1, 0, 0, 0, 0},
    {1, 0, 0, 1, 1, 0, 0},
    {1, 0, 0, 0, 0, 0, 1},
    {0, 1, 0, 0, 0, 1, 0},
    {0, 1, 0, 0, 0, 1, 0},
    {0, 0, 0, 1, 1, 0, 1},
    {0, 0, 1, 0, 0, 1, 0}
};

vector<int> vertices;

void BFS(int v_i) 
{
    vertices.at(v_i) = VISITED;
    queue<int> q;
    q.push(v_i);
    cout << v_i+1 << " ";
    
    while (!q.empty()) 
    {
        int t_v = q.front();
        q.pop();
 
        for (int i = 0; i < edge.size(); i++) 
        {
            if (edge.at(i).at(t_v) == CONNECTED && vertices.at(i) == UNVISITED) 
            {
                cout << i+1<<" ";
                q.push(i);
 
                vertices.at(i) = VISITED;
            }
        }
    }
}

int main() 
{
    vertices.assign(edge.size(),UNVISITED);
 
    for (int i = 0; i < edge.size(); i++) 
    {
        if (vertices.at(i) == UNVISITED) 
        {
            BFS(i);
        }
    }
    cout << endl;
    
    return 0;
}

결과:

1 2 3 4 5 7 6