数据结构——图的遍历

杨伟彬
杨伟彬   编辑于 2018-11-28 09:42
阅读量: 72

1. 图的遍历定义

       从图的任意指定顶点出发,依照某种规则去访问图中所有顶点,且每个顶点仅被访问一次,这一过程叫做图的遍历

       图的遍历按照深度优先和广度优先规则去实施,通常有深度优先遍历法(Depth_First Search—DFS )和广度优先遍历法(Breadth_Frist Search—BFS)两种。

2. 深度优先遍历法

遍历步骤:

       ①访问指定的起始顶点;

       ②若当前访问的顶点的邻接顶点有未被访问的,则任选一个访问之,转2; 反之,退回到最近访问过的顶点;直到始顶点相通的全部顶点都访问完毕;

       ③若此时图中尚有顶点未被访问,则再选其中一个顶点作为起始顶点并访问之,转 2; 反之,遍历结束。

例如:

    

      由上图可知,访问结果不唯一,如何判别V的邻接点是否被访问?

解决方案: 为每个顶点设立一个“访问标志”。

       首先将图中每个顶点的访问标志设为 FALSE,之后搜索图中每个顶点,如果未被访问,则以该顶点为起始点,进行深度优先遍历,否则继续检查下一顶点。

采用递归方法实现,深度优先遍历代码实现如下:

void DFS(ALGraph G,int v)
	//从第v个顶点出发递归地深度优先遍历图或者网G。
{
	int w;
	
	VisitFunc(G,v);	//访问第i个结点
	visited[v] = 1;	//访问过的结点,下标位置标记1

	for(w = FirstAdjVex(G,v); w >= 0; w = NextAdjVex(G,v,w))
		if(!visited[w])//与之邻接且未被访问过的继续访问
			DFS(G,w);
}

void DFSTraverse(ALGraph G,int (* VisitFunc)(ALGraph G, int i))
	//对图G作深度优先遍历。
	//使用全局变量VisitFunc,使DFS不必设函数指针参数
{
	int i;
	for(i = 0; i < G.vexnum; ++i)
		visited[i] = 0;	//访问标志数组初始化
	for(i = 0; i < G.vexnum; ++i)
		if(!visited[i])
			DFS(G,i);	//对尚未访问的顶点调用DFS
}
上面代码中用到的两个函数:
int FirstAdjVex(ALGraph G,int i)
	//i代表的第i个头结点,返回第i个头结点的firstarc指向的表结点 
int NextAdjVex(ALGraph G,int v,int w)
	//w代表adjvex为w的结点
	//返回第v个头结点(顶点)对应的表结点中adjvex值为w的结点的下一个结点的adjvex值,如果没有返回-1

        visited[i]代表第i个顶点的访问标记,如果是0,则没被访问,如果是1,则被访问了。

3. 广度优先遍历法

       步骤:从图的某一结点出发,首先依次访问该结点的所有邻接顶点, 再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点,重复此过程,直至所有顶点均被访问为止。

  

       由上图可知,广度优先遍历结果不唯一。

例如:

  

图解释说明

        对图作广度优先遍历,按广度优先非递归遍历图,代码如下:

void BFSTraverse(ALGraph G,int (* VisitFunc)(ALGraph G, int i))
//对图作广度优先遍历,按广度优先非递归遍历图G。使用辅助队列Q 
{
	LinkQueue Q;
	int i,u;
	for(i = 0; i < G.vexnum; ++i)
		visited[i] = 0;
	InitQueue(Q);	//置空的辅助队列
	for(i = 0; i < G.vexnum; ++i)	//从第0个顶点开始找
		if(!visited[i])
		{
			VisitFunc(G,i);
			visited[i] = 1;
			EnQueue(Q,i);
			while (Q.front != Q.rear)
			{
				int w;
				DeQueue(Q,u);	//队头元素出队,并赋值给u
				for(w = FirstAdjVex(G,u); w >= 0;
 w = NextAdjVex(G,u,w))
					if(!visited[w])
					{
						VisitFunc(G,w);
						visited[w] = 1;
						EnQueue(Q,w);
					}//if
			}//while
		}//if
}

       和深度优先搜索类似,在遍历过程中也需要一个访问标志数组visited,分析上面代码可知,每一个顶点至多进一次队列,在每次进入队列时输出该顶点。

收藏 1 转发 评论 2

我很忧虑

杨老师:“这个实际上是不难的,听懂了吗”