Breadth First Search (BFS) in a Graph

Breadth first search is an algorithm which searches or traverses all the vertices in a graph. It starts to traverse the graph based on a start vertex. The algorithm traverses the vertices from closest ones to farthest ones.

As graphs can have cycles we should not visit any visited vertex twice. For this purpose the algorithm must know if a vertex is visited and it shouldn’t visit it again. To implement the algorithm usually a helper queue is used. Let’s have a look at an example to better understand how the algorithm works.

Let’s say that we have the simple graph above and we want to traverse the graph by starting from vertex A.

At this point we have traversed all the vertices in the graph, so the BFS algorithm finishes.

Implementation

Lets first create a simple vertex class which will represent the vertices in a graph.

    public class Vertex
    {
        public Vertex(string name)
        {
            this.Name = name;
        }

        public string Name { get; set; }

        public bool IsVisited { get; set; }
    }

Next let’s create a graph class that will implement BFS algorithm.

    public class Graph
    {
        // Adjacency list which will keep the connections between vertices
        private readonly Dictionary<Vertex, List<Vertex>> adjLists;

        public Graph()
        {
            adjLists = new Dictionary<Vertex, List<Vertex>>();
        }

        // Add edge between src---->dest vertices
        public void AddEdge(Vertex src, Vertex dest)
        {
            if (this.adjLists.ContainsKey(src))
            {
                this.adjLists[src].Add(dest);
            }
            else
            {
                this.adjLists.Add(src, new List<Vertex> { dest });
            }
        }

        // Applying BFS algorithm and returning a list of traversed vertices 
        public List<Vertex> Bfs(Vertex source)
        {
            List<Vertex> result = new List<Vertex>();

            Queue<Vertex> vertexQueue = new Queue<Vertex>();

            vertexQueue.Enqueue(source);

            while (vertexQueue.Count > 0)
            {
                var vertex = vertexQueue.Dequeue();
                vertex.IsVisited = true;
                result.Add(vertex);

                // Add all unvisited adjacency vertices of currently 
                // visited vertex into the queue
                foreach (var v in this.adjLists[vertex])
                {
                    if (!v.IsVisited)
                    {
                        vertexQueue.Enqueue(v);
                    }
                }
            }

            return result;
        }
    }

Finally we will construct the graph from the example above and run the BFS algorithm on it to show the order in which the vertices will be visited.

        static void Main(string[] args)
        {
            var graph = new Graph();

            var vA = new Vertex("A");
            var vB = new Vertex("B");
            var vC = new Vertex("C");
            var vD = new Vertex("D");
            var vE = new Vertex("E");

            graph.AddEdge(vA, vB);
            graph.AddEdge(vA, vC);
            graph.AddEdge(vA, vD);

            graph.AddEdge(vB, vA);

            graph.AddEdge(vC, vA);
            graph.AddEdge(vC, vE);

            graph.AddEdge(vD, vA);

            graph.AddEdge(vE, vC);

            var traversed = graph.Bfs(vA);

            foreach (var t in traversed)
            {
                Console.Write($"{t.Name} ");
            }
        }

When we run the console app the result will be:

A B C D E

The time complexity of the BFS algorithm is O(V + E), where V is the number of vertices and E is the number of edges.