Simplified Breadth-first Search

Simplified Breadth-first Search

Given a graph G = (V, E) and a distinguished source vertex s, breadth-first search systematically explores the edges of G to “discover” every vertex that is reachable from s. It computes the distance (smallest number of edges) from s to each reachable vertex. It also produces a “breadth-first tree” with root s that contains all reachable vertices. For any vertex reachable from s, the simple path in the breadth-first tree from s to corresponds to a “shortest path” from s to v in G, that is, a path containing the smallest number of edges. The algorithm works on both directed and undirected graphs.

Python

class Graph:

  def __init__(self, nodes):

      self.nodes = nodes

      self.edges = 0

      self.adj = [[] for i in range(self.nodes)]

  def addEdge(self, v, w):

      self.adj[v].append(w)

      self.edges += 1

  def bfs(self, startingNode):

      from queue import Queue

      seen = [False for i in range(self.nodes)]

      q = Queue()

      q.put(startingNode)

      while not q.empty():

          node = q.get()

          print(node, end=", ")

          seen[node] = True

          for neighbour in self.adj[node]:

              if not seen[neighbour]:

                  q.put(neighbour)