BFS (너비 우선 탐색)

📌 BFS란?

BFS (Breadth First Search) 는 그래프를 탐색할 때, 시작 정점에서 가까운 정점부터 차례대로 방문하는 방식입니다.

• DFS는 '깊이'를 우선으로
• BFS는 '너비'를 우선으로

BFS는 최단 거리 탐색에 매우 적합하며, 큐(Queue) 자료구조를 활용합니다.

---

🔁 탐색 순서 예시

아래 그래프에서 BFS(0)를 수행하면 탐색 순서는 다음과 같습니다:

0 → 1 → 3 → 2 → 4

---

⚙️ 전역 변수 및 자료 구조

struct Vertex {};
vector<Vertex> vertices;
vector<vector<int>> adjacent;
vector<bool> discovered;  // 방문 여부

• vertices: 정점 리스트
• adjacent: 그래프 간선 정보 (인접 리스트 or 행렬)
• discovered: 정점의 방문 여부 추적

---

🛠 그래프 생성 함수

void CreateGraph()
{
    vertices.resize(6);
    adjacent = vector<vector<int>>(6);

    // 인접 리스트 방식 (주석 해제하면 됨)
    // adjacent[0] = {1, 3};
    // adjacent[1] = {0, 2, 3};
    // adjacent[3] = {4};
    // adjacent[5] = {4};

    // 인접 행렬 방식
    adjacent = vector<vector<int>>
    {
        {0, 1, 0, 1, 0, 0},
        {1, 0, 1, 1, 0, 0},
        {0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0},
        {0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0},
    };
}

✅ 인접 리스트는 메모리 효율적
✅ 인접 행렬은 빠른 접근 가능

---

🔄 BFS 함수 구현

void Bfs(int here)
{
    vector<int> parent(6, -1);     // 누구에게서 발견되었는가?
    vector<int> distance(6, -1);   // 시작점에서 거리

    queue<int> q;
    q.push(here);
    discovered[here] = true;

    parent[here] = here;           // 자기 자신에게서 발견됨
    distance[here] = 0;

    while (!q.empty())
    {
        here = q.front();
        q.pop();

        cout << "Visited : " << here << endl;

        for (int there = 0; there < 6; ++there)
        {
            if (adjacent[here][there] == 0) continue;
            if (discovered[there]) continue;

            q.push(there);
            discovered[there] = true;

            parent[there] = here;
            distance[there] = distance[here] + 1;
        }
    }
}

📌 주요 로직 설명

코드	의미
q.push(here)	탐색할 정점을 예약 (발견)
discovered[here] = true	이미 발견했음을 표시
parent[there] = here	누구에게 발견됐는지 기록
distance[there] = distance[here] + 1	시작점과의 거리 계산
while (!q.empty())	큐가 빌 때까지 반복 (BFS 핵심)

---

🔄 모든 정점 BFS 수행

void BfsAll()
{
    for (int i = 0; i < 6; ++i)
        if (!discovered[i])
            Bfs(i);
}

✅ 연결되지 않은 컴포넌트도 탐색 가능하게 해줍니다.
❗ Bfs(0)만 호출하면, 0번과 연결된 정점만 방문하고 끝남

---

🎯 BFS 실행 흐름 예시 (인접 리스트 기준)

Bfs(0)
 → 0 발견 → 예약: 1, 3
 → 1 방문 → 예약: 2 (0, 3은 이미 예약됨)
 → 3 방문 → 예약: 4
 → 2 방문
 → 4 방문

탐색 순서: 0 → 1 → 3 → 2 → 4
5번 정점은 단절되어 탐색되지 않음

---

🔎 BFS 특징

항목	설명
자료구조	큐
방문 순서	가까운 노드부터
활용	최단 거리, 경로 탐색
시간 복잡도	O(V + E) (정점 + 간선)
거리 추적	distance[] 배열
경로 추적	parent[] 배열

---

📋 main

int main()
{
    CreateGraph();
    discovered = vector<bool>(6, false);
    BfsAll(); // or Bfs(0);
}

---