# StefanZero.com

Programming the web in San Francisco

# Graph Algorithms

Algorithms

## 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=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.