教黎 第七章图 程序设计—数据结构 图的遍历算法及其应用 int MaxDistance (MGraph G,int vo) { 体初始化各顶点的访问标志，设置为未访问/ for i=0;i<G.vexnum;i++) visited[i]=FALSE; InitQueue(Q); /体不需要考虑其他的连通分量，因为所求的顶点必定与v0在同一个连通分量中*/ EnQueue (Q,vO); visited[v0]=TRUE while(!QueueEmpty(Q)) DeQueue(Q,v); for(w=0:W<G.vexnum:w++) if G.arcs[v][w].adj&&!visited[w]) visited[w]=TRUE; EnQueue(Q,w); return(v); } 3、思考 1)若要求输出满足条件的全部顶点，则如何修改上述算法： 2)考虑其它图的存储表示下的算法实现。 4、其它类似的应用 ·求v0和v1之间的最短路径： ·在顶点子集U中找出距离顶点v0最近的顶点： ·求顶点v0到其余每个顶点的最短路径： ·求距离顶点v0的最短路径长度为K的所有顶点： ·判别v0和v1之间是否存在长度为K的路径。 7.5图的连通性问题 7.5.1无向图的连通分量和生成树 1、基本概念 ·连通分量的顶点集：即从该连通分量的某一顶点出发进行搜索所得到的顶点访问序列： ·生成树： ·某连通分量的极小连通子图 ·深度优先搜索生成树、广度优先搜索生成树 ·由该连通分量的顶点集和搜索所经过的边组成 ·生成森林：非连通图的各个连通分量的极小连通子图构成的集合 2、算法思路 ·也是图的遍历算法的应用 ·将访问顶点变成创建生成树或增加一个结点到生成树中的操作 ·生成树/森林的存储表示采用孩子兄弟表示法 3、深度优先搜索生成树/森林算法思路 文档编号 完成时间 完成人张昱 修改时间20026-6 第10页程序设计——数据结构 第七章 图 图的遍历算法及其应用 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 10 页 int MaxDistance (MGraph G, int v0 ) { /* 初始化各顶点的访问标志，设置为未访问 */ for ( i=0; i<G.vexnum; i++ ) visited[i] = FALSE; InitQueue(Q); /* 不需要考虑其他的连通分量，因为所求的顶点必定与 v0 在同一个连通分量中 */ EnQueue (Q, v0 ); visited[v0] = TRUE; while( !QueueEmpty(Q) ) { DeQueue(Q, v); for( w=0; w<G.vexnum; w++ ) if ( G.arcs[v][w].adj && !visited[w] ) { visited[w] = TRUE; EnQueue(Q, w); } } return(v); } 3、思考 1）若要求输出满足条件的全部顶点，则如何修改上述算法； 2）考虑其它图的存储表示下的算法实现。 4、其它类似的应用 ·求 v0 和 v1 之间的最短路径； ·在顶点子集 U 中找出距离顶点 v0 最近的顶点； ·求顶点 v0 到其余每个顶点的最短路径； ·求距离顶点 v0 的最短路径长度为 K 的所有顶点； ·判别 v0 和 v1 之间是否存在长度为 K 的路径。 7.5 图的连通性问题 7.5.1 无向图的连通分量和生成树 1、基本概念 ·连通分量的顶点集：即从该连通分量的某一顶点出发进行搜索所得到的顶点访问序列； ·生成树： ·某连通分量的极小连通子图 ·深度优先搜索生成树、广度优先搜索生成树 ·由该连通分量的顶点集和搜索所经过的边组成 ·生成森林：非连通图的各个连通分量的极小连通子图构成的集合 2、算法思路 ·也是图的遍历算法的应用 ·将访问顶点变成创建生成树或增加一个结点到生成树中的操作 ·生成树/森林的存储表示采用孩子-兄弟表示法 3、深度优先搜索生成树/森林算法思路