图的遍历——深度优先搜索

叁歲伎倆 2022-05-24 00:18 206阅读 0赞

## 图的遍历——深度优先搜索 ##

## 题目描述 ##

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

其算法可以描述如下：

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

## 输入 ##

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

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

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

## 输出 ##

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

## 样例输入 ##

4
    0 1 0 1
    1 0 0 0
    0 0 0 1
    1 0 1 0

## 样例输出 ##

0 1 3 2

## 提示 ##

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

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

## 深度优先遍历思想： ##

首先从一个为被访问过的开始，沿当前顶点的边走到未访问的顶点；当没有未访问的顶点时，则回到上一顶点，继续访问别的顶点，直到所有的顶点都被访问过。显然，深度优先遍历是沿着图的某一条的分支遍历直到末端，然后回溯，再沿着另一条进行同样的遍历直到所有的顶点都被访问过。

## 程序代码：    ##

#include<stdio.h>
    int book[60],e[60][60],sum,n;//定义全局变量时，默认初始都为0 
    void dfs(int x);
    int main()
    {
    	int i,j;
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    		for(j=0;j<n;j++)
    			scanf("%d",&e[i][j]);
    			
    	//从0号顶点开始查找并标记，0号顶点已经查找过 
    	book[0]=1;
    	dfs(0);
    	
    	
    	printf("\n");
    	return 0;
    }
    void dfs(int x)
    {
    	int i;
    	printf("%d ",x);//输出走过的顶点 
    	
    	//统计走的顶点个数，若所有顶点都已走完返回 
    	sum++;
    	if(sum==n)
    		return;
    	
    	//从0号顶点开始查找直到遇到未被遍历过，且两顶点间有边然后再从查到的顶点开始查 
    	for(i=0;i<n;i++)
    		if(e[x][i]==1&&book[i]==0)
    		{
    			book[i]=1;
    			dfs(i);	
    		}
    	
    	return;	
    }