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:

## Comments: