BFS (Breadth-First Search)

BFS (Breadth-First Search)

✔ 그래프 탐색 알고리즘

탐색(Search)이란 많은 양의 데이터 내에서 원하는 데이터를 찾는 과정을 의미

 

✔ BFS

• 그래프에서 부모 노드를 먼저 방문한 후, 방문했던 부모 노드의 자식 노드를 차례로 탐색하는 알고리즘으로, 너비 우선 탐색이라고도 불림
• 선입선출 형태의 Queue자료구조 활용
• 트리일 경우 순회 방향 (번호 순서대로 진행)
• 시간복잡도 : O(V+E) 👉 V : 노드 수, E : 에지 수

BFS 순회

✔ 동작 과정

1️⃣ 탐색 시작 노드를 Queue에 삽입하고 방문 처리
2️⃣ Queue에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3️⃣ 2️⃣ 과정을 수행할 수 없을 때까지 반복

 

✔ 예시

1️⃣ 시작 노드 1을 Queue에 삽입하고 방문 처리
2️⃣ Queue에서 노드 1을 꺼내 방문하지 않은 인접 노드 2, 3, 8을 Queue에 삽입하고 방문 처리
3️⃣ Queue에서 노드 2를 꺼내 방문하지 않은 인접 노드 7을 Queue에 삽입하고 방문 처리
4️⃣ Queue에서 노드 3을 꺼내 방문하지 않은 인접 노드 4, 5를 Queue에 삽입하고 방문 처리
5️⃣ Queue에서 노드 8을 꺼냈지만 방문하지 않은 인접 노드가 없으므로 Queue에 인접 노드를 삽입하지 않고 진행
6️⃣ Queue에서 노드 7을 꺼내 방문하지 않은 인접 노드 6을 Queue에 삽입하고 방문 처리
7️⃣ 이후 Queue에서 노드 4, 5, 6을 차례로 꺼내고 모두 방문하지 않은 인접 노드가 없으므로 Queue에 더이상 삽입하지 않고 진행
Queue가 비어있으면 위의 과정들을 멈춤
👉 이러한 과정을 반복하였을 때 전체 노드의 탐색 순서(Queue에 삽입되었다가 나온 순서)는 1>2>3>8>7>4>5>6

 

 

✔ 슈도 코드(pseudocode)

G : 그래프
BFS(v) // v: 탐색 시작 정점

    Queue<>() q = new LinkedList<>();  // Queue 생성
    q.add(v);  // 시작 정점 v를 Queue에 삽입
    visited[v] ← TRUE  // v 방문 처리

    While (!q.isEmpty())
        t <- Queue의 첫 번째 원소 반환
        for (t와 연결된 모든 간선에 대해) {
            u <- t의 인접 정점
               if(!visited[u])  // u가 방문되지 않은 정점이라면
                q.add(u);  // u를 Queue에 삽입
                visited[u] = true;  // u 방문 처리