StefanZero.com

Programming the web in San Francisco

Graph Algorithms

Algorithms

Animated Breadth First Search

Press "Restart" to search connections from vertex "0" on a new random graph


Are We Connected?

The goal of the Breadth First Search (BFS) algorithm is to systematically and efficiently find all vertices in a graph that are connected to a given "source" vertex. In this animation, the source vertex is "Vertex 0", but could easily be specified as any of the vertices.

This animation starts with randomly creating 10 vertices at random positions, and then adding 12 distinct random connections (also called edges) to the graph. Since these edges are chosen at random, it is possible that some vertices on the graph may not be connected at all, or that there may be subgroups of vertices that are independently connected, yet not all of the vertices connected to each other.

The first step in BFS is to create an array of "flags", which is called marked, one for vertex, which indicate if that vertex is connected to the source vertex. Each value is initially set as marked[i]=false, except for the source vertex. Here we are starting from "Vertex 0", so marked[0]=true.

Next, we test, one by one, if each edge radiating from the source vertex makes a connection to a vertex that has not already been "discovered". Let's use the letter "j" to represent the vertex on the other end of the connecting edge. So if marked[j]=false, we then set marked[j]=true, to keep track of which vertices are connected to the source vertex. In this animation, the newly discovered connecting edge has its line style changed from dashed to solid, and its width increased, so we can clearly see which connections have been discovered.

After all the edges radiating from the source vertex have been explored, the process is repeated for each newly added vertex, in the order that they were discovered. So as you watch the animation, the region of discovered connections gradually radiates from the source vertex. The words "Breadth First Search" are used to express that the method expands the discovered region progressively from each previously recently discovered vertex. This algorithm also finds the shortest route (in terms of number of edges, not their length), from the source vertex to each connected vertex.

Python Program for Breadth First Search and Breadth First Paths

import sys class breadth_first_search: def __init__(self, g, s): if s < 0 or s >= g.V: raise ValueError( "breadth_first_search constructor error: s is out of range = " + str(s)) self.g = g self.s = s self.marked = [False] * g.V self.count = 0 self._bfs(g, s) def _bfs(self, g, s): queue = [s] self.marked[s] = True while queue: t = queue.pop(0) connections = g.adj[t] for i in connections: if not self.marked[i]: queue.append(i) self.marked[i] = True self.count += 1 def connected(self, v): return self.marked[v] def print_connections(self): print "bfs source vertex = %d" % self.s for i in range(0, self.g.V): if self.marked[i]: print str(i) def get_marked_list(self): marked_list = [] for i in range(0, self.g.V): if self.marked[i]: marked_list.append(i) return marked_list class breadth_first_paths: def __init__(self, g): self.g = g self.marked = [False] * g.V self._dist_to = [float("inf")] * g.V self.edge_to = [0] * g.V self.s = -1 def bfs(self, s): if s < 0 or s >= self.g.V: raise ValueError("breadth_first_search.bfs error: s is out of range = " + str(s)) self.s = s self.marked = [False] * self.g.V self._dist_to = [sys.maxint] * self.g.V self.edge_to = [0] * self.g.V self.marked[s] = True self._dist_to[s] = 0 queue = [s] while queue: v = queue.pop(0) for w in self.g.adj[v]: if not self.marked[w]: self.edge_to[w] = v self._dist_to[w] = self._dist_to[v] + 1 self.marked[w] = True queue.append(w) def has_path_to(self, v): return self.marked[v] def dist_to(self, v): return self._dist_to[v] def path_to(self, v): path = [] if self.has_path_to(v): x = v while self._dist_to[x] != 0: path.append(x) x = self.edge_to[x] path.append(x) return path def print_bfp(self): if self.s == -1: print "source vertex has not been set" return print "source vertex = " + str(self.s) for v in range(0, self.g.V): if self.has_path_to(v): message = "%d to %d (%d): " % (self.s, v, self.dist_to(v)) path = self.path_to(v) path.reverse() for w in path: if w == self.s: message += " %d" % w else: message += " - %d" % w print message else: print "%d to %d (-): not connected"