너비 우선 탐색

1. 개요

1. 루트에서 시작한다.
2. 자식 노드들을 [1]에 저장한다.[1]
3. [1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다.
4. [2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다.
5. 위의 과정을 반복한다.
6. 모든 노드를 방문하면 탐색을 마친다.

2. 특징

3. 소스 코드로의 구현

3.1. C++

#!syntax cpp
const int MAX = 100'001;

queue<int> q;
bool visited[MAX]; // 방문 배열. visited[node] = true이면 node는 방문이 끝난 상태이다.

void bfs(const vector<int> graph[], int source) { // graph는 인접 리스트, source는 시작 노드
    // source 방문
    q.push(source);
    visited[source] = true;

    while(!q.empty()) { // 큐가 빌 때까지 반복
        // 큐에서 노드를 하나 빼 온다. 이 노드를 current라고 하자.
        int current = q.front();
        q.pop();

        for(int next: graph[current]) { // current의 인접 노드들을 확인한다. 이 각각의 노드를 next라고 하자.
            if(!visited[next]) { // 만일 next에 방문하지 않았다면
                // next 방문
                q.push(next);
                visited[next] = true;
            }
        }
    }
}

3.2. Python

#!syntax python
def bfs(graph:Dict, start:int): # Dict 자료형 형태로 준다. key는 노드, value는 인접노드를 가리킨다.
    visited = {i:False for i in graph.keys()} # 방문 배열. visited[node] = True이면 node는 방문이 끝난 상태이다.
    queue = [start]
    visited[start] = True
    while len(queue) > 0: # 큐가 빌 때까지 반복
        current = queue.pop(0) #queue에서 노드를 하나 빼 온다. 이 노드를 current라고 하자.
        for nxt in graph[current]: # current의 인접 노드들을 확인한다. 이 각각의 노드를 nxt라고 하자.
            if not visited[nxt]: # 만일 nxt에 방문하지 않았다면
                #nxt 방문
                queue.append(nxt)
                visited[nxt] = True

4. 같이보기

• 최선 우선 탐색
• 깊이 우선 탐색