Breadth First Search(BFS) on Graph using Adjacency Matrix(Method 2)

Discover all the vertices on graph, print path from source to destination and distance from source to destination using BFS


Category: Data Structure And Algorithms Tags: C#

BFS Code Files

    In previous BFS article I implemented BFS using Adjacency List also I created Vertex structure to hold data of each vertex. In this article I would use only arrays to implement BFS and this is going to be simplest implementation of BFS.

Note- I highly recommend you to read previous article to understand what is BFS, Adjacency Lists and Adjacency Matrices before starting this article because we are going to dive directly into implementation.

Below is the graph on which we are going to apply BFS.

Undirected Graph
Fig 1: Undirected Graph

 

In above graph we have 5 vertices and 6 edges, BFS can start from any of the given vertex we call it source vertex.

static void BFS(int source, int[,] adjMatrix, int[] distanceFromSource, char[] color, int[] parent)
{
    Queue<int> queue = new Queue<int>();
    queue.Enqueue(source);
    color[source] = 'g'; // color grey
distanceFromSource[source] = 0; while (queue.Count > 0) { var u = queue.Dequeue(); // vertex u for (int v = 0; v < adjMatrix.GetLength(1); v++) // vertex v { // Process only it was never discovered(color white) and edge is available between vertex u and v(adjacency-matrix[u,v]==1) if (adjMatrix[u, v] == 1 && color[v] == 'w') { color[v] = 'g'; // grey means node is discovered and in processing distanceFromSource[v] = distanceFromSource[u] + 1; // calculate distance from source by adding one in parent's distance from source parent[v] = u; queue.Enqueue(v); } } color[u] = 'b'; // black means node is processed } }

Let's Talk about input parameters of above method.

Source is a given vertex from where we have to start searching the graph.

Adjacency Matrix is n×n matrix where n is number of vertices, we have explained about Adjacency Matrix in detail in previous article.

Distance From Source is maintained by BFS whenever a node is discovered we calculate how far it is from source by just adding 1 in distance of it's parent. Each vertex's distance from source is stored in array and can be retrieved using distanceFromSource[i] where i=vertex

Color is maintained by BFS to know if a vertex is newly discovered(color white) or vertex is being processed(color grey) or already processed(color black). Each vertex's color is stored in array and can be retrieved using color[i] where i=vertex.

Parent is also maintained by BFS so later we can calculate traversal path from a source to a destination. Each vertex's parent is stored in array and can be retrieved using parent[i] where i=vertex.

We will write one method to print route from source to destination:

static void PrintBFSRoure(int[] parent, int source, int destination)
{
    if (source == destination)
        Console.WriteLine(source);

// Source will not have any parent hence source will remain int.MinValue
// So we will traverse it until source is reached if (parent[destination] != int.MinValue) { PrintBFSRoure(parent, source, parent[destination]); Console.WriteLine(destination); } }

Once we understand all above parameters algorithm becomes very simple. Using a queue we basically traverse through each vertex in graph and calculate the distance.

Running above code:

static void Main(string[] args)
{
    int numOfvertex = 5;
    int[,] adjMatrix = new int[numOfvertex, numOfvertex];
    adjMatrix[0, 1] = adjMatrix[0, 2] = adjMatrix[0, 3] = 1;
    adjMatrix[1, 0] = adjMatrix[1, 3] = 1;
    adjMatrix[2, 0] = adjMatrix[2, 3] = adjMatrix[2, 4] = 1;
    adjMatrix[3, 0] = adjMatrix[3, 1] = adjMatrix[3, 2] = 1;
adjMatrix[4, 2] = 1; int[] distanceFromSource = new int[numOfvertex]; Array.Fill(distanceFromSource, int.MinValue); char[] color = new char[numOfvertex]; Array.Fill(color, 'w'); int[] parent = new int[numOfvertex]; Array.Fill(parent, int.MinValue); int source = 1; int destination = 4; BFS(source, adjMatrix, distanceFromSource, color, parent); Console.WriteLine($"Distance between {source} and {destination} is {distanceFromSource[destination]}"); Console.WriteLine($"Path from {source} to {destination} is:"); PrintBFSRoure(parent, source, destination); }

Above I have created adjacency matrix for the graph, adjMatrix[n,m] = 1 means vertex n and m are connected(nm is a edge) else not.

Initialized distanceFromSource to integer's least value(negative) so once BFS runs it can fill calculated values and if it is not changed for a vertex means the verted has no connection to graph or source.

Initialized parent to integer's least value(negative) so once BFS runs it can fill parent values and if it is not changed for a vertex means the verted has no parent(Source vertex) or has no connection to source/graph. 

Initialized color to white for all vertices, Once BFS completed processing all the nodes color should be changed to black for all the vertices.

Output

Distance between 1 and 4 is 3

Path from 1 to 4 is:

1

0

2

4

BFS in Action:

Traversal from 1 to 4
Fig 2: Traversal from 1 to 4

 


Like 0 People
Last modified on 13 January 2022
Nikhil Joshi

Nikhil Joshi
Ceo & Founder at Dotnetlovers
Atricles: 158
Questions: 16
Given Best Solutions: 16 *

Comments:

No Comments Yet

You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x