Key for important topicsDFS (depth first search) program in c++
/* C++ Program to implement DFS Algorithm for Connected Graph */
#include<iostream>
using namespace std;
#define MAX 100
#define initial 1
#define visited 2
int n; /* Number of nodes in the graph */
int adj[MAX][MAX]; /*Adjacency Matrix*/
int state[MAX]; /*Can be initial or visited */
void DF_Traversal();
void DFS(int v);
void create_graph();
int stack[MAX];
int top = -1;
void push(int v);
int pop();
int isEmpty_stack();
int main()
{
create_graph();
DF_Traversal();
}/*End of main()*/
void DF_Traversal()
{
int v;
for(v=0; v<n; v++)
state[v]=initial;
cout<<("\nEnter starting node for Depth First Search : ");
cin>>(v);
DFS(v);
cout<< ("\n");
}/*End of DF_Traversal( )*/
void DFS(int v)
{
int i;
push(v);
while(!isEmpty_stack())
{
v = pop();
if(state[v]==initial)
{
cout<<(v);
state[v]=visited;
}
for(i=n-1; i>=0; i--)
{
if(adj[v][i]==1 && state[i]==initial)
push(i);
}
}
}/*End of DFS( )*/
void push(int v)
{
if(top == (MAX-1))
{
cout<<("\nStack Overflow\n");
return;
}
top=top+1;
stack[top] = v;
}/*End of push()*/
int pop()
{
int v;
if(top == -1)
{
cout<<("\nStack Underflow\n");
exit(1);
}
else
{
v = stack[top];
top=top-1;
return v;
}
}/*End of pop()*/
int isEmpty_stack( )
{
if(top == -1)
return 1;
else
return 0;
}/*End if isEmpty_stack()*/
void create_graph()
{
int i,max_edges,origin,destin;
cout<<("\nEnter number of nodes : ");
cin>>(n);
max_edges=n*(n-1);
for(i=1;i<=max_edges;i++)
{
cout<<"\nEnter edge( -1 -1 to quit )"<<i<<":";
cin>>origin;
cin>>destin;
if( (origin == -1) && (destin == -1) )
break;
if( origin >= n || destin >= n || origin<0 || destin<0)
{
cout<<("\nInvalid edge!\n");
i--;
}
else
{
adj[origin][destin] = 1;
}
}
}
Comments
Post a Comment