Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C#

Solution: Breadth-First Graph Traversal

Explore the breadth-first search (BFS) algorithm and learn how to implement this graph traversal method effectively. Discover how BFS visits nodes layer by layer, uses a queue to avoid revisiting nodes, and understand its time complexity of O(V + E). This lesson prepares you to handle graph traversal problems in coding interviews with confidence.

We'll cover the following...

Solution

BFS
Graph.cs
class Program
{
    /// <summary>
    /// Method to print a BFS of a graph.
    /// </summary>
    /// <param name="graph">The graph.</param>
    /// <param name="source">Starting vertex.</param>
    public static string BFS(Graph myGraph, int source)
    {
        // Mark all the vertices as not visited
        int V = myGraph.V;
        bool[] visited = new bool[V];
        // Create a queue for BFS
        Queue<int> queue = new Queue<int>();
        // Result string
        string result = "";
        // Mark the source node as
        // visited and enqueue it
        queue.Enqueue(source);
        visited[source] = true;
        while (queue.Count > 0)
        {
            // Dequeue a vertex from
            // queue and print it
            source = queue.Dequeue();
            result += source;
            AdjNode temp = myGraph.graph[source];
            // Get all adjacent vertices of the
            // dequeued vertex source. If a adjacent
            // has not been visited, then mark it
            // visited and enqueue it
            while (temp != null)
            {
                int data = temp.Vertex;
                if (!visited[data])
                {
                    queue.Enqueue(data);
                    visited[data] = true;
                }
                temp = temp.Next;
            }
        }
        return result;
    }
    // Main to test the above program
    public static void Main(string[] args)
    {
        int V = 5;
        Graph g = new Graph(V);
        g.AddEdge(0, 1);
        g.AddEdge(0, 2);
        g.AddEdge(1, 3);
        g.AddEdge(1, 4);
        Console.WriteLine(BFS(g, 0));
    }
}

Explanation

In this algorithm, we begin from a selected node (it can be a root node) and traverse the graph layerwise (one level at a time). We explore all neighbor nodes (those connected to the source node) before moving to the next level of neighbor nodes.

As the name breadth-first suggests, we traverse the graph by moving horizontally, visiting all the nodes of the current layer, and moving to the next layer.

Avoid visiting the same nodes again

A graph can contain cycles, which will lead to visiting the same node again and again, while we traverse the graph. To avoid processing the same node again, we can use a boolean array that marks visited arrays.

To make this process easy, we use a queue to store the node and mark it as visited until all its neighbors (vertices that are directly connected to it) are marked.

Note: The queue follows the First In, First Out (FIFO) queuing method. Therefore, neighbors of the node will be visited in the order in which they were inserted in the queue, i.e., the ...