BFS

25 Jul 2022 in Study / Computer science on Bfs

Algorithm

• Breadth First Search for graph
  
• can be used for the shortest distance
  

Implementation

• by queue
  • FIFO (First in, First Out)
  • deque (bidirectional queue) : efficient

    from collections import deque
    q = deque()
    q.append(1)  # [1]
    q.append(2)  # [1, 2]
    q.popleft()  # [2]
    

• Procedure
  1. node → queue
  2. A node escapes from queue
  3. This node is marked “visited”
  4. All adjacent nodes of this node are processed by first step simultaneously (repeating)
     
• Mark “visited”
  • example 1
    

    graph[i][j] = 0 # originally 1
    

  • example 2
    

    visited = []
    visited.append(/*specific node*/)
    if node not in visited:
    # statement
    

Pseudocode

from collections import deque

def BFS(graph, start_node):
  visited = []
  need_visit = deque()
  need_visit.append(start_node)

  while need_visit:
    node = need_visit.popleft()
    visited.append(node)

    ## movement toward adjacent nodes of the node
    if adjacent_node not in visited:
      need_visit.append(adjacent_node)

Shortest Distance

• We can use “distance[]” instead of “visited[]”

Pseudocode

from collections import deque

def BFS(graph, start_node):
  distance = [-1] * (len(graph) + 1)    # visited node != -1
  distance[start_node] = 0 # The start point's distance = 0
  need_visit = deque()
  need_visit.append(start_node)

  while need_visit:
    node = need_visit.popleft()  # current node

    ## movement toward adjacent nodes of the node
    if distance[adjacent_node] == -1:
      distance[adjacent_node] = distance[node] + 1
      need_visit.append(adjacent_node)