Question

无向图的深度优先遍历怎么做

Answer 1

#include<stdio.h>
#define n 5
int a[10]={0};
int top=0;//定义堆栈
int main()
{
void dfs(int (*edge)[n],int *status);
int edge[n][n]={{0,0,1,1,0},{0,0,0,0,1},{1,0,0,0,0},{1,0,0,0,1},{0,1,0,1,0}};//临接矩阵表示的图
int status[n]={0};//每个点的状态，有没有被访问
int i=0,j=0;
// for(i=0;i<n;i++)
// for(j=0;j<n;j++)
// scanf("%d",&edge[i][j]);
dfs(edge,status);
return 0;
}
void dfs(int (*edge)[n],int *status)//遍历
{
int k=0,j=0;
while(top>=0)
{
// for(i=0;i<n;i++)
// {
if(status[k]==0)
{
top++;
a[top]=k;
// b[count++]=k;
printf("%d",k);
status[k]=1;
}
while(j<n)
{
// for(j=0;j<n;j++)
if(edge[k][j]==1)
{
if(status[j]==0)
{
top++;
a[top]=j;
// b[count++]=k;
printf("%5d",j);
status[j]=1;
k=j;
j=0;
}
else
j++;
}
else
j++;
}
top-=1;
k=a[top];
j=0;
}
}

这个是非递归的，
#include<stdio.h>
#define n 5
int main()
{
void dft(int (*edge)[n],int *status);
int i=0,j=0;
int edge[n][n]={0};
int status[n]={0};
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&edge[i][j]);
dft(edge,status);
return 0;
}
void dft(int (*edge)[n],int *status)
{
void dftcore(int (*edge)[n],int *status,int i);
int i=0;
for(i=0;i<n;i++)
dftcore(edge,status,i);
}
void dftcore(int (*edge)[n],int *status,int i)
{
int j=0;
if(status[i]==1)
return;
printf("%5d",i);
status[i]=1;
for(j=0;j<n;j++)
if(edge[i][j]==1)
dftcore(edge,status,j);
}
这个递归的