BFS And Shortest Path
Last time I talked about using Depth-First Search in C# for traversing graphs, such as networks, web pages, social networks, etc. In this article I will discuss Breadth-First Search, which is another graph search algorithm. Depth-first search is considered an aggressive algorithm, diving deep into the graph and backtracking only when it hits a dead end, only to dive deep once it finds the next available path. Breadth-first search, on the otherhand, is considered a more cautious algorithm. Rather than going deep, breadth-first search checks each path level-by-level, slowly reaching the depths of the graph.
Undirected Graph Modeled as Adjacency List
As with depth-first search, I will model the graph in C# as an adjacency list using a C# Dictionary. The keys are the vertices and the value of each vertex is its set of neighbors. In the example graph below, vertex 1 has neighbors 2 and 3, vertext 2 has 1 as a neighbor, and vertex 3 also has 1 as a neighbor.
The dictionary keys and values of the adjacency matrix will look as follows for this graph.
AdjacencyList = new Dictionary<T, HashSet<T>>();
{1:{2, 3}, 2:{1}, 3:{1}}
The larger Graph Class used in these examples contains the adjacency list and has a couple of helpers to add nodes and edges.
using System;
using System.Collections.Generic;
namespace KoderDojo.Examples {
public class Graph<T> {
public Graph() {}
public Graph(IEnumerable<T> vertices, IEnumerable<Tuple<T,T>> edges) {
foreach(var vertex in vertices)
AddVertex(vertex);
foreach(var edge in edges)
AddEdge(edge);
}
public Dictionary<T, HashSet<T>> AdjacencyList { get; } = new Dictionary<T, HashSet<T>>();
public void AddVertex(T vertex) {
AdjacencyList[vertex] = new HashSet<T>();
}
public void AddEdge(Tuple<T,T> edge) {
if (AdjacencyList.ContainsKey(edge.Item1) && AdjacencyList.ContainsKey(edge.Item2)) {
AdjacencyList[edge.Item1].Add(edge.Item2);
AdjacencyList[edge.Item2].Add(edge.Item1);
}
}
}
}
Breadth-First Search in C#
As mentioned before, breadth-first search visits its closest neighbors level-by-level when traversing the graph. The code for breadth-first search is nearly identical to depth-first search except we will be using a Queue instead of a Stack to make sure we visit the closest neighbors first. Here is an example of breadth-first search in C#.
using System.Collections.Generic;
namespace KoderDojo.Examples {
public class Algorithms {
public HashSet<T> BFS<T>(Graph<T> graph, T start) {
var visited = new HashSet<T>();
if (!graph.AdjacencyList.ContainsKey(start))
return visited;
var queue = new Queue<T>();
queue.Enqueue(start);
while (queue.Count > 0) {
var vertex = queue.Dequeue();
if (visited.Contains(vertex))
continue;
visited.Add(vertex);
foreach(var neighbor in graph.AdjacencyList[vertex])
if (!visited.Contains(neighbor))
queue.Enqueue(neighbor);
}
return visited;
}
}
}
To make sure the breadth-first search algorithm doesn't re-visit vertices, the visited HashSet keeps track of vertices already visited. A Queue, called queue, keeps track of vertices found but not yet visited. Initially queue contains the starting vertex. The next vertex is dequeued from queue. If it has already been visited, it is discarded and the next vertex is dequeued from queue. If it has not been visited, it is added to the set of visited vertices and its unvisited neighbors are added to queue. This continues until there are no more vertices in queue, and the set of vertices visited is returned. The set of vertices returned is all the vertices that can be reached from the starting vertex.
Again, the use of a Queue is what differentiates the code for breadth-first search from depth-first search, which uses a Stack. The queue causes breadth-first search to visit all neighbors level-by-level, slowly descending to the depths of the graph.
Breadth-First Search Example in C#
Given the following graph, use breadth-first search in C# to find all vertices that can be reached from 1.
using System;
namespace KoderDojo.Examples {
public class Program {
public static void Main(string[] args) {
var vertices = new[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
var edges = new[]{Tuple.Create(1,2), Tuple.Create(1,3),
Tuple.Create(2,4), Tuple.Create(3,5), Tuple.Create(3,6),
Tuple.Create(4,7), Tuple.Create(5,7), Tuple.Create(5,8),
Tuple.Create(5,6), Tuple.Create(8,9), Tuple.Create(9,10)};
var graph = new Graph<int>(vertices, edges);
var algorithms = new Algorithms();
Console.WriteLine(string.Join(", ", algorithms.BFS(graph, 1)));
# 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
}
}
}
Since all vertices can be reached by 1, all vertices are visited and returned by breadth-first search. Although the HashSet in C# doesn't guarantee an order, the order returned appears to be the exact path followed by breadth-first-search. Notice that breadth-first search cautiously checks each vertex level-by-level.
Start Level 0: 1
Traverse Level 1: 2, 3
Traverse Level 2: 4, 5, 6
Traverse Level 3: 7, 8
Traverse Level 4: 9, 10
Tracing the Path of Breadth-First Search in C#
If you want a list of the vertices as they are visited by breadth-first search, just add each vertex one-by-one to a list. Here is breadth-first search with an extra parameter, preVisit, which allows one to pass a function that gets called each time a vertex is visited.
public HashSet<T> BFS<T>(Graph<T> graph, T start, Action<T> preVisit = null) {
var visited = new HashSet<T>();
if (!graph.AdjacencyList.ContainsKey(start))
return visited;
var queue = new Queue<T>();
queue.Enqueue(start);
while (queue.Count > 0) {
var vertex = queue.Dequeue();
if (visited.Contains(vertex))
continue;
if (preVisit != null)
preVisit(vertex);
visited.Add(vertex);
foreach(var neighbor in graph.AdjacencyList[vertex])
if (!visited.Contains(neighbor))
queue.Enqueue(neighbor);
}
return visited;
}
Modify the client a bit to initiate a new list, called path, that gets updated each time a new vertex is visited. As you can see, the HashSet happens to be preserving the order that each vertex was inserted, but it is not guaranteed. A list is guaranteed to maintain its order.
using System;
using System.Collections.Generic;
namespace KoderDojo.Examples {
public class Program {
public static void Main(string[] args) {
var vertices = new[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
var edges = new[]{Tuple.Create(1,2), Tuple.Create(1,3),
Tuple.Create(2,4), Tuple.Create(3,5), Tuple.Create(3,6),
Tuple.Create(4,7), Tuple.Create(5,7), Tuple.Create(5,8),
Tuple.Create(5,6), Tuple.Create(8,9), Tuple.Create(9,10)};
var graph = new Graph<int>(vertices, edges);
var algorithms = new Algorithms();
var path = new List<int>();
Console.WriteLine(string.Join(", ", algorithms.BFS(graph, 1, v => path.Add(v)));
# 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Console.WriteLine(string.Join(", ", path));
# 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
}
}
}
Shortest Path Using Breadth-First Search in C#
Breadth-first search is unique with respect to depth-first search in that you can use breadth-first search to find the shortest path between 2 vertices. This assumes an unweighted graph. The shortest path in this case is defined as the path with the minimum number of edges between the two vertices.
In these cases it might be useful to calculate the shortest path to all vertices in the graph from the starting vertex, and provide a function that allows the client application to query for the shortest path to any other vertex. I've created a ShortestPathFunction in C# that does just this. It caculates the shortest path to all vertices from a starting vertex and then returns a function that allows one to query for the shortest path to any vertex from the original starting vertex.
Breadth-first search is being used to traverse the graph from the starting vertex and storing how it got to each node ( the previous node ) into a C# Dictionary, called previous. To find the shortest path to a node, the code looks up the previous node of the destination node and continues looking at all previous nodes until it arrives at the starting node. Since this will be the path in reverse, the code simply reverses the list and returns it.
public Func<T, IEnumerable<T>> ShortestPathFunction<T>(Graph<T> graph, T start) {
var previous = new Dictionary<T, T>();
var queue = new Queue<T>();
queue.Enqueue(start);
while (queue.Count > 0) {
var vertex = queue.Dequeue();
foreach(var neighbor in graph.AdjacencyList[vertex]) {
if (previous.ContainsKey(neighbor))
continue;
previous[neighbor] = vertex;
queue.Enqueue(neighbor);
}
}
Func<T, IEnumerable<T>> shortestPath = v => {
var path = new List<T>{};
var current = v;
while (!current.Equals(start)) {
path.Add(current);
current = previous[current];
};
path.Add(start);
path.Reverse();
return path;
};
return shortestPath;
}
The code return an IEnumerable<T>, which provides all the vertices that make up the shortest path to get from the starting vertex to the destination vertex. Here is some example code to show how it works.
using System;
namespace KoderDojo.Examples {
public class Program {
public static void Main(string[] args) {
var vertices = new[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
var edges = new[]{Tuple.Create(1,2), Tuple.Create(1,3),
Tuple.Create(2,4), Tuple.Create(3,5), Tuple.Create(3,6),
Tuple.Create(4,7), Tuple.Create(5,7), Tuple.Create(5,8),
Tuple.Create(5,6), Tuple.Create(8,9), Tuple.Create(9,10)};
var graph = new Graph<int>(vertices, edges);
var algorithms = new Algorithms();
var startVertex = 1;
var shortestPath = algorithms.ShortestPathFunction(graph, startVertex);
foreach (var vertex in vertices)
Console.WriteLine("shortest path to {0,2}: {1}",
vertex, string.Join(", ", shortestPath(vertex)));
# shortest path to 1: 1
# shortest path to 2: 1, 2
# shortest path to 3: 1, 3
# shortest path to 4: 1, 2, 4
# shortest path to 5: 1, 3, 5
# shortest path to 6: 1, 3, 6
# shortest path to 7: 1, 2, 4, 7
# shortest path to 8: 1, 3, 5, 8
# shortest path to 9: 1, 3, 5, 8, 9
# shortest path to 10: 1, 3, 5, 8, 9, 10
}
}
}
Conclusion
Both depth-first search and breadth-first search are basic graph algorithms, but quite useful for traversing graphs. At the minimum they will help you understand what vertices can find a path to other vertices ( connectivity ). This is useful for networks, websites, and social networks to name a few. In the case of an unweighted graph, breadth-first search will also find the shortest path.