BFS 구현 (큐)

그래프는 이 블로그에서 가져온 그림을 참고했다.

 

#include <iostream>
#include <queue>
#include <time.h> // To measure execution time
#define SIZE 9

using namespace std;

void BFS(vector<int> _graph[], bool _visit[])
{
    queue<int> bfsQueue;
    
    bfsQueue.push(1);
    
    int currentIndex = 0;
    while(!bfsQueue.empty())
    {
        currentIndex = bfsQueue.front();
        _visit[currentIndex] = true;
        cout << currentIndex;
        bfsQueue.pop();
        
        for (size_t i = 0; i < _graph[currentIndex].size(); ++i)
        {
            if (!_visit[_graph[currentIndex][i]])
                bfsQueue.push(_graph[currentIndex][i]);
        }
    }
    
}

void LinkTwoNodes(vector<int>_graph[], int _a, int _b)
{
    _graph[_a].push_back(_b);
    _graph[_b].push_back(_a);
}

void MakeGraph(vector<int> _graph[])
{
    LinkTwoNodes(_graph, 1, 2);
    LinkTwoNodes(_graph, 2, 5);
    LinkTwoNodes(_graph, 1, 3);
    LinkTwoNodes(_graph, 3, 6);
    LinkTwoNodes(_graph, 6, 9);
    LinkTwoNodes(_graph, 3, 7);
    LinkTwoNodes(_graph, 1, 4);
    LinkTwoNodes(_graph, 4, 8);
}

int main()
{
    time_t startTime = clock();
    
    vector<int> graph[SIZE + 1];
    bool visit[SIZE + 1] = { false };
    
    MakeGraph(graph);
    
    BFS(graph, visit);
    
    time_t endTime = clock();
    cout << "\nexecution time : " << endTime - startTime << endl;
    
    return 0;
}

결과

실행속도는 34ms이다. 

큐를 사용하는 경우 큐는 일반적으로 큐에 빈 메모리가 남아 있어도 rear가 배열의 끝에 도달했을 경우 꽉 차있는것으로 판단할 수 있다는 단점이 있다.

시간 복잡도

DFS와 같다. 일반적으로 BFS가 더 빠르긴 하다.

 

V : 노드(정점)

E : 엣지(간선)

 

    3.1. 그래프를 인접행렬 (이차원 배열)로 구성하는 경우

        DFS가 각 정점(|V|)마다 호출되고 연결된 정점을 찾는데 |V|만큼의 시간이 걸린다.

        따라서 O( |V|^2 )

 

    3.2. 그래프를 인접리스트 (벡터의 배열)로 구성하는 경우

        DFS가 각 정점(|V|)마다, 각 간선(|E|)마다 호출된다.

        따라서 O( |V|+|E| )