Depth First Search


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

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

About these ads

27 thoughts on “Depth First Search

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

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

  3. 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

  4. 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;
    }

  5. 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!

  6. 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

  7. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s