DFS的非递归实现借助栈,除第一个节点外其余节点逆序。
输入:
5 6
1 2
2 3
3 5
1 4
4 2
4 5
输出:
1 4 5 3 2
#include<stdio.h>
#include<stdlib.h>
#define N 100
typedef int ElemType;
struct stack{
ElemType data[N];
int top;
};
int n;
int a[N][N],vis[N];
void DFS(int pos){ //除第一个节点外其余节点逆序
vis[pos]=1;
stack S;
S.top=0;
S.data[S.top++]=pos;
while(S.top>0){
int t=S.data[--S.top];
printf("%d ",t);
int i=0;
for(i=1;i<=n;i++){
if(a[t][i]&&vis[i]==0){
S.data[S.top++]=i;
vis[i]=1;
}
}
}
}
int main()
{
int i,j,k,m;
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++){
int x,y;
scanf("%d %d",&x,&y);
a[x][y]=a[y][x]=1;
}
DFS(1);
return 0;
}