[알고리즘] 너비 우선 탐색 BFS(Breath-First-Search)-C++

BFS

BFS(Breath-First-Search) : 너비 우선 탐색

같은 자식 레벨은 다 탐색하고 다음 레벨의 자식으로 넘어간다.

1. root 노드부터 먼저 검색
2. level 1의 모든 노드 검색(왼쪽 노드부터 오른쪽 노드로)
3. level 2…leaf마디 까지 모든 노드 검색

사용 : 그래프(최단 거리 구하기), 트리(트리를 레벨별로 탐색) 자료구조 탐색에 사용

🎯EX

1. 루트노드 1을 큐에 넣는다.
2. 1을 큐에서 꺼내고 인접 노드 2,3을 모두 큐에 넣는다.( 1 방문 처리)
3. 2를 큐에서 꺼내고 인접노드 4,5를 모두 큐에 넣는다.( 1 방문 처리)
4. 3을 큐에서 꺼내고 인접노드 6,7을 모두 큐에 넣는다.
5. 4를 큐에서 꺼내고 인접노드 8,9를 모두 큐에 넣는다.t
6. 5를 큐에서 꺼내고 인접노드 10을 큐에 넣는다.
7. 큐에 있는 노드들에 대해 같은 과정을 반복하고 큐가 비면 반복 종료

🌟 노드를 방문 하는 순서 : 1→2→3→…→10

구현

• 재귀 알고리즘을 구현하기는 어렵기 때문에 Queue를 사용해 구현
  • 시작 정점을 큐에 넣는다.( 큐에 들어간 노드는 방문 처리)
  • 큐에서 정점을 하나씩 꺼내면서 해당 정점에 인접한 정점들을 모두 큐에 넣는다.
  • 큐에서 다음으로 꺼낼 정점을 선택, 이 과정을 큐가 빌 때까지 반복(탐색 안한 노드가 없을 때까지)
• 이미 방문한 노드에 대해서는 방문 처리를 해야한다. 그렇지 않으면 무한루프에 빠지게 된다.
  

🧀 BFS에서 재귀 알고리즘을 구현하기 어려운 이유

• 너비우선 탐색은 level 별로 순차적으로 탐색을 진행하기 때문에 재귀적으로 호출될 때마다 해당 레벨을 추적하고 제어하기 어렵다.
• 재귀 호출은 함수 호출에 따른 오버헤드가 발생할 수 있다. queue를 사용한 반복적인 방식(iterative approach)에서는 이러한 오버헤드가 없으므로 더 효율적이다.

의사 코드

void breadth_first_search(tree T) {
	queue_of_node Q;
	node u, v;
	initialize(Q); // 큐 Q가 비도록 초기화
	v = root of T;//루트 노드 v
	visit v;//v 방문
	enqueue(Q,v);//v를 큐에 추가
	while(!empty(Q)) {//큐에 들어온 노드가 있다면
		dequeue(Q,v);//해당 노드를 큐에서 제거하고
		for(each child u of v) {//v의 자식들 u에 대해
			visit u;//u 방문
			enqueue(Q,u);//큐에 추가
		}
	}
}

C++ 구현

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

using namespace std;

// 그래프의 정점을 표현하는 구조체
struct Node {
    int data;
    vector<Node*> neighbors;
    bool visited; // 방문 여부를 나타내는 변수
};

// 너비우선 탐색 함수
void breadth_first_search(Node* start) {
    queue<Node*> q;

    // 시작 정점을 큐에 넣고 방문 처리
    q.push(start);
    start->visited = true;

    while (!q.empty()) {
        // 큐에서 정점을 하나씩 꺼냄
        Node* current = q.front();
        q.pop();
        
        // 현재 정점 방문
        cout << "Visiting node: " << current->data << endl;

        // 현재 정점의 모든 인접한 정점들에 대해
        for (Node* neighbor : current->neighbors) {
            // 인접한 정점이 방문되지 않았다면 큐에 넣고 방문 처리
            if (!neighbor->visited) {
                q.push(neighbor);
                neighbor->visited = true;
            }
        }
    }
}

int main() {
    // 그래프 생성
    Node* node1 = new Node{1, {}, false};
    Node* node2 = new Node{2, {}, false};
    Node* node3 = new Node{3, {}, false};
    Node* node4 = new Node{4, {}, false};

    // 그래프의 간선 설정
    node1->neighbors.push_back(node2);
    node1->neighbors.push_back(node3);
    node2->neighbors.push_back(node4);
    node3->neighbors.push_back(node4);

    // 너비우선 탐색 실행
    breadth_first_search(node1);

    return 0;
}