《数据结构教学课件》第7章幻灯片资料.pptx

数据结构;第7章图 7. 1基本术语 7.2存储结构;7.1图的基本术语（ 图：记为g=（ke） T;证明： ① 完全无向图有n(n-l)/2条边。 证明：若是完全无向图，则顶点1必与所有其他顶点各有1条连 线，即有n?l条边，顶点2有n.2条边，…，顶点有1条边，顶点 n有0条边. 总边数=n-l+ n-2+... + l+0= (n-l+0)n/2= n(n-l)/2 ② 完全有向图有〃(〃」)条边。 证明：若是完全有向图，则顶点1必必与所有其他顶点各有2条 连线，即有2(n?l)条边,顶点2有2(n-2)条边，…，顶点nJ有2 条边，顶点n有0条边. 总边数=2( n-l+ n-2+... +1+0)=2(n-l+0)n/2= n(n-l);例：判断下列4种图形各属什么类型?;稀疏图：边较少的图。通常边数VVlP 稠密图：边很多的图。;无向图中，边数接近n(n-l)/2 ； 有向图中，边数接近n(n-l) 子图：设有两个图G = (V,E)和G，= (V，,E\若VW且 EjE,则称图G，是图G的子图。;带权图：即边上带权的图。其中权是指每条边可以标上 具有某种含义的数值（即与边相关的数）。 网络：=带权图;强连通图：在 图中,若对于每一对顶点*和Vj,都存在一条 从*到与和从与到*的路径，则称此图是强连通图。 非强连通图的极大强连通子图叫做强连通分量。;邻接点：若(〃,卩)是顼G)中的一条边，则称“与u互为邻接顶点;例2：有向图的邻接表同;讨论：邻接表与邻接矩阵有什么异同之处?;解决思路：可设置一个辅助数组visited [n]9用来标记每个被;一、深度优先搜索（ ）;讨论2： ——可以用递归算法！ DFS1( ){ 〃A[n][n]为邻接矩阵，v为起始顶点(编号) visit (v) ； //访问(例如打印)顶点v visited[v]=l; 〃访问后立即修改辅助数组标志 for( j=I; j=n; j++) //从v所在行从头搜索邻接点 if (A[v, j] ! visited[j]) DFS1( j ; return;;讨论3: —照样借用visited [n ]!;DFS算法效率分析： (设图中有〃个顶点，。条边) ■如果用邻接矩阵来表示图，遍历图中每一个顶点 都要 该顶点所在行，因此遍历全部顶点 所需的时间为0(/)。 ■如果用邻接表来表示图，虽然有 个表结点， 但只需扫描 个结点即可完成遍历，加上访问 个头结点的时间，因此遍历图的时间复杂度为 O(n+e)o 结论： 适于在邻接矩阵上进行深度遍历； 适于在邻接表上进行深???遍历。;广度优先搜索（遍历）步骤:;结论:;void DFSearch( int v, int s, char *PATH) ( //从第v个顶点出发递归地深度优先遍历图G, 〃求得一条从v到s的简单路径，并记录在PATH中 visited[v] = TRUE; 〃访问第v个顶点 Append(PATH, getVertex(v)); // 第v个顶点加入路径 for (w=FirstAdjVex(v); w!=0!found; w=NextAdjVex(v)) if (w=s) (found = TRUE; Append(PATH, w);} else if (!visited[w]) DFSearch(w, s, PATH); if (ifound) Delete (PATH); // 从路径上删除顶点 v };7.4图的其他运算;1.求图的生成树（或生成森林） 生成树：是一个极小连通子图，它含有图中全部顶点，但只有 nT条边。 生成森林：由若干棵生成树组成，含全部顶点，但构成这些树 的边是最少的。;例1:画出下图的生成树;例2：画出下图的生成森林（或极小连通子图）;先写出邻接表（或邻接矩阵）:;? (E);2.求最小生成树;典型用途： 欲在n个城市间建立通信网，贝！In个城市应铺n-1条线路； 但因为每条线路都会有对应的经济成本，而n个城市可能有n (n-1)/2条线路，那么，如何选择n-l条线路，使总费用最少？ 数学模型： 顶点---表示城市,有n个; 边----表示线路,有『1条;J 显然此连通网 ) 岫认『表示线路的经济代价;亠 连通网一表示n个城市间通信网。;讨论：如何求得最小生成树？ ______ ——有多种算法，但最常用的是以下两种:;克鲁斯卡尔(Kruskal)算法： 设0={ V, E }是有刀个顶点的连通网， 步骤： (1) 首先构造一个只有n个顶点但没有边的非连通图 T= { V, 0}f图中每个顶点自成一个连通分量。 (2) 当在边集E中选到一条具有最