# Depth First Search

/******************************************************************

-> This Program is to implement Depth First search.

-> Data Structers:
Stack:Array

-> This program works in microsoft vc++ 6.0 environment.

*******************************************************************/

#include<iostream.h>
int visit[100];
class graph
{
private:
int n;
graph*next;
public:
void dfs(int); //dfs for a single node
void dfs(); //dfs of the entire graph
void ftraverse(graph*);
}*g[100];

int dfs_span_tree[100][100];

{
int x;
graph*last;

cout<<“Enter adjecent node ,-1 to stop:\n”;
cin>>x;
while(x!=-1)
{
graph*NEW;
NEW=new graph;
NEW->n=x;
NEW->next=NULL;

else
last->next=NEW;
last=NEW;

cout<<“Enter adjecent node ,-1 to stop:\n”;
cin>>x;
}
}

void graph::ftraverse(graph*h)
{
while(h!=NULL)
{
cout<<h->n<<“->”;
h=h->next;
}
cout<<“NULL”<<endl;
}

void graph::dfs(int x)
{
cout<<“node “<<x<<” is visited\n”;
visit[x]=1;

graph *p;
p=g[x];
while(p!=NULL)
{
int x1=p->n;
if(visit[x1]==0)
{
cout<<“from node “<<x<<‘ ‘;
//Add the edge to the dfs spanning tree
dfs_span_tree[x][x1]=1;
dfs(x1);
}
p=p->next;
}
}

void graph::dfs()
{
int i;
cout<<“**********************************************************\n”;
cout<<“This program is to implement dfs for an unweighted graph \n”;
cout<<“**********************************************************\n”;

cout<<“Enter the no of nodes ::”;
cin>>n;
for(i=1;i<=n;i++)
g[i]=NULL;

for(i=1;i<=n;i++)
{
cout<<“Enter the adjacent nodes to node no. “<<i<<endl;
cout<<“***************************************\n”;
}

//display the graph
cout<<“\n\nThe entered graph is ::\n”;
for(i=1;i<=n;i++)
{
cout<<” < “<<i<<” > ::”;
ftraverse(g[i]);
}

for(i=1;i<=n;i++)
visit[i]=0; //mark all nodes as unvisited

cout<<“\nEnter the start vertex ::”;
int start;
cin>>start;

for(i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dfs_span_tree[i][j]=0;

cout<<“\nThe dfs for the above graph is ::\n”;
dfs(start);

cout<<“\n\nThe required dfs spanning tree is ::\n”;

for(i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<dfs_span_tree[i][j]<<‘ ‘;
cout<<endl;
}
}
int main()
{
graph obj;
obj.dfs();
return 0;
}

## 29 thoughts on “Depth First Search”

1. Orlando says:

plz show me the algorithm and way this technique is implemented. ok….

2. Shruthi Rao says:

Can u plz send me this program in ‘C’ language….

3. Bhavna says:

The program works extremely well for numbers but am having difficulty to implement it with characters…..Help plz

4. iqbal says:

Can u plz send me this program C++ . . .

Breadth-first search and depth-first search in the one program, with Data structers used linked list

5. Pigeon says:

I was doing a DFS on a class that required a string to search on this bit of code will find it and best of all its very simple. (Will work on any ‘Type’)

template
bool QandATree::recSearch(nodeType* searchNode, const dType& target) const
{
bool found;

found = searchNode->data == target;

if (!found)
{
if (!found)
}

return found;
}

6. bharath says:

hii frnds..

can u plz frwd me a code for top down and bottom up integration…

7. kamesh says:

Can u plz send me Depth First Search in C or C++ prog. lang.

8. kamesh says:

Can u plz send me Best First Search in C or C++ prog. lang.

9. kamesh says:

Can u plz send me Depth First Search/Breadth First Search prog. in C or C++ lang.

10. it is nice,but i need this code in java.can us send me this to my mail.

1. sale itana sada code dala hai.kuchh samajh hi nahi aa raha. sale phursat me baith

1. Dhak Dhak gall.!! says:

samjhne ke liye dimaag chahiye bachcha..!!!

11. bhavin( says:

12. Wamp says:

kitne main doge..???????
taj mahal bhi chahiye……

13. siva says:

i want c code for genralize circuit. by using dfs,topological sorting,DAG

14. mithun says:

what are doing here? why you don’t use simple code

15. Power says:

Pls I need a shorter c++ code for the implementation of Dfs using the pseudocode as a guide.

16. I’m glad I located this site, I couldnt find any knowledge on this topic before. Also operate a website and for anyone who is ever serious in doing some guest writing for me make sure you feel free to let me know, im always look for people to check out my blog site. Please stop by and leave a comment sometime!

17. I have need a dfs program using c which will find the search path

18. vidhyalakshmi says:

can i have the output for this program?

19. Kathy says:

Is there a way to do this using c? I am trying to create a circuit and then use depth first search to figure out what the longest delay is (so it figures out the longest route…but then also looks at the delay from each of the devices to…like …
NAND–>NAND–>NOR
\ \
V V
NAND–>AND….so it figures out that the AND is level 4 but then it also takes a look at which way it takes the longest…as is does NOR delay cause it to get to AND later than NAND delay type of example

I have each of the gate objects as seperate structs (ex. nor struct as well as nand struct) so that i can implement several of the same type

Any ideas?….your program above seems pretty good…it is just that I do not know c++ and so I am trying to figure out a non object oriented approach

20. Dhak Dhak gall.!! says:

samjhne ke liye dimaag chahiye bachcha…!!

21. Hmm it seems like your blog ate my first comment (it was
super long) so I guess I’ll just sum it up what I had written and say, I’m thoroughly enjoying your blog.
I too am an aspiring blog writer but I’m still new to the whole thing. Do you have any tips for newbie blog writers? I’d really appreciate it.