BFS(Breadth-first-search) 넓이 우선 탐색

정의

BFS란 트리나 그래프 자료구조를 서칭하는데 사용되는 기법이다. 루트노드에서 시작해서 다음노드로 이동하기 전에 현재 깊이의 모든 인접 노드를 탐색하는 방식으로 진행된다.

 

Python Code

G는 Graph, v는 이미 방문한 지역을 나타내는 마커라고 할 때 다음과 같이 나타 낼 수 있다.

 

marked = [False] * G.size()
 
def bfs(G, v):
    queue = [v]
    while len(queue) > 0:
        v = queue.pop(0)
        if not marked[v]:
            visit(v)
            marked[v] = True
            for w in G.neighbors(v):
                if not marked[w]:
                    queue.append(w)

활용처

1. 연결된 요소 찾아내기

2. 출구가 하나만 있는 미로 퍼즐 해결

3. 랜덤 DFS 서치를 활용한 미로 생성

4. Flood fill

 

 

---

Reference

https://www.youtube.com/watch?v=xlVX7dXLS64