DFS using stacks error!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
|
#include<iostream>
using namespace std;
class dfs
{
int v,i,k,matrix[20][20],j,color[20],stack[20],top;
public:
dfs();
void graph();
void traversal(int);
};
dfs::dfs()
{ top=-1;k=1;
for(int i=1 ;i<=20;i++)
color[i]=0;
}
void dfs::graph()
{
int e,s;
cout<<"Enter the number of vertices\n";
cin>>v;
cout<<"Enter the number of edges\n";
cin>>e;
cout<<"Enter the edges\n";
for(int k=1;k<=e;k++)
{
cin>>i>>j;
matrix[i][j]=1;
matrix[j][i]=1;
}
cout<<"Enter the source vertex\n";
cin>>s;
traversal(s);
}
void dfs::traversal(int s)
{
cout<<s<<" ";
color[s]=1;
while(k<v)
{
for(j=1;j<=v;j++)
{
if((matrix[s][j]==1)&&(color[j]==0))
{
stack[++top]=j;
color[j]=1;
}
}
s=stack[--top];
cout<<s<<" ";
k++;
}
}
int main()
{
dfs a;
a.graph();
system("pause");
return 0;
}
|
Enter the number of vertices
3
Enter the number of edges
2
Enter the edges
1 3
1 2
Enter the source vertex
1
1 2 0 Press any key to continue . . .
|
I can see no reason why the 3rd vertex is not getting visited. Please help guys..
Topic archived. No new replies allowed.