Algorithms for Coding Interviews in C#/

...

/

Solution: Breadth-First Graph Traversal

Solution: Breadth-First Graph Traversal

Learn how to implement the breadth-first traversal of a graph.

We'll cover the following...

Solution

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