亲宝软件园·资讯

展开

C语言 数据结构 图的遍历

玄澈_ 人气:0

引入 

在数据结构中常见的有深度优先搜索和广度优先搜索。为什么叫深度和广度呢?其实是针对图的遍历而言的,请看下面这个图:

图是由一些小圆点(称为顶点) 和 连接这些点的直线 (称为边)组成的。

例如上图就是由5个顶点(编号为 1,2,3,4,5) 和5条边(1-2,1-3,1-4,2-4)组成。

现在我们从1号顶点开始遍历这个图,遍历就是把图的每一个顶点都访问一次。使用深度优先搜索将会得到如下的结果。

图中每个顶点旁边的数表示这个顶点是第几个被访问到的,我们称之为 —— 时间戳 

深度优先搜索

使用深度优先搜索来遍历这个图的过程:

首先从一个未走过的顶点作为起始顶点,比如以1号顶点作为起点。沿1号顶点的边去尝试其他它未走过的顶点,首先发现的是2号顶点还没被走过,于是来到了2号顶点。

再以2号顶点作为出发点继续尝试访问其他未走到过的顶点,这样又来到了4号顶点。

再以4号顶点作为出发点继续尝试访问其他未走过的顶点。但是,此时在4号顶点的周围已经没有其他的顶点了,所以需要返回到2号顶点。返回到2号顶点后,发现沿2号顶点也不能在访问到其他未走到的点了,此时又需要返回到1号顶点。

继续以1号顶点尝试访问其他顶点,我们来到了3号点。以此类推,我们最后来到了5号点。到此,所以的顶点都走过了,遍历结束

深度优先搜索的主要思想是:

首先以一个未被访问的顶点作为起始顶点,沿当前顶点的边走到未被访问过的顶点

当没有未访问过的顶点时,则回到上一个顶点,继续试探访问别的顶点,直到所有的顶点都被访问过。

显然,深度优先搜索是沿着图的某一条分支遍历直至末端,然后回溯,再沿另一条实现相同的遍历,直到所以的顶点都被访问完为止。

代码实现 

上面的二维数组中 第i行第j列就是表示顶点i到顶点j是否有边。

1表示有边,x表示没有边,0表示顶点自己到自己。

我们将这种方法称为 ——  图的邻接矩阵储存法。 

细心的朋友可能会发现这张图沿着对角线全部是0,因为上面这张图是 无向图。 

所谓无向图就是指图的边没有方向。例如边 1 - 5 表示 1号顶点可以到 5号顶点,5号顶点也可以到1号顶点。

接下来就是解决怎么用深度优先搜索来实现遍历了:

void dfs(int cur)				//cur是当前所在的顶点编号
{
	printf("%d", cur);
	sum++;						//每访问一个点就sum++
	if (sum == n) return;		//所有的顶点都访问过了
	for (i = 1; i <= n; i++)	//从1到n的顶点依次尝试,看看有哪些顶点与当前顶点cur有边相连
	{
		//判断当前顶点cur到顶点i是否有边,并判断顶点i是否已被访问过
		{
			if (e[cur][i] == 1 && book[i] == 0)
			{
				book[i] = 1;	//标记顶点i已经访问过
				dfs(i);			//从顶点i出发继续遍历
			}
		}
	}
	return;
}

在上面的代码中 变量 cur 存储的是当前正在遍历的点,二维数组e存储的就是图的边(邻接矩阵),数组book用来标记哪些顶点已经访问过,变量sum用来记录已经访问多少个顶点,变量你存储的是图的顶点总个数。

完整代码  

#include <stdio.h>
int book[101], sum, n, e[101][101];
void dfs(int cur)				//cur是当前所在的顶点编号
{
	printf("%d", cur);
	sum++;						//每访问一个点就sum++
	if (sum == n) return;		//所有的顶点都访问过了
	for (i = 1; i <= n; i++)	//从1到n的顶点依次尝试,看看有哪些顶点与当前顶点cur有边相连
	{
		//判断当前顶点cur到顶点i是否有边,并判断顶点i是否已被访问过
		{
			if (e[cur][i] == 1 && book[i] == 0)
			{
				book[i] = 1;	//标记顶点i已经访问过
				dfs(i);			//从顶点i出发继续遍历
			}
		}
	}
	return;
}
 
int main()
{
	int i, j, m, a, b;
	scanf("%d %d", &n, &m);
	//初始化二维矩阵
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			if (i == j) e[i][j] = 0;
			else e[i][j] = 99999999;	//我们假设99999999为x
 
	//读入顶点之间的边
	for (i = 1; i <= n; i++)
	{
		scanf("%d %d", &a, &b);
		e[a][b] = 1;
		e[b][a] = 1;	//因为该图为无向图
	}
 
	//从1号顶点出发
	book[1] = 1;  //标记1号顶点已经访问
	dfs(1);		  //从1号顶点开始遍历
 
	return 0;
}

加载全部内容

相关教程
猜你喜欢
用户评论