Monday, September 17, 2018

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)


No comments:

Post a Comment