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

-> This Program is to implement Depth First search.

-> Data Structers:

Graph:Adjacency List

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:

graph* read_graph(graph*);

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];

graph* graph::read_graph(graph*head)

{

int x;

graph*last;

head=last=NULL;

cout<<”Enter adjecent node ,-1 to stop:\n”;

cin>>x;

while(x!=-1)

{

graph*NEW;

NEW=new graph;

NEW->n=x;

NEW->next=NULL;

if(head==NULL)

head=NEW;

else

last->next=NEW;

last=NEW;

cout<<”Enter adjecent node ,-1 to stop:\n”;

cin>>x;

}

return head;

}

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”;

g[i]=read_graph(g[i]);

}

//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;

}

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

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

Pingback: INDEX « Data Structures through C & C++ for beginners

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

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

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 (searchNode->lLink != NULL)

found = recSearch(searchNode->lLink, target);

if (searchNode->rLink != NULL)

if (!found)

found = recSearch(searchNode->rLink, target);

}

return found;

}

hii frnds..

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

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

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

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

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

please send this code

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

samjhne ke liye dimaag chahiye bachcha..!!!

What is your favorite board game?

business game…? delhi buy karni hai kya….????

kitne main doge..???????

taj mahal bhi chahiye……

i want using satack

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

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

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

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!

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

can i have the output for this program?

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

samjhne ke liye dimaag chahiye bachcha…!!

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.