TIL. 129 BFS (너비 우선 탐색)

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

그래프 탐색.

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

너비 우선 탐색.

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.BFS(너비 우선 탐색)이 DFS(깊이 우선 탐색)보다 좀 더 복잡하다.

너비 우선 탐색(BFS)의 특징.

직관적이지 않은 면이 있다.BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.BFS는 재귀적으로 동작하지 않는다.차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다.이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
선입선출(FIFO) 원칙으로 탄색‘Prim’, ‘Dijkstra’ 알고리즘과 유사하다.

너비 우선 탐색(BFS)의 과정

깊이가 1인 모든 노드를 방문하고 나서 그 다음에는 깊이가 2인 모든 노드를,
그 다음에는 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마친다.

BFS 알고리즘 파이썬 코드

def bfs(graph, start):
  visited = []
  queue = [start]
  while queue:
    n = queue.pop(0)
    if n not in visited:
      visited.append(n)
      queue += graph[n] - set(visited)
      print(visited)
  return visited

graph = {'A' : set(['B', 'C']),
        'B' : set(['A', 'D', 'E']),
        'C' : set(['A', 'F']),
        'D' : set(['B']),
        'E' : set(['B', 'F']),
        'F' : set(['C', 'E'])
}

start = 'A'

print(bfs(graph, start))

출처: https://blog.tomclansys.com/67?category=1066976 [톰 클란시의 IT 블로그:티스토리]