BFS (너비 우선 탐색)

전체 코드

class Graph
{
    int[,] adj = new int[6, 6]
    {
        { 0, 1, 0, 1, 0, 0 },
        { 1, 0, 1, 1, 0, 0 },
        { 0, 1, 0, 0, 0, 0 },
        { 1, 1, 0, 0, 1, 0 },
        { 0, 0, 0, 1, 0, 1 },
        { 0, 0, 0, 0, 1, 0 }
    };
    List<int>[] adj2 = new List<int>[6]
    {
        new List<int> {1, 3},
        new List<int> {0, 2, 3},
        new List<int> {1},
        new List<int> {0,1,4},
        new List<int> { 3,5 },
        new List<int> {4},
    };

    bool[] visited = new bool[6];
    
    public void BFS(int start)
{
    bool[] found = new bool[6];   // 각 정점이 방문되었는지 여부를 저장하는 배열
    int[] parent = new int[6];    // 각 정점의 부모를 기록하는 배열 (경로 추적에 사용)
    int[] distance = new int[6];  // 시작 정점으로부터의 거리를 기록하는 배열

    Queue<int> q = new Queue<int>();  // BFS 탐색을 위한 큐 생성
    q.Enqueue(start);                 // 시작 정점을 큐에 삽입
    found[start] = true;              // 시작 정점을 방문 처리

    while (q.Count > 0)
    {
        int now = q.Dequeue();        // 큐에서 현재 정점을 꺼냄
        Console.WriteLine(now);       // 현재 방문한 정점을 출력

        for (int next = 0; next < 6; next++)
        {
            if (adj[now, next] == 0)  // 현재 정점과 연결되지 않은 정점은 건너뜀
                continue;

            if (found[next])          // 이미 방문한 정점은 건너뜀
                continue;

            q.Enqueue(next);          // 방문하지 않은 정점을 큐에 삽입
            found[next] = true;       // 해당 정점을 방문 처리
            parent[next] = now;       // 부모 정점 기록
            distance[next] = distance[now] + 1;  // 거리를 1 증가
        }
    }
}
}

1. BFS란?

✅ BFS(Breadth-First Search, 너비 우선 탐색) 개념

• BFS는 그래프 탐색 알고리즘 중 하나로, 출발 정점에서 가까운 정점부터 차례로 방문하는 방식이다.
• 큐(Queue)를 활용한 탐색으로, 선입선출(FIFO, First In First Out) 방식을 사용한다.
• 최단 거리 찾기에 자주 사용되며, 가중치가 없는 그래프에서 최단 경로를 구하는 데 유용하다.

---

2. BFS를 위한 그래프 표현 방법

2.1. 인접 행렬(Adjacency Matrix) 방식

class Graph
{
    int[,] adj = new int[6, 6]
    {
        { 0, 1, 0, 1, 0, 0 },
        { 1, 0, 1, 1, 0, 0 },
        { 0, 1, 0, 0, 0, 0 },
        { 1, 1, 0, 0, 1, 0 },
        { 0, 0, 0, 1, 0, 1 },
        { 0, 0, 0, 0, 1, 0 },
    };
}

✅ 설명

• adj[i, j] = 1이면 정점 i와 정점 j가 연결되어 있음을 의미한다.
• 모든 정점을 저장하기 때문에 메모리 사용량이 많지만, 특정 정점 간 연결 여부를 빠르게 확인할 수 있다.

---

2.2. 인접 리스트(Adjacency List) 방식

List<int>[] adj2 = new List<int>[]
{
    new List<int>() { 1, 3 },
    new List<int>() { 0, 2, 3 },
    new List<int>() { 1 },
    new List<int>() { 0, 1, 4 },
    new List<int>() { 3, 5 },
    new List<int>() { 4 },
};

✅ 설명

• 각 정점마다 연결된 정점들을 리스트로 저장한다.
• 메모리 효율성이 뛰어나며, 간선 수가 적을 때 유리하다.

---

3. BFS 구현

3.1. BFS 함수

