[BFS] Breath-First Search (너비 우선 탐색)

목적

- Graph의 모든 Node를 Cycle(순환) 없이 탐색하는 방법 중 하나

- 같은 Node를 다시 탐색하지 않음

- 모든 Node를 한 번씩만 탐색

 

과정

1. 가장 위의 Node, Root Node에서 시작

2. 맨 위의 Node를 빼서 Queue에 넣은 후, 방문 표시(Visited True 표시)

3. 다음, 빼낸 Node와 바로 인접한 Node들을 빼서 Queue에 넣은 후, 방문 표시

4. 모든 Node들을 탐색할 때까지 3 반복

 

# pseudocode
create a queue Q 
mark v as visited and put v into Q 
while Q is non-empty 
    remove the head u of Q 
    mark and enqueue all (unvisited) neighbors of u

graph = {
  '5' : ['3','7'],
  '3' : ['2', '4'],
  '7' : ['8'],
  '2' : [],
  '4' : ['8'],
  '8' : []
}

visited = [] # List for visited nodes.
queue = []     #Initialize a queue

def bfs(visited, graph, node): #function for BFS
  visited.append(node)
  queue.append(node)

  while queue:          # Creating loop to visit each node
    m = queue.pop(0) 
    print (m, end = " ") 

    for neighbour in graph[m]:
      if neighbour not in visited:
        visited.append(neighbour)
        queue.append(neighbour)

# Driver Code
print("Following is the Breadth-First Search")
bfs(visited, graph, '5')    # function calling

 

 

출처

https://favtutor.com/blogs/breadth-first-search-python