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;
int adj[20][20],color[20],p[20],d[20],f[20];
void DFS_visit(int);
void initialization()
{
    int k,j;
    for(k=0; k<20; k++)
    {
        for(j=0; j<20; j++)
        {
            adj[k][j]=0;
        }
    }

}
void build_adj_matrix()
{
    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;
        adj[a][b]=1;
    }
}
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(adj[u][v]==1)
        {
            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();
    build_adj_matrix();
    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(adj[u][v]==1){
			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

 

Reference:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm
http://www.dotnetlovers.com/Article/182/implementation-of-depth-first-searchdfs

Another code to find the order of the node:
References:
One of my classmates blog link: http://programminghelpbd.blogspot.com/2014/06/breadth-first-search-dfs-in-java.html
and this ppt : https://drive.google.com/file/d/0B0sCkwd_qKgJZEJzS1pWeXNmNUE/edit
CLRS website: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm

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

saurabhschool youtube link : https://www.youtube.com/watch?v=gCNsAKkUHPM

Youtube video of Mifta Sintaha:

and here is also a good implementation:
http://electrofriends.com/source-codes/software-programs/cpp-programs/cpp-data-structure/c-programs-for-the-implementation-of-depth-first-searchdfs-for-a-given-graph/comment-page-1/#comments

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;
int adj[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10];

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;
        adj[i][j]=1;
    }

    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--)
            if(adj[v][j]!=0 && visited[j]!=1 && visit[j]!=1)
            {
                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

Leave a Reply

Your email address will not be published. Required fields are marked *