너비 우선 탐색(Breadth-First-Search)

BFS

그래프 전체를 탐색하는 방법 중 하나로, 루트 노드 또는 다른 임의의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법입니다.

시작 정점을부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 순회함으로 써 노드를 넓게(wide)하게 탐색을 합니다.

 

더 설명하자면,

BFS는 해를 찾아서 조직적으로 트리의 모든 노드들을 검사하는 무정보 탐색(Uniformed search)입니다.

달리 말하자면, 목표에 대한 고려없이 목표가 발견될 때까지 전체 트리 또는 그래프를 전부 탐색하고,

BFS는 휴리스틱을 사용하지 않습니다.

(반대로 휴리스틱을 사용하는 알고리즘은 ex) Greedy best-first search 또는 A*)

 

👇 search 의 두 분류

---

Uniformed search

• BFS (Breath - first)
• DFS (Depth - first)
• Brute Force
• Hill climbing
• Dijkstra

Informed Search

• Greedy Best First Search ( huristics )
• A*

---

주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때, 이 방법을 사용합니다.

큐(Queue) 자료구조를 활용하여, 인접한 노드를 반복적으로 삽입하고, 먼저 삽입된 노드부터 차례대로 큐에서 꺼내도록 알고리즘으로 작성하여 구현되는 알고리즘입니다.

 

👇 Heuristic 이란?

---

*휴리스틱(heuristic)

휴리스틱(heuristics) 또는 발견법(發見法)이란 불충분한 시간이나 정보로 인하여 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서 사람들이 빠르게 사용할 수 있게 보다 용이하게 구성된 간편추론의 방법입니다.

=> '대충 어림 짐작하기'라는 의미로 생각하면 됩니다.

ex) A* 알고리즘에서 거리 계산할 때, 정확한 값이 아닌 휴리스틱 추정값을 사용해서 구현합니다.

---

 

 

 

BFS 특징

• 최단 경로를 찾을 때 사용합니다
• 일반적으로 큐(queue) 하여 선입선출 형태로 탐색합니다..
• 재귀적으로 동작하지 않습니다.
• 어떤 노드를 방문했는 지 검사해야 합니다.

 

 

BFS 장단점

장점

• 노드 의 수가 적고 깊이가 얕은 경우 빠르게 동작합니다.
• 단순 검색 속도가 깊이 우선 탐색보다 빠릅니다.
• 너비를 우선 탐색하기에 답이 되는 경로가 여러 개인 경우에도 최단 경로를 보장합니다.
• 최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있습니다.

단점

• 재귀호출의 DFS와는 달리 큐에 다음 정점들을 저장해야 하므로, 저장공간이 많이 필요합니다.
• 노드의 수가 늘어나면, 탐색해야하는 노드 또한 많아져 시간이 오래걸립니다.

 

 

BFS와 DFS 비교

BFS

• 초기 노드에서 시작하여 모든 자식 노드를 확장하여 생성
• 생성된 노드 순서대로 확장(queue)
• 메모리 효율적이지 못함
• 최적해 보장

DFS

• 해가 존재할 가능성이 존재하는 한 앞으로 전진(깊이 방향으로 탐색)
• 최근에 생성된 노드를 다시 확장
• 메모리 효율적
• 최적해 보장하지 못함

 

 

BFS 구현 방식

Input : 그래프 G, G의 정점 v

Output : v로 부터 탐색 가능한 모든 정점들

BFS(G, start_v)
    let Q be a Queue // Q라는 큐를 하나 생성
    label start_v as discovered // 시작정점을 탐색 완료 표시
    Q.enqueue(start_v) // 큐에 시작 정점을 추가하기
    
    // 큐 안에 정점이 다 없을 때까지 구현부 반복합니다
    while Q is not empty do
        v := Q.dequeue() // 현재 탐색하고 있는 정점을 v에 넣습니다.
        
        // 만약 목표한 v에 도착할 경우 return 을 시킵니다.
        if v is the goal then
            return v
            
        // 현재 정점 v의 모든 인접한 정점 w에 대하여
        for all edges from v to w in G.adjacenctEdges(v) do
        	// 만약 w가 탐색이 되어있지 않다면?
            if w is not labeled as discovered then
                lavel w as discovered // 인접 정점 w를 탐색완료 표시를 합니다.
                w.parent := v // * 문제마다 다르게 구현해야할 부분(?)
                Q.enqueue(w) // 큐에 인접 정점을 넣습니다

 

그래프에서 어떤식으로 움직일까요?

 

 

위의 그래프에서 BFS는 A에서 출발하면,

왼쪽 edge를 오른쪽의 edge보다 먼저 선택한다고 가정하면 방문 순서는

A, B, C, E, D, F, G 입니다.

 

BFS 시간복잡도

정점의 수가 n 개이고, 간선의 수가 e인 그래프의 경우

• 그래프가 인접 리스트로 표현된 경우 O(n+e)
• 그래프가 인접 행렬로 표현된 경우 O(n²)