# Depth Firtst Search(DFS) Algorithm Explanation and Implementation in C++

Discovery Time and Finishing Time Code:

//dfs using adjacency list in directed graph
#include<iostream>
using namespace std;
int WHITE=1,GREY=2,BLACK=3,INF=310000,NIL=-1;
int num_v,num_e,time=0;
void DFS_visit(int);
void initialization()
{
int k,j;
for(k=0; k<20; k++)
{
for(j=0; j<20; j++)
{
}
}

}
{
int i,a,b;
cout<<"Enter number of vertices: "<<endl;
cin>>num_v;
cout<<"Enter number of edges: "<<endl;
cin>>num_e;
cout<<"Enter edges: "<<endl;
for(i=1; i<=num_e; i++)
{
cin>>a>>b;
}
}
void dfs()
{
int i,u;
for(i=1; i<=num_v; i++)
{
color[i]=WHITE;
p[i]=NIL;
}
for(u=1; u<=num_v; u++)
{
if(color[u]==WHITE)
{
DFS_visit(u);
}
}
}
void DFS_visit(int u)
{
int i,v;
color[u]=GREY;
time=time+1;
d[u]=time;
for(v=1; v<=num_v; v++)
{
{
if(color[v]==WHITE)
{
p[v]=u;
DFS_visit(v);
}
}
}
color[u]=BLACK;
time=time+1;
f[u]=time;
}
void distance_output()
{
int i;
cout<<"Discovery time and finish time:\n";
for(i=1; i<=num_v; i++)
{
cout<<"Node "<<i<<" is "<<d[i]<<"/"<<f[i]<<" \n";
}
}
int main()
{
initialization();
dfs();
distance_output();
return 0;
}

input/output:

Enter number of vertices:
4
Enter number of edges:
4
Enter edges:
2 3
2 1
1 4
3 4
Discovery time and finish time:
Node 1 is 1/4
Node 2 is 5/8
Node 3 is 6/7
Node 4 is 2/3

pseudo:

void DFS_visit(int u){
int i,v;
colour[u]=GREY;
time=time+1;
d[u]=time;
for(v=1;v<=num_v;v++)
{
if(color[v]==WHITE){
p[v]=u;
DFS_visit(v);
}
}

}
color[u]=BLACK;
time=time+1;
f[u]=time;
}

Pseudocode from shafayet vai’s blog:

procedure DFS(G, source):
U ← source
time  ← time+1
d[u]  ← time
color[u]  ← GREY
for all edges from u to v in G.adjacentEdges(v) do
if color[v] = WHITE
DFS(G,v)
end if
end for
color[u] ← BLACK
time ← time+1
f[u] ← time
return

Another code to find the order of the node:
References:
CLRS website: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm

Shafayet Ashraf: http://www.shafaetsplanet.com/planetcoding/?p=973

and here is also a good implementation:

Java array basics: http://www.tutorialspoint.com/java/java_arrays.htm

Another code to find the order of vertices:

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;

main()
{
int m;
cout <<"enterno of vertices";
cin >> n;
cout <<"ente no of edges";
cin >> m;
cout <<"\nEDGES \n";
for(k=1; k<=m; k++)
{
cin >>i>>j;
}

cout <<"enter initial vertex:";
cin >>v;
cout <<"ORDER OF VISITED VERTICES: ";
cout << v <<" ";
visited[v]=1;
k=1;
while(k<n)
{
for(j=n; j>=1; j--)
{
visit[j]=1;
stk[top]=j;
top++;
}
v=stk[--top];
cout<<v << " ";
k++;
visit[v]=0;
visited[v]=1;
}
}

It would be a great help, if you support by sharing :)
Author: zakilive