最新图及其应用(new)幻灯片.ppt

《最新图及其应用(new)幻灯片.ppt》由会员分享，可在线阅读，更多相关《最新图及其应用(new)幻灯片.ppt（205页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第10章章 图及其应用图及其应用 2：是一种网状数据结构。是顶点集：是一种网状数据结构。是顶点集V和连和连接这些顶点的弧集接这些顶点的弧集(边集边集)VR所组成的结构记为所组成的结构记为 : G=(V,VR）若若, 则称此图为则称此图为有向图。有向图。 , 通常用尖括弧表示一条有向通常用尖括弧表示一条有向边边, vi, vj表示从顶点表示从顶点vi到到vj的一段弧的一段弧, vi称为边的始点称为边的始点(或弧尾或弧尾), vj称为边的终点称为边的终点(或弧头或弧头), vi,vj和和 vj, vi代表两条不同的弧。代表两条不同的弧。132第第10章章 图及其应用图及其应用 3第第10章章 图

2、及其应用图及其应用 4第第10章章 图及其应用图及其应用 5第第10章章 图及其应用图及其应用 6第第10章章 图及其应用图及其应用 7第第10章章 图及其应用图及其应用 8第第10章章 图及其应用图及其应用 9 如图所示的无向图中如图所示的无向图中, , 分别为分别为v1, v2, v3, v4与与v1, v5, v4, 。 v1到到v5的两条路径都为的两条路径都为。为简单回路或者简单环。为简单回路或者简单环。 第第10章章 图及其应用图及其应用 10 在在中，若从顶点中，若从顶点i到顶点到顶点j有路径，则称顶点有路径，则称顶点i和顶点和顶点j是连通的。若任意两个顶点都是连通的，则称是连通的

3、。若任意两个顶点都是连通的，则称此无向图为连通图，否则称为非连通图。此无向图为连通图，否则称为非连通图。 连通图和非连通图示例见图连通图和非连通图示例见图: 3 1 2 4 1 2 3 4 5 （a） 连通图 (b) 非连通图 图 7-4 连通图和非连通图 第第10章章 图及其应用图及其应用 11 对于对于来说来说, 若图中若图中, 则称该则称该。强连通图和非强连通图示例见图强连通图和非强连通图示例见图: A B D C (a)强连通图 (b)非强连通图 图 7-5 强连通图和非强连通图 1 2 1 6 5 4 3 强连通图 (b)非强连通图 图 7-5 强连通图和非强连通图 第第10章章 图

4、及其应用图及其应用 12中，极大的连通子图为该图的连通分量。显中，极大的连通子图为该图的连通分量。显然，任何连通图的连通分量只有一个，即它本身，而然，任何连通图的连通分量只有一个，即它本身，而非连通图有多个连通分量。非连通图有多个连通分量。24351672435167第第10章章 图及其应用图及其应用 13 有向图中的有向图中的称为该有向图的称为该有向图的。显然，任何强连通图的强连通分量只有一个，。显然，任何强连通图的强连通分量只有一个，即它本身，而非强连通图有多个强连通分量。即它本身，而非强连通图有多个强连通分量。 下图不是强连通的下图不是强连通的, 但它有两个强连通分量但它有两个强连通分量

5、:132321第第10章章 图及其应用图及其应用 142341如：顶点如：顶点1的度为的度为3132如：顶点如：顶点2的入度为的入度为2 出度为出度为1中中, 要区别顶点的入度和出度的概念。要区别顶点的入度和出度的概念。 顶点顶点v的的 是指是指记为记为ID(v) 顶点顶点v的的 是指是指记为记为OD(v) 显然：显然：D(v)=ID(v)+OD(v) 顶点的顶点的 是指是指, 通常记通常记 为为D(v)第第10章章 图及其应用图及其应用 15 10.1 图的概念 10.2 图的存储 10.3 图的遍历 10.4 生成树和最小生成树 10.5 最短路径 10.6 有向无环图的应用第第10章章

6、图及其应用图及其应用 16 10.2.1 邻接矩阵存储法 10.2.2 邻接表表示法 10.2.3 十字链表 10.2.4 邻接多重表 第第10章章 图及其应用图及其应用 17用一个二维数组（矩阵）来表示图中顶点之间的相邻关系。 设图设图G=(V, VR)有有n(n1)个顶点个顶点, 则则G的邻接矩阵是按如的邻接矩阵是按如下定义的下定义的n阶方阵阶方阵: 1 若若(vi,vj)或或VR(G) aij= 0 反之反之第第10章章 图及其应用图及其应用 18 图图G1、 G2的邻接矩阵分别表示为的邻接矩阵分别表示为A1和和A2, 矩阵的矩阵的行、行、 列号对应于图中结点的号。列号对应于图中结点的号

7、。 0 1 1 11 0 1 01 1 0 11 0 1 01A0 1 10 0 10 1 02A2341132G1G2第第10章章 图及其应用图及其应用 19 （1）矩阵是对称的，可压缩存储（上（下）三角）矩阵是对称的，可压缩存储（上（下）三角）;（2）第）第i行或第行或第i 列中列中1的个数为顶点的个数为顶点i 的度的度;（3）矩阵中）矩阵中1的个数的一半为图中边的数目的个数的一半为图中边的数目;（4）很容易判断顶点）很容易判断顶点i 和顶点和顶点j之间是否有边相连之间是否有边相连(看看矩阵中矩阵中i行行j列值是否为列值是否为1)。第第10章章 图及其应用图及其应用 20（1） 矩阵不一定

8、是对称的矩阵不一定是对称的;（2） 第第i 行中行中1的个数为顶点的个数为顶点i 的出度的出度;（3） 第第i列中列中1的个数为顶点的个数为顶点 i的入度的入度;（4） 矩阵中矩阵中1的个数为图中弧的数目的个数为图中弧的数目;（5） 很容易判断顶点很容易判断顶点i 和顶点和顶点j 是否有弧相连是否有弧相连.第第10章章 图及其应用图及其应用 21 若图若图G是一个有是一个有n个顶点的网，则它的邻接矩阵是具个顶点的网，则它的邻接矩阵是具有如下性质的有如下性质的nn矩阵矩阵A： ijwjiA,若若或或(vi, vj) VR(G)反之反之 第第10章章 图及其应用图及其应用 22 5 7 4 8 5

9、 3A234158475一个有向网一个有向网N及其邻接矩阵的示例。及其邻接矩阵的示例。 第第10章章 图及其应用图及其应用 23 n n个顶点需要个顶点需要n n* *n n个单元存储边个单元存储边( (弧弧););空间效率为空间效率为O(nO(n2 2) )。 邻接矩阵法邻接矩阵法优点：优点：邻接矩阵法邻接矩阵法缺点：缺点： 容易实现图的操作，如：求某顶点的度、判断顶点容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。之间是否有边（弧）、找顶点的邻接点等等。第第10章章 图及其应用图及其应用 24邻接矩阵表示法的邻接矩阵表示法的C语言类型描述如下：语言类型描

10、述如下： define MAX_V_N 10 define INFINITY 32768 typedef GraphKind; 第第10章章 图及其应用图及其应用 25typedef ArcNode; 第第10章章 图及其应用图及其应用 26 typedef AdjMatrix; 第第10章章 图及其应用图及其应用 27int LocateVertex(AdjMatrix * G, VertexData v)/求顶点位置函数求顶点位置函数 int j = -1, k; for(k=0; kvexnum; k+) if(G-vexsk = = v) j = k; break; return(j)

11、; 第第10章章 图及其应用图及其应用 28int CreateDN(AdjMatrix *G) /创建有向网创建有向网 int i, j, k, weight; VertexData v1, v2; scanf(%d, %d, &G-arcnum, &G-vexnum); for(i=0; ivexnum; i+) for(j=0; jvexnum; j+) G-arcsij.adj = INFINITY; for(i=0; ivexnum; i+) scanf(%c, &G-vexsi); 第第10章章 图及其应用图及其应用 29 for(k=0; karcnum; k+) scanf(%

12、c, %c, %d, &v1, &v2, &weight); i=LocateVex(G, v1); j=LocateVex(G, v2); G-arcsij.adj = weight; return(Ok); 第第10章章 图及其应用图及其应用 30 10.2.1 邻接矩阵存储法 10.2.2 邻接表表示法 10.2.3 十字链表 10.2.4 邻接多重表第第10章章 图及其应用图及其应用 31 邻接表（邻接表（Adjacency List）表示法是图的一种链式存）表示法是图的一种链式存储结构。它包括两个部分储结构。它包括两个部分, 一部分是一部分是, 另一部分是另一部分是。 在在(n为顶点

13、数为顶点数), 用来存放边用来存放边的信息。的信息。 将将。2341112342413234(a) G1的 邻 接 表 表 示 法1123423455453532341212表 头 结 点 表边 表(b) G2的 邻 接 表 表 示 法表 头 结 点 表边 表图 7.9第第10章章 图及其应用图及其应用 32 这样，一个这样，一个n个顶点的图的邻接表表示由个顶点的图的邻接表表示由与与两部分构成：两部分构成： 由所有表头结点以顺序结构（向量）由所有表头结点以顺序结构（向量）的形式存储的形式存储.。 表头结点的结构如图所示，由两部分构成：表头结点的结构如图所示，由两部分构成：用于存储顶点的名用于存

14、储顶点的名(值值)；用于指向链表中第一个顶点（即与顶点用于指向链表中第一个顶点（即与顶点vi邻接的第一个邻接的第一个邻接点）。邻接点）。 第第10章章 图及其应用图及其应用 33由邻接点链式存储的单链表。由邻接点链式存储的单链表。 单链表中每个结点由三个域组成单链表中每个结点由三个域组成: 指示与顶点指示与顶点vi 邻接的点在图中的位置；邻接的点在图中的位置； 指指向顶点向顶点vi 的下一个邻接点；的下一个邻接点； 存储和边存储和边(或弧或弧)相关的信息相关的信息,如权值等。如权值等。第第10章章 图及其应用图及其应用 34112342413234(a) G1的 邻 接 表 表 示 法1123

15、423455453532341212表 头 结 点 表边 表(b) G2的 邻 接 表 表 示 法表 头 结 点 表边 表图 7.92341第第10章章 图及其应用图及其应用 355423415第第10章章 图及其应用图及其应用 36 （1）第）第i 个链表中结点数目为顶点个链表中结点数目为顶点i的度；的度；（2）所有链表中结点数目的一半为图中边数；）所有链表中结点数目的一半为图中边数；（3）占用的存储单元数目为）占用的存储单元数目为n+2e (e为边数为边数)。第第10章章 图及其应用图及其应用 37（1）第）第i 个链表中结点数目为顶点个链表中结点数目为顶点i的出度；的出度；（2）所有链表

16、中结点数目为图中弧数；）所有链表中结点数目为图中弧数；（3）占用的存储单元数目为）占用的存储单元数目为n+e 。 从有向图的邻接表可知，不能求出顶点的入度。从有向图的邻接表可知，不能求出顶点的入度。若要求第若要求第i个顶点的个顶点的，必须，必须，在所，在所有边链表中查找有边链表中查找求和。求和。由此可见，由此可见， 对于用邻接表方式存储的有向图，求顶点对于用邻接表方式存储的有向图，求顶点的入度并不方便，的入度并不方便， 它需要通过扫描整个邻接表才能得它需要通过扫描整个邻接表才能得到结果。到结果。 第第10章章 图及其应用图及其应用 38 法，对每一顶点法，对每一顶点vi再建立一个再建立一个逆邻

17、接表，即对每个顶点逆邻接表，即对每个顶点vi建立一个所有以顶点建立一个所有以顶点vi为弧为弧头的弧的表，如图所示：头的弧的表，如图所示： 112342344113图7.102341第第10章章 图及其应用图及其应用 39空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点； 判断两顶点间是否有边或弧，需搜索两结点判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。对应的单链表，没有邻接矩阵方便。第第10章章 图及其应用图及其应用 40define MAX_V_N 10 typedef GraphKind; typedef ArcNode; /边表中结点的类型边表

18、中结点的类型邻接表存储结构的形式化说明如下：邻接表存储结构的形式化说明如下： 第第10章章 图及其应用图及其应用 41typedef VertexNode; /表头结点表中结点的类型表头结点表中结点的类型typedef AdjList; /基于邻接表的图基于邻接表的图(Adjacency List Graph) 第第10章章 图及其应用图及其应用 42邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。 对于任一确定的无向图，邻接矩阵是唯一的（行列对于任一确定的无向图，邻接矩阵是唯一的（

19、行列号与顶点编号一致），但邻接表不唯一（链接次序与号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。顶点编号无关）。 邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复杂而邻接表的空间复杂度为度为O(n+e)O(n+e)。第第10章章 图及其应用图及其应用 43 10.2.1 邻接矩阵存储法 10.2.2 邻接表表示法 10.2.3 十字链表 10.2.4 邻接多重表 第第10章章 图及其应用图及其应用 44 十字链表是有向图的另一种链式存储结构。在十字十字链表是有向图的另一种链式存储结构。在十字链表中，链表中，弧尾顶点在弧尾顶点在图中的位置图中

20、的位置弧头顶点在弧头顶点在图中的位置图中的位置指向与此弧弧头指向与此弧弧头相同的下一条弧相同的下一条弧指向与此弧弧尾指向与此弧弧尾相同的下一条弧相同的下一条弧指向该弧的指向该弧的相关信息相关信息第第10章章 图及其应用图及其应用 45对应于每个顶点也有一个结点（对应于每个顶点也有一个结点（）：）：指向以该顶点作为弧头指向以该顶点作为弧头的第一个弧顶点的第一个弧顶点存储与顶点有关的信息存储与顶点有关的信息, ,如顶点的名字等如顶点的名字等指向以该顶点作为弧指向以该顶点作为弧尾的第一个弧顶点尾的第一个弧顶点datafirstinfirstout第第10章章 图及其应用图及其应用 461234123

21、41213 34 234141 第第10章章 图及其应用图及其应用 47define MAX_V_N 10 typedef GraphKind; typedef ArcNode; /*弧结点的类型弧结点的类型*/第第10章章 图及其应用图及其应用 48typedef VertexNode; /*顶点结点的类型顶点结点的类型*/typedef OrthList; /*图的十字链表表示法图的十字链表表示法(Orthogonal List)*/ 第第10章章 图及其应用图及其应用 49 10.2.1 邻接矩阵存储法 10.2.2 邻接表表示法 10.2.3 十字链表 10.2.4 邻接多重表 第第1

22、0章章 图及其应用图及其应用 50是无向图的另一种链式存储结构。在是无向图的另一种链式存储结构。在邻接多重表中，邻接多重表中，markivexilinkjvexjlinkinfo标记该条边是标记该条边是否被搜索过否被搜索过指向下一依附指向下一依附于顶点于顶点i的边的边该边的一个该边的一个顶点在图中顶点在图中的位置序号的位置序号该边的另一个该边的另一个顶点在图中顶点在图中的位置序号的位置序号指向下一指向下一条依附于条依附于顶点顶点j的边的边指向该弧的指向该弧的相关信息相关信息第第10章章 图及其应用图及其应用 51 每一个顶点也用一个结点表示，该结点有两个域：每一个顶点也用一个结点表示，该结点有

23、两个域：datafirstedge存储与顶点有存储与顶点有关的信息，如关的信息，如顶点的名字顶点的名字指向第一条依附指向第一条依附于该顶点的边于该顶点的边第第10章章 图及其应用图及其应用 5235143234521212345123454523415第第10章章 图及其应用图及其应用 53邻接多重表的结构类型说明如下：邻接多重表的结构类型说明如下： typedef VertexNode; /*顶点结点的类型顶点结点的类型*/第第10章章 图及其应用图及其应用 54typedef EdgeNode; /*边结点的类型边结点的类型*/typedef AdjMultiList; /*基于图的邻接多

24、重表表示法基于图的邻接多重表表示法(Adjacency Multi-list)*/第第10章章 图及其应用图及其应用 55 在图的链接存储在图的链接存储(邻接表、逆邻接表、十字链表邻接表、逆邻接表、十字链表和邻接多重表和邻接多重表)中，表头向量需要占用中，表头向量需要占用n个存储单元，个存储单元，所有边结点需要占用所有边结点需要占用2e或或e存储单元，所以最多需要存储单元，所以最多需要（n+2e）个存储单元，稀疏图采用这种存储方式可）个存储单元，稀疏图采用这种存储方式可节省存储空间。节省存储空间。第第10章章 图及其应用图及其应用 56 10.1 图的概念 10.2 图的存储 10.3 图的遍

25、历 10.4 生成树和最小生成树 10.5 有向无环图的应用 10.6 最短路径第第10章章 图及其应用图及其应用 57沿着某条搜索路径对图中所有顶点各沿着某条搜索路径对图中所有顶点各作一次访问。作一次访问。 图的遍历比起树的遍历要复杂得多。图中顶点关图的遍历比起树的遍历要复杂得多。图中顶点关系是多对多的关系，图可能是非连通图，图中还可能系是多对多的关系，图可能是非连通图，图中还可能有回路存在，有回路存在， 因此在访问了某个顶点后，可能沿着因此在访问了某个顶点后，可能沿着某条路径搜索后又回到该顶点上。某条路径搜索后又回到该顶点上。 。 第第10章章 图及其应用图及其应用 58 为此为此 我们设

26、置一个我们设置一个，用于，用于标示图中每个顶点是否被访问过，标示图中每个顶点是否被访问过，则置则置访问标志数组中的访问标志数组中的，以表示该顶点，以表示该顶点已访问。已访问。 根据搜索路径的不同，图的遍历又分：根据搜索路径的不同，图的遍历又分： 第第10章章 图及其应用图及其应用 5910.3.1 深度优先搜索遍历 10.3.2 广度优先搜索遍历 第第10章章 图及其应用图及其应用 60 （Depth-First Search）是指按照深）是指按照深度方向搜索，它类似于树的先根遍历，是树的先根遍度方向搜索，它类似于树的先根遍历，是树的先根遍历的推广。历的推广。 尽可能先对纵深方向进行搜索。尽可

27、能先对纵深方向进行搜索。 从某个顶点从某个顶点v0出发，进行出发，进行dfs的算法描述如下：的算法描述如下： 第第10章章 图及其应用图及其应用 61BAGDCFHEI 下图给出了一个深度优先搜索的过程图示，其中下图给出了一个深度优先搜索的过程图示，其中，箭头旁边，箭头旁边的数字代表搜索顺序，的数字代表搜索顺序， 。 第第10章章 图及其应用图及其应用 62 ，则从图中某一个顶，则从图中某一个顶点出发可以访问到图中所有顶点，否则只能访问到点出发可以访问到图中所有顶点，否则只能访问到一部分顶点。一部分顶点。 另外，从刚才写出的遍历结果可以看出，从某另外，从刚才写出的遍历结果可以看出，从某一个顶点

28、出发的遍历结果是不唯一的。但是一个顶点出发的遍历结果是不唯一的。但是,若我们若我们给定图的存贮结构给定图的存贮结构,则从某一顶点出发的遍历结果应则从某一顶点出发的遍历结果应是唯一的。是唯一的。 第第10章章 图及其应用图及其应用 63(1) 为防止重复访问顶点，需为防止重复访问顶点，需 ，其值为，其值为 0 时，表示顶点时，表示顶点 i 未被访问未被访问过；值为过；值为 1 时，表示顶点时，表示顶点 i 已被访问过。已被访问过。(2) 算法中需算法中需，可根据不同的存，可根据不同的存储结构具体实现。这里为简化描述，给出两个自定义储结构具体实现。这里为简化描述，给出两个自定义函数：函数： 第第1

29、0章章 图及其应用图及其应用 64 ：返回图：返回图G中顶点中顶点v0的第一个邻的第一个邻接点的编号，若不存在，返回接点的编号，若不存在，返回 0 。 ：返回图：返回图G中顶点中顶点 v0的邻接的邻接点中，处于点中，处于 w 之后的那个邻接点的编号；若不存在，则之后的那个邻接点的编号；若不存在，则返回返回 0 。 第第10章章 图及其应用图及其应用 65访问 v0置访问标志visitedv0=1w = FirstAdjVertex(g,v0) w = = 0 w 已被访问过dfs(g ,w) w= NextAdjVertex(g , v0, w)第第10章章 图及其应用图及其应用 66 voi

30、d DFS（Graph g, int v0） visit（v0）； visitedv0 =True； w=FirstAdjVertex(g, v0); while ( w! = -1) if(! visited w ) DFS(g, w); w=NextAdjVertex(g, v0, w); /DepthFirstSearch第第10章章 图及其应用图及其应用 67 若若，则从图中某一，则从图中某一个顶点出发。个顶点出发。，而只能访问到一个连通子图（既连通分量），而只能访问到一个连通子图（既连通分量）或只能访问到一个强连通子图（既强连通分量）。或只能访问到一个强连通子图（既强连通分量）。 这

31、时，这时，最后将，最后将每个连通分量或每个强连通分量的遍历结果合起来，每个连通分量或每个强连通分量的遍历结果合起来，则得到整个非连通图的遍历结果。则得到整个非连通图的遍历结果。第第10章章 图及其应用图及其应用 68 非连通图的遍历算法实现与连通图的只有一点非连通图的遍历算法实现与连通图的只有一点不同，即不同，即，反复调用连通图的，反复调用连通图的深度优先搜索遍历算法即可。具体实现如下：深度优先搜索遍历算法即可。具体实现如下： for(int i=1;i=n;i+) if(!visitedi) dfs(i) ; 第第10章章 图及其应用图及其应用 69156710823491234567891

32、02112655102834437499(a) 无 向 图 G 5(b ) G 5的 邻 接 表图 7.1734129108567(c) 无 向 图 G 5的 三 个 连 通 分 量 下图是一个非连通图，按照它的邻接表进行深下图是一个非连通图，按照它的邻接表进行深度优先搜索遍历，三次调用度优先搜索遍历，三次调用DFS过程得到的访问顶过程得到的访问顶点序列为：点序列为： 1， 2， 4， 3， 9 5， 6， 78， 10 第第10章章 图及其应用图及其应用 70int visitedMAX_V_N; void TraverseGraph (Graph g) for (vi=0; vig.vex

33、num; vi+) visitedvi= 0 ; for( vi=0; vig.vexnum; vi+) if (！Visitedvi ) DFS(g， vi)； / TraverseGraph 第第10章章 图及其应用图及其应用 71 void DFS(AdjMatrix g, int v0) visit(v0); visitedv0=True; for ( vj=0; vjadjvex) DFS（g，p-adjvex）；）； p=p-nextarc ； /DepthFirstSearch第第10章章 图及其应用图及其应用 73 10.3.1 深度优先搜索遍历 10.3.2 广度优先搜索遍历

34、第第10章章 图及其应用图及其应用 74（Breadth-First Search）是指照广度）是指照广度方向搜索，它类似于树的层次遍历，是树的按层次遍方向搜索，它类似于树的层次遍历，是树的按层次遍历的推广。历的推广。广度优先搜索的广度优先搜索的是：是： （1） 从图中某个顶点从图中某个顶点v0出发，出发， （2） 第第10章章 图及其应用图及其应用 75BAGDCFHEI第第10章章 图及其应用图及其应用 76需需，记录已被访问过的顶点。，记录已被访问过的顶点。广度优先遍历中，访问过一个顶点后，下一个需要广度优先遍历中，访问过一个顶点后，下一个需要访问的顶点可能是任何一个已访问过的顶点的邻接

35、访问的顶点可能是任何一个已访问过的顶点的邻接点；因此，点；因此，来来。 该该应该是应该是“”：?第第10章章 图及其应用图及其应用 77这样，这样， 开始时，将其置空；开始时，将其置空； 在每访问一个顶点时，将其入队；在每访问一个顶点时，将其入队； 在访问完一个顶点的所有后继后，将其出队；在访问完一个顶点的所有后继后，将其出队； 若队列为空，说明每一个访问过的顶点的所有后若队列为空，说明每一个访问过的顶点的所有后继均已访问完毕，遍历结束。继均已访问完毕，遍历结束。第第10章章 图及其应用图及其应用 78访问v0; Visitedv0=1; v0入队;队空 v =队头元素; w = FirstA

36、djVertex(g,v)访问w; Visitedw=1; w入队w = =0 w 已访问过 w= NextAdjVertex(g , v, w)NNNYYY结束结束第第10章章 图及其应用图及其应用 79 void BFS(Graph g, int v0) visit(v0); visitedv0=True; setnull(Q); ent_queue(Q, v0)； while ( ! empty(Q) v = out_queue(Q); w=FirstAdj(g, v); 第第10章章 图及其应用图及其应用 80 while (w! = -1 ) if (!visited(w) visi

37、t(w); visitedw=True; ent_queue(Q, w); w=NextAdj(g, v, w); 第第10章章 图及其应用图及其应用 81 分析上述算法，分析上述算法，。 则当结点则当结点v出队后，出队后，由于访问所有顶点的邻接点由于访问所有顶点的邻接点的总的时间复杂度为的总的时间复杂度为O(d0+d1+d2+dn-1)=O(e)， 因此因此图采用邻接表方式存储，图采用邻接表方式存储，由于找每个顶点的由于找每个顶点的邻接点时邻接点时 第第10章章 图及其应用图及其应用 82： 与非连通图的深度优先搜索一样，非连通的或与非连通图的深度优先搜索一样，非连通的或非强连通图的广度优先

38、搜索从图中某一个顶点出发，非强连通图的广度优先搜索从图中某一个顶点出发，也不能访问到图中所有顶点，而只能访问到一个连也不能访问到图中所有顶点，而只能访问到一个连通子图（既连通分量）或只能访问到一个强连通子通子图（既连通分量）或只能访问到一个强连通子图（既强连通分量）。图（既强连通分量）。 遍历算法实现时，对所有顶点进行循环，反复调遍历算法实现时，对所有顶点进行循环，反复调用连通图的广度优先搜索遍历算法即可。具体可以用连通图的广度优先搜索遍历算法即可。具体可以表示如下：表示如下：第第10章章 图及其应用图及其应用 83for(int i=1;i=n;i+) if(!visitedi) bfs(i

39、) ; 分析上述过程，每个顶点至多进一次队列。遍历分析上述过程，每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接图的过程实质上是通过边或弧找邻接 点的过程。因此点的过程。因此。 第第10章章 图及其应用图及其应用 84 10.1 图的概念 10.2 图的存储 10.3 图的遍历 10.4 生成树和最小生成树 10.5 最短路径 10.6 有向无环图的应用第第10章章 图及其应用图及其应用 85 深度优先及广度优先遍历图的过程中，所深度优先及广度优先遍历图的过程中，所一起构成连通图的一起构成连通图的。它是连通图的一颗生成树。它是连通图的一颗生成树。是一个极小连通子图，它含有图中全部顶

40、点，是一个极小连通子图，它含有图中全部顶点，但只有但只有n-1n-1条边。条边。 由深度优先搜索遍历得到的生成树，称为深度优由深度优先搜索遍历得到的生成树，称为深度优先生成树，由广度优先搜索遍历得到的生成树，称为先生成树，由广度优先搜索遍历得到的生成树，称为广度优先生成树。广度优先生成树。第第10章章 图及其应用图及其应用 86DFS生生成成树树v0v1v2v4v4v3邻接表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFS生生成成树树v0v1v3v2v4第第10章章 图及其应用图及其应用 87 一般情况下，若图中的每条边给定了权值，这时，一般情况下，若图中的

41、每条边给定了权值，这时，我们所关心的不是生成树，而是生成树中边上权值之我们所关心的不是生成树，而是生成树中边上权值之和。和。 图的生成树不是唯一的。图的生成树不是唯一的。 当按深度和广度优先搜索当按深度和广度优先搜索法进行遍历就可以得到两种不同的生成树。法进行遍历就可以得到两种不同的生成树。第第10章章 图及其应用图及其应用 88连通网连通网 的生成树。的生成树。 413265413265(a)413265(b)413265(c) 其中其中(a)的权值之和为的权值之和为26, (b)的权值之和为的权值之和为16, (c)的权的权值之和为值之和为15, 可以证明可以证明(c)为一棵最小生成树。为

42、一棵最小生成树。第第10章章 图及其应用图及其应用 89欲在欲在n个城市间建立通信网，则个城市间建立通信网，则n个城市应铺个城市应铺n-1条线条线路；但因为每条线路都会有对应的经济成本，而路；但因为每条线路都会有对应的经济成本，而n个城个城市可能有市可能有n(n-1)/2 条线路，那么，条线路，那么，如何选择如何选择n1条线路，条线路，使总费用最少？使总费用最少？顶点顶点表示城市，有表示城市，有n个；个；边边表示线路，有表示线路，有n1条；条；边的权值边的权值表示线路的经济代价；表示线路的经济代价；连通网连通网表示表示n个城市间通信网。个城市间通信网。显然此连通网显然此连通网是一个是一个生成树

43、！生成树！第第10章章 图及其应用图及其应用 90 如何选择其中的如何选择其中的n-1条线路条线路(边边)在在n个城市间建成个城市间建成全都能相互通讯的网全都能相互通讯的网, 并且总的建设花费为最小并且总的建设花费为最小? 这就是求该网络的最小生成树问题。这就是求该网络的最小生成树问题。 第第10章章 图及其应用图及其应用 91有如下重要有如下重要： 设设 N=(V, VR) 是一连通网，是一连通网，U 是顶点集是顶点集V的一个的一个非空子集。非空子集。 若（若（u , v）是一条具有最小权值的边，）是一条具有最小权值的边， 其中其中uU， vV-U， 则存在一棵包含边（则存在一棵包含边（u

44、, v）的）的最小生成树。最小生成树。 我们可以利用我们可以利用MST性质来生成一个连通网的最小性质来生成一个连通网的最小生成树。生成树。便是利用了这个性质。便是利用了这个性质。 第第10章章 图及其应用图及其应用 92 1. 普里姆算法普里姆算法 每一次在满足如下条件的边中，选一条最小权值每一次在满足如下条件的边中，选一条最小权值的边。的边。一端顶点已入选，而另一端未选。一端顶点已入选，而另一端未选。第第10章章 图及其应用图及其应用 93 假设假设N=(V, VR)是连通网，是连通网，TE为最小生成树中边的为最小生成树中边的集合。集合。（1） 初始初始U=u0(u0V), TE= （2）

45、在所有在所有uU, vV-U的边中选一条代价最小的的边中选一条代价最小的边边(u0,v0 )并入集合并入集合TE，同时将，同时将v0并入并入U； （3） 重复（重复（2），）， 直到直到U=V为止。为止。 此时，此时，TE中必含有中必含有n-1条边，则条边，则T=（V，TE）为）为N的最小生成树。的最小生成树。 第第10章章 图及其应用图及其应用 94413265利用普里姆算法从利用普里姆算法从v1开始构造最小生成树。开始构造最小生成树。1第第10章章 图及其应用图及其应用 95 可以看出，可以看出， 普利姆算法逐步增加普利姆算法逐步增加U中的顶点，中的顶点， 可称为可称为“加点加点法法”。

46、为了实现这个算法需要设置一个为了实现这个算法需要设置一个对每个顶点对每个顶点vV-U，在辅助数组，在辅助数组中存在一个分量中存在一个分量closedgev,它包括两个域它包括两个域和和, 其中其中lowcost存储该边上的权，存储该边上的权， 显然有显然有 closedgev.lowcost=Min(cost(u,v)|uU) struct closedgeMAX_V_N; 第第10章章 图及其应用图及其应用 96 typedef AdjMatrix; 第第10章章 图及其应用图及其应用 97typedef ArcNode; 第第10章章 图及其应用图及其应用 98假设开始顶点就选为顶点假设开

47、始顶点就选为顶点1，首先有，首先有U=1，U-V=2，3，4，5，6i12456closedgei.adjvex111111closedgei.lowcost065 06246063205546505135065160413265413265for (i=1; i=gn.vexnum; i+) closedgei.adjvex=k0; / k0U closedgei.lowcost=gn.arcsk0i.adj; 第第10章章 图及其应用图及其应用 99i12345closedgei.adjvex133133closedgei.lowcost0505 6 for ( i=1 ; i=gn.ve

48、xnum; i+) if ( gn.arcsk1i.adj closedgei.lowcost) closedgei.lowcost= gn.arcsk1i.adj; closedgei.adjvex=k1; 413265U=1, 3，U-V=2，4，5，606246063205546505135065160i12456closedgei.adjvex111111closedgei.lowcost065 第第10章章 图及其应用图及其应用 100i12356closedgei.adjvex133636closedgei.lowcost050 60 U=1, 3, 6，U-V=2，4，54132

49、6506246063205546505135065160i12345closedgei.adjvex133133closedgei.lowcost0505 6 第第10章章 图及其应用图及其应用 101i12356closedgei.adjvex133636closedgei.lowcost050 60 413265U=1, 3, 6, 4， U-V=2，5i13456closedgei.adjvex133436closedgei.lowcost00060 06246063205546505135065160第第10章章 图及其应用图及其应用 102i123456closedgei.adjve

50、x123426closedgei.lowcost0000 0 U=1, 3, 6, 4, 2，U-V=5413265i13456closedgei.adjvex133436closedgei.lowcost00060 06246063205546505135065160第第10章章 图及其应用图及其应用 103U=1, 3, 6, 4, 2, 5， U-V= i123456closedgei.adjvex123456closedgei.lowcost000000 413265i123456closedgei.adjvex123426closedgei.lowcost0000 0 0624606