Question

Write the pseudocode of the Depth First Search Algorithm DFS(G) using adjacencymatrix
representation of the graph G. What is the running time of your pseudocode?

Specification: start from the psedocode discussed in class and do only the modifications
needed for adjacency-matrix graph representation.

Below is the pseudocode discussed in class:

Answer 1

Pseudocode for Depth first search algorithm using adjacency matrix representation of graph G:

DFS(G, i)

1. Enter the number of vertices ‘n’ in the graph

2. Initialize an array G[i][j] and complete the adjacency matrix.

   For i=1 to n

   For j=1 to n

   Enter G[i][j]

3. Initialize visited[i] to zero.

4. Call procedure DFS(G,i)

5. Repeat steps 6 to 8 for ‘n’ times

6. Mark visited[i]=1

7. For j=1 to n

8. If (visited[j]==0 && G[i][j]==1) then call DFS(G,j)

   Running time of this pseudocode is O(n² ) where n is the number of vertices. As we can see in the pseudocode, function DFS(G,i) is called for every vertex and it executes ‘for loop’ for n times. So for n number of vertices, for loop will be executed n times. Thus it takes O(n*n)= O(n²) time.