public void BFS(int start)
{
    bool[] found = new bool[6];   // 방문 여부 체크 배열
    int[] parent = new int[6];    // 부모 정점 기록
    int[] distance = new int[6];  // 시작 정점으로부터 거리 저장

    Queue<int> q = new Queue<int>();  // BFS 탐색을 위한 큐
    q.Enqueue(start);                 // 시작 정점을 큐에 삽입
    found[start] = true;              // 방문 처리
    parent[start] = start;             // 출발지는 자기 자신을 부모로 설정
    distance[start] = 0;               // 출발지의 거리는 0

✅ 설명

• found[]: 방문 여부를 기록하여, 중복 방문을 방지한다.
• parent[]: 방문한 정점의 부모를 기록하여 경로를 추적할 수 있다.
• distance[]: 시작 정점으로부터의 최단 거리를 기록한다.
• 큐(Queue) 활용:
  • BFS는 큐(Queue)를 사용하여 탐색을 수행하며, 가장 먼저 삽입된 정점부터 탐색한다.

---

3.2. BFS 탐색 과정

    while (q.Count > 0)
    {
        int now = q.Dequeue();        // 현재 정점을 큐에서 꺼냄
        Console.WriteLine(now);       // 방문한 정점 출력

        for (int next = 0; next < 6; next++)
        {
            if (adj[now, next] == 0)  // 연결되지 않은 정점은 건너뜀
                continue;
            if (found[next])          // 이미 방문한 정점은 건너뜀
                continue;

            q.Enqueue(next);          // 방문하지 않은 정점을 큐에 삽입
            found[next] = true;       // 방문 처리
            parent[next] = now;       // 부모 정점 기록
            distance[next] = distance[now] + 1;  // 최단 거리 계산
        }
    }
}

✅ 설명

• 큐에서 정점 꺼내기: q.Dequeue()를 사용하여 가장 먼저 들어온 정점을 꺼내 방문한다.
• 인접한 정점 탐색:
  • adj[now, next] == 1인 경우만 방문 가능.
  • 이미 방문한 정점(found[next] == true)은 건너뜀.
• 거리 계산:
  • distance[next] = distance[now] + 1을 사용하여 최단 거리를 계산한다.
• 부모 기록:
  • parent[next] = now를 통해 경로 추적이 가능하도록 설정.

---

4. BFS 실행 및 결과

class Program
{
    static void Main(string[] args)
    {
        Graph graph = new Graph();
        graph.BFS(0);  // 0번 정점에서 BFS 탐색 시작
    }
}

• BFS(0)을 실행하면 0번 정점에서 시작하여 BFS 탐색을 진행한다.
• BFS 순회 결과:

  0 1 3 2 4 5

  • 0 → 1, 3 → 2, 4 → 5 순서로 탐색한다.

---

5. BFS의 작동 방식 요약

✅ BFS 탐색 원리

1. 시작 정점을 큐에 넣고 방문 처리.
2. 큐에서 정점을 하나씩 꺼내, 해당 정점과 연결된 미방문 정점들을 큐에 넣는다.
3. 각 정점의 부모와 최단 거리를 기록하여, 경로 추적 및 최단 거리 계산이 가능하게 한다.
4. 큐가 빌 때까지 이 과정을 반복하여 모든 정점을 방문한다.

---

6. BFS를 활용한 최단 경로 구하기

parent => 0 0 1 0 3 4
distance => 0 1 2 1 2 3

✅ 설명

• parent[] 배열:

  • parent[0] = 0: 정점 0의 부모는 자기 자신.
  • parent[1] = 0: 정점 1의 부모는 정점 0.
  • parent[2] = 1: 정점 2의 부모는 정점 1.
  • parent[3] = 0: 정점 3의 부모는 정점 0.
  • parent[4] = 3: 정점 4의 부모는 정점 3.
  • parent[5] = 4: 정점 5의 부모는 정점 4.

• distance[] 배열:

  • distance[0] = 0: 출발지인 정점 0.
  • distance[1] = 1: 정점 1까지 거리 1.
  • distance[2] = 2: 정점 2까지 거리 2.
  • distance[3] = 1: 정점 3까지 거리 1.
  • distance[4] = 2: 정점 4까지 거리 2.
  • distance[5] = 3: 정점 5까지 거리 3.

✅ BFS의 핵심

• BFS를 통해 각 정점까지의 최단 거리 정보를 저장할 수 있다.
• 가중치 없는 그래프에서 최단 경로를 찾을 때 유용하다.

---