深度优先搜索DFS的非递归实现

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;
}
上一篇:NWRRC2015 Insider’s Information


下一篇:命令