图的遍历及生成树

图的遍历及生成树2010-3-3第1页，课件共32页，创作于2023年2月期末考试长春工业大学>>数据结构精品课程网站>>习题解析/sjjg/index.php?option=com_content&task=category§ionid=&id=21&Itemid=266第2页，课件共32页，创作于2023年2月第3页，课件共32页，创作于2023年2月7.3图的遍历从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。这一过程就叫做图的遍历。

抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。第4页，课件共32页，创作于2023年2月图的遍历操作要解决的关键问题1、在图中，如何选取遍历的起始顶点？在图中，任何两个顶点之间都可能存在边，顶点是没有确定的先后次序的，所以，顶点的编号不唯一。这里指按顶点的存储顺序。解决方案：从编号小的顶点开始。2、因图中可能存在回路，在访问完某个顶点之后会沿着某些边又回到了曾经访问过的顶点。那么如何避免顶点的重复访问？解决方案：附设访问标志数组visited[0..n-1]，它的初始状态为0，在图的遍历过程中，一旦某一个顶点i被访问，就立即改visited[i]为1，防止它被多次访问。第5页，课件共32页，创作于2023年2月1.深度优先搜索(DFS，Depth_FirstSearch

)基本思想：（1）从图中某顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到；（2）若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点；（3）重复上述两步，直至图中所有顶点都被访问到为止。与树的先序遍历过程类似第6页，课件共32页，创作于2023年2月详细过程：1)1.1在访问图中某一起始顶点v

后，由v出发，访问它的任一邻接顶点w1；1.2再从w1出发，访问与w1邻接但还未被访问过的顶点w2；1.3然后再从w2出发，进行类似的访问……直至到达所有的邻接顶点都被访问过的顶点u为止。2)

退回一步，退到前一次刚访问过的顶点，看是否还有其它未被访问的邻接顶点:2.1如果有，则访问此顶点，之后再从此顶点出发，返回第1)步的操作；2.2如果没有，就再退回一步进行搜索。2.3重复上述过程，直到连通图中所有顶点都被访问过为止。第7页，课件共32页，创作于2023年2月例：从顶点v1出发，DFS下图。访问序列：v1,v2,v4,v8,v5,v3,v6,v7v1v6v2v5v3v8v4v7v1v6v2v5v3v8v4v7第8页，课件共32页，创作于2023年2月图的DFS算法一般描述intvisited[MAXVEX];//访问标志数组voidDFSTraverse(GraphG)

{

//对图G作深度优先遍历

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;

//访问标志数组初始化0for(v=0;v<G.vexnum;++v)

if(!visited[v])DFS(G,v);//对尚未访问的顶点调用DFS}第9页，课件共32页，创作于2023年2月voidDFS(GraphG,intv){//从第v个顶点出发递归地深度优先遍历图G

visited[v]=TRUE;Visit(v);//访问第v个顶点

//对v的尚未访问的邻接顶点w递归调用DFS

for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))

if(!visited[w])DFS(G,w);}第10页，课件共32页，创作于2023年2月用邻接表实现图的深度优先搜索v1v6v2v5v3v8v4v7v9v101234567817^17^26^25^34^23^

12^056^034^910

8/\9/\0123456789第11页，课件共32页，创作于2023年2月在图的邻接表中如何进行DFS？DFS结果00000123辅助数组visited[n]1000110011101111例：—照样借用visited[n]起点0123注意：在邻接表中，并非每个链表元素（表结点）都被扫描到,因此遍历速度很快。v0→→→v1v2v3第12页，课件共32页，创作于2023年2月voidDFS(ALGraphG,

intv){ArcNode*p;visited[v]=1;/*置已访问标记*/printf("%d",v); /*输出被访问顶点的编号*/p=G.vertices[v].firstarc;

/*p指向顶点v的第一个邻接点*/while(p!=NULL){if(visited[p->adjvex]==0)DFS(G,p->adjvex);

/*若p->adjvex顶点未访问,递归访问它*/

p=p->nextarc;/*p指向顶点v的下一个邻接点*/}}邻接表的DFS算法第13页，课件共32页，创作于2023年2月for(j=0;j<G.vexnum;j++)if(G.arcs[v][j]&&!visited[j])DFS1(G,

j);}//DFS1DFS1(MGraphG,intv){visit(v);visited[v]=1;//G.arcs[n][n]为邻接矩阵，v为起始顶点(编号）//访问（例如打印）顶点vG.arcs[v][j]＝1有邻接点visited[n]=0未访问过//访问后立即修改辅助数组标志//从v所在行从头搜索邻接点邻接矩阵的DFS算法第14页，课件共32页，创作于2023年2月分析：

