算法大视界课件-城市互连

第九章第九章 城市互连城市互连9.19.1 问题：智者旅行问题：智者旅行9.29.2 图的基本知识图的基本知识9.3 9.3 最小生成树最小生成树9.49.4 智者旅行问题求解智者旅行问题求解9.5 9.5 应用：高速公路问题应用：高速公路问题9.6 9.6 总结与思考总结与思考附录附录主要内容：主要内容：9.1.1 9.1.1 问题描述问题描述 已知已知5 5个城市个城市A A、B B、C C、D D、E,E,而而且城市且城市A A、B B、C C、D D、E E 两两直接互连两两直接互连（见右图），城市间的具体距离已在（见右图），城市间的具体距离已在线上标出。旅行商从城市线上标出。旅行商从城市 A A 出发，出发，必须到访所有城市，而且每个城市只必须到访所有城市，而且每个城市只能到访一次，最后回到城市能到访一次，最后回到城市 A A。问：。问：旅行商从城市旅行商从城市 A A 出发再回到城市出发再回到城市 A A 所走的最短路径。所走的最短路径。9.1 9.1 问题：智者旅行问题：智者旅行A BDCE32322779959.1.2 9.1.2 问题分析问题分析 解决这个问题的方法从城市解决这个问题的方法从城市A A出发，出发，寻找到和城市寻找到和城市A A最短距离的城市，通过最短距离的城市，通过观察可知此时应该到达城市观察可知此时应该到达城市C C，再次寻，再次寻找到下一个最短距离的城市，通过观找到下一个最短距离的城市，通过观察可知到达城市察可知到达城市E E，依次寻找下去就可，依次寻找下去就可以求出最短的路径。以求出最短的路径。这个问题就抽象成了求图中经过这个问题就抽象成了求图中经过所有点的总距离最短。所有点的总距离最短。A BDCE3232277995 与该问题相类似的还有很多。与该问题相类似的还有很多。例如，城市输电线路网。一个城市中有许多变电站，要将这些例如，城市输电线路网。一个城市中有许多变电站，要将这些变电站通过输电线路全部连接起来，形成一个城市供电网。输电线变电站通过输电线路全部连接起来，形成一个城市供电网。输电线路如何连，使得即保证把全部变电站都连接，同时输电线路长度又路如何连，使得即保证把全部变电站都连接，同时输电线路长度又最短（或输电损耗最小）。最短（或输电损耗最小）。图中，顶点代表变电站，边代表输电线路（可能的），权代表图中，顶点代表变电站，边代表输电线路（可能的），权代表线路长度（或损耗）。线路长度（或损耗）。该类问题都是属于在一个赋权连通图中求该类问题都是属于在一个赋权连通图中求最小生成树最小生成树的问题。的问题。即：一个包含了连通图里的所有顶点（即：一个包含了连通图里的所有顶点（VertexVertex）的连通子图，且其）的连通子图，且其所有边的权值之和亦为最小。所有边的权值之和亦为最小。接下来就让我们一起来认识图及如何求其最小生成树吧！接下来就让我们一起来认识图及如何求其最小生成树吧！同理，城市通讯网的规划和构建、校园道路的规划和建设，都同理，城市通讯网的规划和构建、校园道路的规划和建设，都属于此类问题。属于此类问题。9.2.1 9.2.1 图的定义和术语图的定义和术语图的结构定义图的结构定义:图是由一个顶点集图是由一个顶点集 V V 和一个弧集和一个弧集 R R构成的数据结构。构成的数据结构。Graph=(V,R)R=VRGraph=(V,R)R=VR其中，其中，VRVR|v,wV|v,wV 且且 P(v,w)P(v,w)，表示从表示从 v v 到到 w w 的一条弧，并称的一条弧，并称 v v 为弧尾，为弧尾，w w 为弧头。为弧头。谓词谓词 P(v,w)P(v,w)定义了弧定义了弧 的意义或信息。的意义或信息。9.29.2 图的基本知识图的基本知识 由于由于“弧弧”是有方向的，因此称由顶点集和弧集构成的图为是有方向的，因此称由顶点集和弧集构成的图为有有向图向图。例如例如:G1=(V:G1=(V1 1,VR,VR1 1)A AB B E E C C D D其中其中V V1 1=A,B,C,D,E=A,B,C,D,EVRVR1 1=,=,若若 VR VR 必有必有 VR,VR,则称则称 (v,w)(v,w)为顶点为顶点v v 和顶点和顶点 w w 之间存在一条边。之间存在一条边。由顶点集和边集构成的图称作由顶点集和边集构成的图称作无向图无向图。B B C CA A D D F F E E例如例如:G2=(V:G2=(V2 2,VR,VR2 2)V V2 2=A,B,C,D,E,F=A,B,C,D,E,FVRVR2 2=(=(A,B)A,B),(A,E),(A,E),(B,E),(B,F),(C,B,E),(B,F),(C,D),(C,F),(D,F)D),(C,F),(D,F)主要操作：主要操作：结构的建立：结构的建立：CreatGraph(&G,V,VR)CreatGraph(&G,V,VR):/:/按定义按定义(V,VR)(V,VR)构造图构造图 对邻接点的操作：对邻接点的操作：FirstAdjVex(G,v);FirstAdjVex(G,v);/返回返回 v v 的的“第一个邻接点第一个邻接点”，若该顶，若该顶点在点在 G G 中没有邻接点，则返回中没有邻接点，则返回“空空”NextAdjVex(G,v,w)NextAdjVex(G,v,w);/;/返回返回 v v 的（相对于的（相对于w w的）的）“下一个邻下一个邻接点接点”，若，若w w是是v v的最后一个邻接点，则返回的最后一个邻接点，则返回“空空”遍历：遍历：DFSTraverse(G,v,Visit()DFSTraverse(G,v,Visit();/;/从顶点从顶点v v起深度优先遍历图起深度优先遍历图G G，并对每个顶点调用函数并对每个顶点调用函数VisitVisit一次且仅一次。一次且仅一次。BFSTraverse(G,v,Visit()BFSTraverse(G,v,Visit();/;/从顶点从顶点v v起广度优先遍历图起广度优先遍历图G G，并对每个顶点调用函数并对每个顶点调用函数VisitVisit一次且仅一次。一次且仅一次。A AE EF FB BB BC C设图设图G=(V,VR)G=(V,VR)和图和图 G G=(V,VR),=(V,VR),且且 VV V,VRV,VR VR,VR,则称则称 GG为为 G G 的的子图子图。A AB BE EC CF F1597211132 弧或边带权的图分别称作弧或边带权的图分别称作有向网有向网或或无向网无向网。名词和术语名词和术语网、子图网、子图 邻接点、度、入度、出度邻接点、度、入度、出度 假若顶点假若顶点v v 和顶点和顶点w w 之间存在一条边，则称顶点之间存在一条边，则称顶点v v 和和w w 互为互为邻邻接点接点，边边(v,w)(v,w)和顶点和顶点v v 和和w w 相相关联关联。和顶点和顶点v v 关联的边的数目定义为顶点关联的边的数目定义为顶点v v的的度度。例如：例如：ID(B)=3ID(B)=3ID(A)=2ID(A)=2A AC CD DF FE EB B顶点的顶点的出度出度(OD)(OD):以顶点以顶点v v为弧尾为弧尾的弧的数目；的弧的数目；顶点的顶点的入度入度(ID)(ID):以顶点以顶点v v为弧头为弧头的弧的数目。的弧的数目。A AB BE EC CF F对有向图来说对有向图来说，顶点的度顶点的度(TD)=(TD)=出度出度(OD)+(OD)+入度入度(ID)(ID)例如例如:ID(A)=1ID(A)=1OD(A)=2OD(A)=2ID(B)=2ID(B)=2OD(B)=1OD(B)=1 设图设图G=(V,VR)G=(V,VR)中的一个顶点序列中的一个顶点序列 u=v u=vi,0i,0,v,vi,1i,1,v vi,mi,m=w=w中，中，(v(vi,j-1i,j-1,v,vi,ji,j)VR 1jm,VR 1jm,则称从顶点则称从顶点u u 到顶点到顶点w w 之间之间存在一条存在一条路径路径。路径上边的数目称作。路径上边的数目称作路径长度路径长度。A AB BE EC CF F如如:长度为长度为3 3的路径的路径A,B,C,FA,B,C,F简单路径简单路径:序列中顶点不重复出序列中顶点不重复出现的路径。现的路径。简单回路简单回路:序列中第一个顶点和序列中第一个顶点和最后一个顶点相同的简单路径。最后一个顶点相同的简单路径。路径、路径长度、简单路径、简单回路路径、路径长度、简单路径、简单回路 若图若图G G中任意两个顶点之间都中任意两个顶点之间都有路径相通，则称此图为有路径相通，则称此图为连通图连通图；若无向图为非连通图，则图若无向图为非连通图，则图中各个极大连通子图称作此图的中各个极大连通子图称作此图的连通分量连通分量。B BA AC CD DF FE EB BA AC CD DF FE E连通图、连通分量、强连通图、强连通分量连通图、连通分量、强连通图、强连通分量 对有向图，若任意两个顶点之间都存在一条有向路径，则称此对有向图，若任意两个顶点之间都存在一条有向路径，则称此有向图为有向图为强连通图强连通图。否则，其各个强连通子图称作它的否则，其各个强连通子图称作它的强连通分量强连通分量。A AB BD DC CE E强连通图强连通图A AB BD DC CE E强连通分量强连通分量生成树生成树 假设一个连通图有假设一个连通图有 n n 个顶点和个顶点和 e e 条边，其中条边，其中 n-1 n-1 条边和条边和 n n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树生成树。B BA AC CD DF FE EB BA AC CD DF FE E生成树生成树9.2.29.2.2 图的存储结构图的存储结构一、数组表示方法一、数组表示方法 用两个数组分别存储数据元素（顶点）和数据元素之间的关系用两个数组分别存储数据元素（顶点）和数据元素之间的关系（边或弧）的信息。（边或弧）的信息。定义定义:邻接矩阵的元素为邻接矩阵的元素为:A Aijij=0 (v0 (vi i,v,vj j)VRVR1 (v1 (vi i,v,vj j)VRVR 对对无向图而言，必有无向图而言，必有 A Aijij=A Ajiji，其邻接矩阵一定是，其邻接矩阵一定是对称矩阵对称矩阵。B BA AC CD DF FE E0 01 10 00 01 10 01 10 00 00 01 11 10 00 00 01 10 01 10 00 01 10 00 01 11 11 10 00 00 00 001 11 11 10 00 0A AB BC CD DE EF FA B C D E FA B C D E FA AB BE EC CD DA AB BC CD DE EA B C D E A B C D E 无向图无向图有向图有向图网的邻接矩阵可定义为：网的邻接矩阵可定义为：A Aijij=否则否则W Wi,ji,j 若若(v(vi i,v,vj j)或或v VRVRA AB BE EC CD D56384260 05 5 6 6 0 02 2 0 06 63 38 8 0 0 4 4 0 0A B C D E A B C D E A AB BC CD DE Etypedef struct ArcNode typedef struct ArcNode int adjvex;/int adjvex;/该弧所指向的顶点的位置该弧所指向的顶点的位置 struct ArcNode *nextarc;/struct ArcNode *nextarc;/指向下一条弧的指针指向下一条弧的指针 InfoType *info;/InfoType *info;/该弧相关信息该弧相关信息 ArcNode;ArcNode;adjvex nextarcadjvex nextarc infoinfo弧的结点结构弧的