Skip to content

Instantly share code, notes, and snippets.

@shubham100795
Created March 8, 2017 20:24
Show Gist options
  • Save shubham100795/f74d15a17032fcc95c9117b539a0896d to your computer and use it in GitHub Desktop.
Save shubham100795/f74d15a17032fcc95c9117b539a0896d to your computer and use it in GitHub Desktop.
Non recursive DFS for a graph
#include<iostream>
#include<stack>
#define initial 0
#define visited 1
using namespace std;
int adj[10][10];
int state[10];
void create_graph(int n)
{
int x,max_ver,i,j,k,src,dest;
for(j=0;j<n;j++)
{
for(k=0;k<n;k++)
{
adj[j][k]=0;
}
}
cout<<"press 1 for undirected graph and 2 for directed graph \n";
cin>>x;
if(x==1)
max_ver=n*(n-1)/2;
else
max_ver=n*(n-1);
for(i=0;i<max_ver;i++)
{
cout<<"enter the source and destination \n";
cin>>src>>dest;
if(src==-1&&dest==-1)
break;
if(src<0||src>=n||dest<0||dest>=n)
{
cout<<"invalid vertex \n";
i--;
}
adj[src][dest]=1;
if(x==1)
adj[dest][src]=1;
}
for(j=0;j<n;j++)
{
for(k=0;k<n;k++)
{
cout<<adj[j][k]<<"\t";
}
cout<<endl;
}
}
void DFS_traversal(int s,int n)
{
int i;
stack<int> st;
st.push(s);
while(!st.empty())
{
int v=st.top();
st.pop();
if(state[v]==initial)
{
cout<<v<<"\t";
state[v]=visited;
}
for(i=0;i<n;i++)
{
if(adj[v][i]==1&&state[i]==initial)
st.push(i);
}
}
}
int main()
{
int n,s,z;
cout<<"enter the no of vertices \n";
cin>>n;
create_graph(n);
for(z=0;z<n;z++)
{
state[z]=initial;
}
cout<<"enter the starting vertex \n";
cin>>s;
cout<<endl;
DFS_traversal(s,n);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment