数据结构主 题：第四章 图（二）本章节知识脉络：1. 图的遍历；2. 最小生成树；3. 最短路径。重点和难点：1. 重点：图的遍历算法，最小生成树算法， 最短路径算法。2. 难点：图遍历的算法，掌握构造最小生成树的 Prim 算法和 Kruskal 算法；掌握单源最短路径的Dijkstra 算法，会在给定实例图上描述算法过程。了解所有点对之间的最短路径算法。一、 图的遍历1. 图的遍历的定义 给出一个图 G 和其中任意一个顶点 V0，从 V0出发系统地访问 G 中所有的顶点，每个顶点访问一次，这叫做图的遍历。图的遍历分为：深度优先搜索，广度优先搜索。 深度优先搜索（depth-rst search，简称 DFS）1）基本思想① 访问一个顶点 V，然后访问该顶点邻接到的未被访问过的顶点 V'；② 再从 V'出发递归地按照深度优先的方式周游；③ 当遇到一个所有邻接于它的顶点都被访问过了的顶点 U 时则回到已访问顶点序列中最后一个拥有未被访问的相邻顶点的顶点 W；④ 再从 W 出发递归地按照深度优先的方式周游；⑤ 最后，当任何已被访问过的顶点都没有未被访问的相邻顶点时，则周游结束。 2）图的深度优先搜索算法的实现3）深度优先搜索效率分析对于具有 n 个顶点和 e 条边的无向图或有向图，深度优先搜索算法对图中每个顶点至多调用一次 DFS 函数。 用邻接矩阵表示图时，共需检查 n2个矩阵元素，所需时间为 O(n2)； 用邻接表表示图时，找邻接点需将邻接表中所有边结点检查一遍，需要时间 O(e)，对应的深度优先搜索算法的时间复杂度为 O(n+e)。 广度优先搜索（breadth-rst search， 简称 BFS）1）基本思想① 访问顶点 V0；② 然后访问 V0邻接到的所有未被访问过的顶点 V01，V02，...，V0i；③ 再依次访问 V01，V02，...，V0i邻接到的所有未被访问的顶点；④ 如此进行下去，直到访问遍所有的顶点。2）图的广度优先搜索算法的实现3）广度优先搜索效率分析广度优先搜索算法的时间复杂度与深度优先搜素算法的时间复杂度相同。二、 最小生成树1. 最小生成树的概念 连通图的最小生成树1）连通图的生成树不唯一。2）生成树的代价，为树上各边的权之总和。所有的生成树中，代价最小的生成树称为图 G 的最小生成树（minimum-cost spanning tree，简称 MST）3）应用举例 上图代表 6 个城市间的交通网，边上的权表示公路的造价，现在要用公路把 6 个城市连接起来（这至少要修 5 条公路），如何设计使得这 5 条公路的总造价最少？2. 最小生成树的构造算法 prim 算法1）算法思想图 G=(V,E)是具有 n 个顶点的连通图，设 U 是最小生成树中顶点的集合，TE 是最小生成树中边的集合；初始，U={u1}，TE={}，重复执行：在所有 u∈U，v∈V-U 的边(u,v)中寻找代价最小的边(u',v')，并纳入集合 TE 中；同时将 v'纳入集合 U 中；直至 U=V 为止。集合 TE 中必有 n-1 条边。2）代码实现#dene INFINITY MAX_VAL /* 最大值 */ MSTEdge *Prim_MST(AdjGraph *G , int u)/* 从第 u 个顶点开始构造图 G 的最小生成树 */{ MSTEdge TE[] ; // 存放最小生成树 n-1 条边的数组指针int j , k , v , min ;for (j=0; j<G->vexnum; j++){ closedge[j].adjvex=u ; closedge[j].lowcost=G->adj[j][u] ;} /* 初始化数组 closedge[n] */ closedge[u].lowcost=0 ; /* 初始时置 U={u} */ TE=(MSTEdge *)malloc((G->vexnum-1)*sizeof(MSTEdge)) ;for (j=0; j<G->vexnum-1; j++){ min= INFINITY ;for (v=0; v<G->vexnum; v++) if(closedge[v].lowcost!=0&& closedge[v].Lowcost<min) { min=closedge[v].lowcost ; k=v ; }TE[j].vex1=closedge[k].adjvex ; TE[j].vex2=k ;TE[j].weight=closedge[k].lowcost ;closedge[k].lowcost=0 ; /* 将顶点 k 并入 U 中 */for (v=0; v<G->vexnum; v++) if (G->adj[v][k]<closedge[v]. lowcost) { closedge[v].lowcost= G->adj[v][k] ; closedge[v].adjvex=k ; } /* 修改数组 closedge[n]的各个元素的值 */}return(TE) ;} /* 求最小生成树的 Prime 算法 */ 2）算法分析：本算法的重点是边一定存在于 U 与 V-U 之间（MST 性质）。设带权连通图有 n 个顶点，则算法的主要执行是二重循环： 求 closedge 中权值最小的边，频度为 n-1 ； 修改closedge 数组，频度为 n 。因此，整个算法的时间复杂度是 O(n2)，与边的数目无关。 Kruskal 算法1）算法思想；设 G=(V, E)是具有 n 个顶点的连通网，T=(U, TE)是其最小生成树。初值：U=V，TE={} 。对 G 中的边按权值大小从小到大依次选取。① 选取权值最小的边(vi，vj)，若边(vi，vj)加入到 TE 后形成回路，则舍弃该边(边(vi，vj)；否则，将该边并入到 TE 中，即 TE=TE∪{(vi，vj)} 。② 重复① ，直到 TE 中包含有 n-1 条边为止。2）算法实现：MSTEdge *Kruskal_MST(ELGraph *G) /* 用 Kruskal 算法构造图 G 的最小生成树 */{ MSTEdge TE[] ; int j, k, v, s1, s2, Vset[] ;WeightType w ;Vset=(int *)malloc(G->vexnum*sizeof(int)) ;for (j=0; j<G->vexnum; j++)Vset[j]=j ; /* 初始化数组 Vset[n] */ sort(G->edgelist) ; /* 对表按权值从小到大排序 */j=0 ; k=0 ;while (k<G->vexnum-1&&j< G->edgenum){ s1=Vset[G->edgelist[j].vex1] ;s2=Vset[G->edgelist[j].vex2] ;/* 若边的两个顶点的连通分量编号不同, 边加入到 TE 中 */if (s1!=s2) {TE[k].vex1=G->edgelist[j].vex1 ; TE[k].vex2=G->edgelist[j].vex2 ; TE[k].weight=G->edgelist[j].weight ; k++ ; for (v=0; v<G->vexnum; v++) if (Vset[v]==s2) Vset[v]=s1 ; }j++ ;}free(Vset) ; return(TE) ;} /* 求最小生成树的 Kruskal 算法 */3）算法分析：设带权连通图有 n 个顶点，e 条边，则算法的主要执行是：① Vset 数组初始化：时间复杂度是 O(n) ；② 边表按权值排序：若采用堆排序或快速排序，时间复杂度是 O(e㏒e) ；③ while 循环：最大执行频度是 O(n)，其中包含修改 Vset 数组，共执行 n-1 次，时间复杂度是 O(n2) ；④ 整个算法的时间复杂度是 O(e㏒e+n2) 。三、 最短路径1. 单源最短路径 ① 给定一个带权有向图 G=<V,E>，其中每条边(vi,vj)上的权 W[vi,vj]是一个非负实数。另外，给定 V 中的一个顶点 s 作为源点。② 要计算从源点 s 到所有其他各顶点的最短路径，这个问题通常称为单源最短路径（ single-source shortest paths）问题。2. Dijkstra 算法该算法是由 E.W.Dijkstra 提出的一种按路径长度递增的次序产生到各顶点最短路径的贪心算法。 Dijkstra 算法思想：1) 如果 v0到 vj的最短路径为：v0->vx1->vx2->vxn->vi->vj则 v0->vx1->vx2->vxn->vi是 v0到 vi的最短路径。2) 按长度顺序产生最短路径时，下一条最短路径总是由一条已产生的最短路径加上一条边形成。3) 集合 S 表示最短路径已经确定的顶点集，其余的顶点放在另一个集合 V-S 中，初始时，集合 S只包含源点 s，表示此时只有源点到自己的最短路径是已知的。4) 设 v 是 V 中的某个顶点，把从源点 s 到顶点 v 且中间只经过集合 S 中顶点的路径称为从源点到顶点 v 的特殊路径，并用数组 D 来记录当前所找到的从源点 s 到每个顶点的最短特殊路径长度，用数组 Path 记录到各个顶点的前驱顶点。5) 如果从源点 s 到顶点 v 有弧，则 D[v]记为弧的权值，否则将 D[v]置为无穷大。Path 数组初始化为 s。6) Dijkstra 算法每次从尚未确定最短路径长度的集合 V-S 中取出一个最短特殊路径长度最小的顶点 u，将 u 加入集合 S，同时修改数组 D 和 Path 的值：若加进 u 做中间顶点，使得 vi的最短特殊路径长度变短，则修改 vi的最短特殊路径长度及前驱顶点编号（即当 D[u]+W[u,vi]<D[vi]时，令D[vi]=D[u]+W[u,vi]，path[vi]=u）。7) 然后重复上述操作，一旦 S 包含了 V 中所有的顶点，D 中各顶点的距离值就记录了从源点 s 到该顶点的最短路径长度。 Dijkstra 算法实例  Dijkstra 算法实现:BOOLEAN nal[MAX_VEX] ;int pre[MAX_VEX] , dist[MAX_VEX] ;void Dijkstra_path (AdjGraph *G, int v)/* 从图 G 中的顶点 v 出发到其余各顶点的最短路径 */{ int j, k, m, min ; for ( j=0; j<G->vexnum; j++){ pre[j]=v ; nal[j]=FALSE ;dist[j]=G->adj[v][j] ;} /* 各数组的初始化 */dist[v]=0 ; nal[v]=TRUE ; /* 设置 S={v} */for ( j=0; j<G->vexnum-1; j++) /* 其余 n-1 个顶点 */{ m=0 ;while (nal[m]) m++; /* 找不在 S 中的顶点 vk */min=INFINITY ; for ( k=0; k<G->vexnum; k++) { if (!nal[k]&&dist[m]<min) { min=dist[k] ; m=k ; } } /* 求出当前最小的 dist[k]值 */nal[m]=TRUE ; /* 将第 k 个顶点并入 S 中 */for ( j=0; j<G->vexnum; j++){ if (!nal[j]&&(dist[m]+G->adj[m][j]<dist[j])) { dist[j]=dist[m]+G->adj[m][j] ; pre[j]=m ; }} /* 修改 dist 和 pre 数组的值 */ } /* 找到最短路径 */} Dijkstra 算法复杂度注意该算法要求图中不存在负权回路。空间复杂度取决于存储方式，邻接矩阵为 O(n2)。时间复杂度取决于求权值最小边的方式： a) 采用最小堆来选择权值最小的边，那么每次改变最短特殊路径长度时需要对堆进行一次重排，此时的时间复杂度为 O((n+e)loge)，适合于稀疏图。b) 通过直接比较 D 数组元素，确定代价最小的边就需要总时间 O(n2)；取出最短特殊路径长度最小的顶点后，修改最短特殊路径长度共需要时间 O(e)，因此共需要花费 O(n2)的时间，这种方法适合于稠密图。四、 本节例题最短路径的生成算法可用（）。A．普里姆算法 B．克鲁斯卡尔算法 C．迪杰斯特拉算法 D．哈夫曼算法答案：C五、 思考题一个无向图的邻接表如下图所示：（1）从顶点 v0出发进行深度优先搜索，经历的结点顺序为（）。A．v0, v3, v2, v1 B．v0, v1, v2, v3 C．v0, v2, v1, v3 D．v0, v1, v3, v2答案:B（2）从顶点 V0出发进行广度优先搜索，经历的结点顺序为（）。A．v0, v3, v2, v1 B．v0, v1, v2, v3 C．v0, v2, v1, v3 D．v0, v1, v3, v2答案：D