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