西安电子科技大学计算机学院数据结构课件 第7章（2）.pptVIP

* 第7章 图 7.4 图的连通性问题 1. 无向图的连通分量 图遍历时，对于连通图，无论是广度优先有哪些信誉好的足球投注网站还是深度优先有哪些信誉好的足球投注网站，仅需要调用一次有哪些信誉好的足球投注网站过程，即从任一个顶点出发，便可以遍历图中的各个顶点。对于非连通图，则需要多次调用有哪些信誉好的足球投注网站过程，而每次调用得到的顶点访问序列恰为各连通分量中的顶点集。 j=0; for(v=0; v G.vernum; ++v) if(!visited[v]){ DFS(G, v); j++; } A L M J B F C;  D E; G K H I; 2. 无向图的生成树 一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有构成一棵树的(n-1)条边。 en-1 → 非连通图 en-1 → 有回路 e=n-1 → 不一定都是图的生成树 设G=(V,E)为连通图,则从图中任一顶点出发遍历图时,必定将E(G)分成两个集合T和B,其中T是遍历图过程中走过的边的集合,B是剩余的边的集合：T∩B=Φ,T∪B=E(G)。显然,G=(V,T)是G的极小连通子图,即G是G的一棵生成树。 由深度优先遍历得到的生成树称为深度优先生成树；由广度优先遍历得到的生成树称为广度优先生成树。这样的生成树是由遍历时访问过的n个顶点和遍历时经历的n-1条边组成。 对于非连通图,每个连通分量中的顶点集和遍历时走过的边一起构成一棵生成树,各个连通分量的生成树组成非连通图的生成森林。 问题：以孩子兄弟链表作为森林（或树）的存储结构，如何建立无向图的深度优先生成森林或广度优先生成森林？ 深度优先生成森林 广度优先生成森林 void DFSForest(ALGraph G, CSTree T) { T = NULL; for(v=0; vG.vexnum; ++v) visited[v] = 0; for(v=0; vG.vexnum; ++v) if( !visited[v]){ p = (CSTree) malloc(sizeof(CSNode)); *p = { G.vertices[v].data, NULL, NULL}; if( !T) T = p; else q-nextsibling = p; q = p; DFSTree(G, v, p); } } void DFSTree(Graph G, int v, CSTree T) { ArcNode *a; CSTree p; visited[v] = 1; first = TRUE; for(a=G.vertices[v].firstarc; a; a=a-nextarc){ w = a-adjvex; if( !visited[w]){ p = (CSTree) malloc(sizeof(CSNode)); *p = {G.vertices[w].data, NULL, NULL}; if( first) { T-lchild = p; first = FALSE; } else q-nextsibling = p; q = p; DFSTree(G, w, q); }//if }//for } 3. 最小生成树 在一个连通网的所有生成树中， 各边的代价之和最小的那棵生成树称为该连通网的最小代价生成树（Minimum Cost Spanning Tree），简称为最小生成树(MST)。 最小生成树有如下重要性质(MST性质)：  设 N=(V, {E}) 是一连通网，U 是顶点集V的一个非空子集。 若（u , v）是一条具有最小权值的边， 其中u∈U， v∈V-U， 则存在一棵包含边（u , v）的最小生成树。 用反证法来证明这个MST性质：  假设不存在这样一棵包含边（u , v）的最小生成树。 任取一棵最小生成树T，将（u , v）加入T中。根据树的性质，此时T中必形成一个包含（u , v）