图的遍历

图的遍历

问题描述：

  从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历。图的遍历的遍历有DFS和BFS两种。  上面的图，从顶点0出发，按照顶点序号从小到大的顺序DFS，得到遍历顺序为0 1 2 3  4 5 6 7 8。

输入：

图的顶点数与边数，以及每条边的两个顶点。

输出：

dfs遍历顺序

输入样例：

9 10
0 1
1 2
2 3
1 4
0 4
0 8
8 5
5 4
5 6
6 7

输出样例：

0 1 2 3 4 5 6 7 8

代码：

#include <iostream>
#define N 20
using namespace std;
int a[N][N],b[N],bz[N],s,n;
void dfs(int k)
{
int i;
if(s==n)
{
for(i=0;i<n-1;i++)cout<<b[i]<<" ";
cout<<b[n-1]<<endl;
}
else
for(i=0;i<n;i++)
if(bz[i]==0&&a[k][i]==1)
{
b[s]=i;s++;
bz[i]=1;
dfs(i);
bz[i]=0;
}
}
int main(int argc, char *argv[])
{
int i,j,k,x,y;
memset(a,0,sizeof(a));
memset(bz,0,sizeof(bz));
cin>>n>>k;
while(k--)
{
cin>>x>>y;
a[x][y]=a[y][x]=1;
}
bz[0]=1;s=1;b[0]=0;
dfs(0);
return 0;
}

最后

以上就是结实纸鹤为你收集整理的图的遍历的全部内容，希望文章能够帮你解决图的遍历所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。