Dot Net For All

Breadth First Search(BFS) in C#

Vikram Chaudhary

Hello Friends, In this article I will discuss one of the two traversing mechanisms used for tree and graphs. I will cover breadth first search(BFS) with C# example. Graphs is one of the most challenging and complex data structure.

How Breadth First Search Works

Breadth-first search (BFS) is a method for exploring a tree or graph. In a BFS, you first explore all the nodes one step away, then all the nodes two steps away, etc.

If we are well known to the Breadth First Search it would be very easy to understand system design concepts and crack interview questions.

Breadth-first search is like throwing a stone in the center of a pond. The nodes you explore “ripple out” from the starting point.

Here’s a how a BFS would traverse this tree, starting with the root:

Breadth First First Traversal in a tree

In the first image of above figure we have started with a the top most node.

In the second image, we traverse all the nodes present at the second level. In the third image all the nodes present at the third level and so on. Untill we reach the end.

Advantages:

Disadvantages

Breadth First Search Code Example in C#

In the below code I have tried to create the same structure as shown in the figure below.

static void Main(string[] args)
        {
             IDictionary<int, List<int>> tree = new Dictionary<int, List<int>>();
            tree[1] = new List<int> { 2, 3, 4 };
            tree[2] = new List<int> { 5 };
            tree[3] = new List<int> { 6, 7 };
            tree[4] = new List<int> { 8 };
            tree[5] = new List<int> { 9 };
            tree[6] = new List<int> { 10 };
            HashSet<int> itemCovered = new HashSet<int>();
            Queue queue = new Queue();
            queue.Enqueue(tree.ElementAt(0).Key);
            while (queue.Count > 0)
            {
                var element = queue.Dequeue();
                if (itemCovered.Contains(Convert.ToInt32(element)))
                    continue;
                else
                    itemCovered.Add(Convert.ToInt32(element));
                Console.WriteLine(element);
                List<int> neighbours;
                tree.TryGetValue(Convert.ToInt32(element), out neighbours);
                if (neighbours == null)
                    continue;
                foreach (var item1 in neighbours)
                {
                    queue.Enqueue(item1);
                }
            }
        }
}

I am doing following steps in above code to traverse the tree:

  1. First move horizontally and visit all the nodes of the current layer
  2. Move to the next layer

I am using a queue to push the item being traversed and adding all the neighbors of the item in queue. And once traversed popping them out.

And the output of the above code would be as shown in the figure below:

BFS Problem

Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

Solution:

As part of the solution we will be traversing all the nodes at one level and try to find the max node.

  1. Add the root node to queue.
  2. Traverse the queue till the time it is empty.
  3. Get the count of elements in queue.
  4. Traverse the elements till the count.
  5. Get the max in the inner loop.
 public int[] FindLargestValueinEachTreeRowMethod(TreeNode root)
        {
            List<int> result = new List<int>();
            if (root == null) return result.ToArray();

            Queue<TreeNode> dfs_queue = new Queue<TreeNode>();
            dfs_queue.Enqueue(root);

            while (dfs_queue.Count > 0)
            {
                int max_value = Int32.MinValue;
                int elements_count = dfs_queue.Count;

                for (int i = 0; i <= elements_count; i++)
                {
                    TreeNode node = dfs_queue.Dequeue();
                    max_value = Math.Max((int)max_value, (int)node.val);
                    if (node.left != null) dfs_queue.Enqueue(node.left);
                    if (node.right != null) dfs_queue.Enqueue(node.right);
                }

                result.Add(max_value);
            }

            return result.ToArray();
            
        }

Practical Use of Breadth First Search

I have been asked a very useful and interesting programming interview question related to BFS. Below is the question.

You’re given a grid map of subway stations, write a function which outputs the distance from each road intersection to the nearest station.You cannot move diagonally while going from one point to another. The answer is bit complex and not very difficult.

input:

. . . . . X
. . . . . .
. . . . . .
. X . . . .
. . . . X .

output:

4 3 3 2 1 0
3 2 3 3 2 1
2 1 2 3 2 2
1 0 1 2 1 2
2 1 2 1 0 1

You may also like to know two interesting ways to solve depth first search(DFS) in C#.

References:

Using Advanced Data Structures in Modern Applications
Algorithms and Data Structures – Part 1

Top career enhancing courses you can't miss

My Learning Resource

Excel your system design interview