算法7-4,7-5：图的遍历——深度优先搜索

62 阅读 0 评论 41 点赞

我是靠谱客的博主漂亮黑猫，最近开发中收集的这篇文章主要介绍算法7-4,7-5：图的遍历——深度优先搜索，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。其过程为：假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可以从图中的某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。

其算法可以描述如下：

在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法遍历所有顶点，输出遍历顶点的顺序。

输入

输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。

以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个0或1，1表示第i个顶点和第j个顶点有直接连接，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。

输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图。

输出

只有一行，包含n个整数，表示按照题目描述中的深度优先遍历算法遍历整个图的访问顶点顺序。每个整数后输出一个空格，并请注意行尾输出换行。

样例输入

样例输出

0 1 3 2

提示

在本题中，需要熟练掌握图的邻接矩阵存储方式。在建立完成无向图之后，需要严格按照题目描述的遍历顺序对图进行遍历。另外，算法中描述的FirstAdjVex函数和NextAdjVex函数，需要认真的自行探索并完成。

通过这道题目，应该能够对图的深度优先搜索建立更加直观和清晰的概念。

题意描述：

1表示第i个顶点和第j个顶点有直接连接，0表示没有直接连接，输出从0到n的遍历顺序。

思路：

利用深度搜索把输入读入一个二维数组中，依次输出所遍历的点。

具体代码：

#include<stdio.h>
int e[60][60],book[60];
int sum,n;
void dfs(int cur)
{
int i;
printf("%d ",cur);
sum++;
if(sum == n) return;
for(i = 0;i < n; i ++)
{
if(e[cur][i] == 1 &&book[i] == 0)
{
book[i] = 1;
dfs(i);
}
}
return;
}
int main()
{
int i,j,k;
scanf("%d",&n);
for(i = 0;i < n;i ++)
for(j = 0;j < n;j ++)
{
if(i==j)
e[i][j]=0;
else
e[i][j]=99999999;
}
for(i = 0;i < n;i ++)
for(j = 0;j < n;j ++)
{
scanf("%d",&k);
e[i][j]=k;
}
book[0]=1;
dfs(0);
    return 0;
}