在遍历图时，对图中每个顶点至多调用一次DFS函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。

因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为O(n2)。如果用邻接表来表示图，虽然有2e个表结点，但只需扫描

e个结点即可完成遍历，加上访问

n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。第15页，课件共32页，创作于2023年2月2.广度优先搜索(BFS,Breadth_FirstSearch)基本思想：从图中某个顶点V0出发，并在访问此顶点后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点；重复上述过程，直至图中所有顶点都被访问到为止。与树的层次遍历过程类似第16页，课件共32页，创作于2023年2月

例：从顶点v1出发，BFS下图。访问序列：v1,v2,v3,v4,v5,v6,v7,v8v1v6v2v5v3v8v4v7第17页，课件共32页，创作于2023年2月用邻接表实现图的广度优先搜索v1v6v2v5v3v8v4v7v1v2v3v4v5v6v7v8

17^17^2

6^2

5^34^2

3

^

12^056^034^01234567第18页，课件共32页，创作于2023年2月BFS非递归算法voidBFSTraverse(GraphG,Status(*Visit)(intv)){

//使用辅助队列Q和访问标志数组visited[v]

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;

InitQueue(Q);//置空的辅助队列Q

for(v=0;v<G.vexnum;++v)

if(!visited[v]){//v尚未访问

visited[v]=TRUE;Visit(v);

EnQueue(Q,v);//v入队第19页，课件共32页，创作于2023年2月

while(!QueueEmpty(Q)){

DeQueue(Q,u);//队头元素出队并置为u

for(w=FirstAdjVex(G,u);

w>=0;

w=NextAdjVex(G,u,w))

if(!visited[w]){//w为u的尚未访问的邻接顶点

visited[w]=TRUE;Visit(w);

EnQueue(Q,w);

}//if

}//while}//if}//BFSTraverse第20页，课件共32页，创作于2023年2月分析：每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。邻接矩阵：O(n2)邻接表：O(n+e)第21页，课件共32页，创作于2023年2月第7章图7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径第22页，课件共32页，创作于2023年2月7.4图的连通性问题1）无向图的连通分量和生成树2）最小生成树

普里姆算法克鲁斯卡尔算法第23页，课件共32页，创作于2023年2月要想判定一个无向图是否为连通图，或有几个连通分量，通过对无向图遍历即可得到结果。连通图：仅需从图中任一顶点出发，进行深度优先搜索（或广度优先搜索），便可访问到图中所有顶点。

无向图的连通性1.无向图的连通分量和生成树非连通图：需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。

第24页，课件共32页，创作于2023年2月基本概念生成树：某连通分量的极小连通子图，它含有图中全部顶点，但只有n-1条边

；生成森林：非连通图的各个连通分量的极小连通子图（即生成树）构成的集合，含全部顶点，但构成这些树的边是最少的。第25页，课件共32页，创作于2023年2月思考1：若对连通图进行遍历，得到的是什么？遍历过程中历经的边的集合和图G中所有顶点一起构成连通图G的极小连通子图，即图的生成树。

由深度优先搜索得到的生成树，称为深度优先搜索生成树。

由广度优先搜索得到的生成树，称为广度优先搜索生成树。思考2：若对非连通图进行遍历，得到的是什么？得到的将是各连通分量的生成树，即图的生成森林。第26页，课件共32页，创作于2023年2月（a）深度优先生成树（b）广度优先生成树生成树V1V3V2V4V5V6V7V8