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

 Category: Data Structure And Algorithms Tags:

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.

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:

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