Depth First Search(DFS) on Graph using Adjacency Matrix(Method 2)

Discover all the vertices on graph, print discover and finish time of each vertex using DFS


Category: Data Structure And Algorithms Tags: C#

DFS Code Files

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

Directed Graph
Fig 1: Directed Graph

Below is the Implementation of DFS.

static void DFS(int[,] edjMatrix, int[] discoverTime, int[] finishTime, char[] color, int[] parent)
{
    for (int u = 0; u < edjMatrix.GetLength(0); u++)
    {
        if (color[u] == 'w')
        {
            Visit(u, edjMatrix, discoverTime, finishTime, color, parent);
        }
    }
}
static int time = 0;
static void Visit(int u, int[,] edjMatrix, int[] discoverTime, int[] finishTime, char[] color, int[] parent)
{
    time++;
    discoverTime[u] = time;
    color[u] = 'g';

    for (int v = 0; v < edjMatrix.GetLength(1); v++)
    {
        if (edjMatrix[u, v] == 1 && color[v] == 'w')
        {
            parent[v] = u;
            Visit(v, edjMatrix, discoverTime, finishTime, color, parent);
        }
    }
    color[u] = 'b';
    time++;
    finishTime[u] = time;
}

Let's Talk about input parameters of above method.

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

Discover Time and Finish Time is maintained by DFS whenever a node is discovered we store discover time and whenever processing is finished of a vertex we store the time in finish time array. Each vertex's discover time and finish time is stored in arrays and can be retrieved using discoverTime[i], finishTime[i] where i=vertex

Color is maintained by DFS 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 DFS 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.

Below method will print discover and finish time of each of the vertex.

static void PrintDFS(int[] startTime, int[] endTime)
{
    for (int i = 0; i < startTime.Length; i++)
    {
        Console.WriteLine($"Vertex {i}, DiscoverTime {startTime[i]}, FinishTime {endTime[i]}");
    }
}

Running above code:

static void Main(string[] args)
{
    int numOfvertex = 5;
    int[,] edjMatrix = new int[numOfvertex, numOfvertex];
    edjMatrix[0, 2] = edjMatrix[0, 3] = 1;
    edjMatrix[1, 0] = edjMatrix[1, 3] = 1;
    edjMatrix[2, 3] = edjMatrix[2, 4] = 1;

    int[] discoverTime = new int[numOfvertex];
    int[] finishTime = new int[numOfvertex];

    char[] color = new char[numOfvertex];
    Array.Fill(color, 'w');

    int[] parent = new int[numOfvertex];
    Array.Fill(parent, int.MinValue);

    DFS(edjMatrix, discoverTime, finishTime, color, parent);
    PrintDFS(discoverTime, finishTime);
}

Output

Vertex 0, DiscoverTime 1, FinishTime 8

Vertex 1, DiscoverTime 9, FinishTime 10

Vertex 2, DiscoverTime 2, FinishTime 7

Vertex 3, DiscoverTime 3, FinishTime 4

Vertex 4, DiscoverTime 5, FinishTime 6

DFS in Action:

DFS Traversal
Fig 2: DFS Traversal

 


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