数据结构－第07章－图_03.pptVIP

7.4 图的连通性问题 术语 连通(可及)：在图G中，若从顶点v到v’有路径，则称v 和v’是连通的(可及的)。 连通图：在无向图G中，任意两个顶点都是连通的，称 图G是连通图。 连通分量：无向图中的极大连通子图。参考P.159 图7.3 子图：有两个图G=(V,E)和G’=(V’,E’)，如果V’?V且E’?E， 则称G’为G的子图。 7.4 图的连通性问题 连通分量 (Connected component) 当无向图为非连通图时， 从图中某一顶点出发， 利用DFS或BFS不可能遍历到图中的所有顶点，只能访问到该顶点所在的最大连通子图(连通分量)的所有顶点。 若从无向图的每一个连通分量中的一个顶点出发进行遍历，可求得无向图的所有连通分量。 7.4 图的连通性问题 连通分量 (Connected component) 求连通分量的算法需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。 7.4 图的连通性问题 生成树:假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个 极小连通子图，称该极小连通子图为此连 通图的生成树。 对于非连通的无向图，所有连通分量的 生成树组成了非连通图的生成森林。 7.4.1 无向图的连通分量和生成树 生成树: 一个连通图从任一顶点遍历后，其所有边集E(G)可 以分为两个集合T(G)和B(G)，T(G)是遍历图过程中 历经的边的集合；B(G)是剩余的边的集合。T(G)和 G中所有顶点一起构成连通图G的极小连通子图即生 成树。 可以这样理解生成树：由遍历连通图G时所经 过的边和顶点构成的子图是G的生成树。 7.4.1 无向图的连通分量和生成树 右图是由深度优先有哪些信誉好的足球投注网站得到的是深度优先有哪些信誉好的足球投注网站生成树： 7.4.1 无向图的连通分量和生成树 右图是由广度优先有哪些信誉好的足球投注网站得到的是广度优先有哪些信誉好的足球投注网站生成树： 7.4.1 无向图的连通分量和生成树 2．算法7.7 非连通图森林的生成算法： void DFSForest(Graph G，CSTree T) //建立无向图G的深度优先生成森林（最左）孩子（右）兄弟链表T { T=NULL； int i=0； for( i=0；iG.vexnum；i++) visited[i]=FALSE; //访问标志置0 for( i=0；iG.vexnum；i++) if ( !visited[i] ) { p=(CSTree)malloc(sizeof(CSNode))；//分配森林树的根结点空间 *p={GetVex(G，i)，NULL，NULL}；//给该结点赋值 if ( !T )T=p； //是第一颗生成树的根（T的根） else q-nextsibling=p； //是上一邻接顶点的右兄弟结点 q=p; DFSTree(G,i,q)； //建立以p为根的生成树 } }//DFSForest 7.4.1 无向图的连通分量和生成树 3．算法7.8 连通图生成树的算法： void DFSTree(Graph G，int v，CSTree T) //从第v个顶点出发深度优先遍历图G，建立以T为根的生成树。 { visited[v]=TRUE；first=TRUE； for(w=FirstAdjVex(G，v)；w=0；w=NextAdjVex(G，v，w)) if ( !Visited[w] ) { p=(CSTree)malloc(sizeof(CSNode))； //分配孩子结点 *p={GetVex(G，w)，NULL，NULL}； if ( first ) { T-lchild=p；first=FALSE；} //是根的左孩子结点 else q-nextsibling=p； //是上一邻接顶点的右兄弟结点 q=p； DFSTree(G,w,q)； //从第w个顶点出发深度优先遍历图G } //建立子生成树q } 7.4.3 最小生成数 使用不同的遍历图的方法，可以得到不同的生成 树；从不同的顶点出发，也可能得到不同的生成