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)
