자료구조 - 그래프의 탐색(BFS)

[너비 우선 탐색(BFS : breath first search)]

BFS(너비 우선 탐색, Breadth-First Search)는 그래프 탐색 알고리즘 중 하나로, 시작 정점에서 인접한 모든 정점을 먼저 탐색하는 방식입니다. 큐 자료구조를 사용하여 구현됩니다.

 

 

 

BFS 알고리즘

1. 시작 정점을 큐에 넣고 방문했다고 표시한다.
2. 큐에서 정점을 하나 꺼내고, 해당 정점과 인접한 모든 정점을 큐에 넣고 방문했다고 표시한다.
3. 큐가 빌 때까지 2번 과정을 반복한다.

 

 

 

BFS 구현 : 인졉 행렬

#include <iostream>
#include <vector>
#include <queue>

void BFS(const std::vector<std::vector<int>>& adjMatrix, int start)
{
    std::vector<bool> visited(adjMatrix.size(), false); // 정점의 방문 여부를 저장하는 벡터
    std::queue<int> q; // BFS를 위한 큐

    // 시작 정점을 큐에 넣고 방문 표시
    q.push(start);
    visited[start] = true;

    // 큐가 빌 때까지 반복
    while (!q.empty())
    {
        // 큐에서 정점을 하나 꺼내서 출력
        int v = q.front();
        std::cout << v << " ";
        q.pop();

        // 인접한 정점 중 방문하지 않은 정점을 큐에 넣고 방문 표시
        for (int i = 0; i < adjMatrix.size(); ++i)
        {
            if (adjMatrix[v][i] == 1 && !visited[i]) 
            {
                q.push(i);
                visited[i] = true;
            }
        }
    }
}

 

 

BFS 구현 : 인접 리스트

#include <iostream>
#include <vector>
#include <queue>
#include <list>

void BFS(const std::vector<std::list<int>>& adjList, int start)
{
    std::vector<bool> visited(adjList.size(), false); // 정점의 방문 여부를 저장하는 벡터
    std::queue<int> q; // BFS를 위한 큐

    // 시작 정점을 큐에 넣고 방문 표시
    q.push(start);
    visited[start] = true;

    // 큐가 빌 때까지 반복
    while (!q.empty())
    {
        // 큐에서 정점을 하나 꺼내서 출력
        int v = q.front();
        std::cout << v << " ";
        q.pop();

        // 인접한 정점 중 방문하지 않은 정점을 큐에 넣고 방문 표시
        for (int neighbor : adjList[v]) 
        {
            if (!visited[neighbor])
            {
                q.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

 

 

 

 

[시간 복잡도 분석]

 

인접 행렬

• 각 정점에 대해 모든 정점을 확인하므로, 시간 복잡도는 O(V^2) 입니다.
• 여기서 V는 정점의 수입니다.

인접 리스트

• 각 정점에 대해 인접한 정점을 확인하므로, 시간 복잡도는 O(V + E) 입니다.
• 여기서 V는 정점의 수, E는 간선의 수입니다.

인접 리스트 방식은 인접 행렬 방식에 비해 공간 효율성이 높고, 시간 복잡도가 더 낮아 대규모 그래프에 적합합니다.

 

 

 

 

 

ㅇㅅㅇ