그래프 탐색 - 너비 우선 탐색(BFS)

DFS는 스택을 사용해서 구현했었다

BFS는 큐를 사용한다!! 큐는 들어간 순서대로 나오는 거 FIFO

 

1) 큐가 비었나 확인(비었으면 모든 노드 다 방문한 거임. 탐색종료)

2) 큐에서 노드를 팝

3) 방금 막 팝한 노드 인접 노드 확인-> 그 중 방문 안한거 있으면 그 노드 큐에 푸쉬 후 방문 처리

 

1. 그림으로 보는 큐를 이용한 DFS

처음 1을 푸쉬하고 방문 처리

 

큐에 1이 있으니 안 비었고, 1을 팝한당 1의 인접 노드인 4,5 푸쉬

큐 안 비었으니 4팝한당. 4의 인접 노드인 2,3 push

큐 안 비었으니 5 팝한당 그리고 5의 인접 노드는 모두 방문했던 애들이니까 아무것도 안 함

큐 안 비었으니 2 팝한당 근디 2의 인접 노드는 모두 방문했던 애들이니 아무것도 안함.

2 팝한다음 3이 큐에 남아있으니 큐 안 비었음 그래서 3 팝함. 3의 인접노드들은 모두 방문했음

큐가 비었다 드뎌! 이제 탐색 종료~

 

2. 코드로 보는 큐로 구현한 DFS

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;


// 인접 리스트
vector<vector<int>> AdjList;
// 방문 여부
vector<bool> bVisited;

// BFS 함수
void BFS(int StartNode)
{
    queue <int> Q;
    
    Q.push(StartNode);
    bVisited[StartNode] = true;

    while (!Q.empty())
    {
        int Current = Q.front();
        Q.pop();
        cout << Current << " 방문" << endl;

        for (int NodesClosed : AdjList[Current])
        {
            if (!bVisited[NodesClosed])
            {
                Q.push(NodesClosed);
                bVisited[NodesClosed] = true;
            }
        }
    }
}
int main()
{
    int NodeCount = 5;                  // 그래프의 노드 개수
    AdjList.resize(NodeCount + 1);       // 인덱스 1부터 사용
    bVisited.resize(NodeCount + 1, false);

    // 간선 추가 (인접 리스트로 그래프 생성)
    AdjList[1] = { 4, 5 };
    AdjList[4] = { 2, 3 };
    AdjList[5] = { 1, 4 };
    AdjList[3] = { 2, 4 };
    AdjList[2] = { 3, 4 };

    // BFS 탐색 시작
    BFS(1);

	return 0;
}