数据结构第6章

1、JYP1第6章 图 本章学习一种更普遍的非线性结构图，特别是图的基本表示和基本问题的解决方法。 JYP26.1 图的基本定义 图G由集合V和集合E组成，记为G = (V, E)。其中，V(G) 是顶点的有限集合，且V ；E(G) 是边的有限集合，边由V中的不同顶点对构成。一个图的顶点和边可附加额外信息，并用于计算机应用建模。例如，一个用顶点表示城市，边表示城市间距离的图可用于交通网络的研究。图的典型应用领域：电路分析、寻找最短路由，通信网络、项目规划，鉴别化合物、统计力学、遗传学、控制论、语言学，以及社会科学等。JYP3 图可分为无向图和有向图：在无向图中，E = (u, v) | u, v

2、V，顶点对 (u, v) 是无序的，(u, v) 和 (v, u) 表示同一条边。在有向图中，E = | u, v V，顶点对 是有序的，表示一条从u到v的有向边；u和v分别是边的尾（tail）和头（head）。因此， 和 表示两条不同的边。JYP4 下面给出了三个图。其中，G1和G2是无向图，G3是有向图。注意有向图的边用带箭头的线段表示。 JYP5 这些图的顶点集合与边集合分别为：V(G1) = 0, 1, 2, 3E(G1) = (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)V(G2) = 0, 1, 2, 3, 4, 5, 6E(G2) =

3、 (0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)V(G3) = 0, 1, 2E(G3) = , , 。JYP6 限制：（1） 图中不能有从一个顶点v到其自身的边。（2） 图中同一条边不可以出现多次。在n个顶点的无向图中，不同的顶点对 (u, v)（u v）最多有n (n 1)/2个。具有n个顶点，n (n 1)/2条边的无向图称为完全无向图，如G1。n个顶点的有向图则最多有n (n 1) 条边。JYP7 如果 (u, v) 是 E(G) 中的一条边，则称顶点u与v互为邻接，边 (u, v) 与顶点u和v相关联。在G2中，与顶点1邻接的顶点为0，3

4、和4，与顶点2相关联的边为(0, 2), (2, 5) 和 (2, 6)。如果 是一条有向边，则称顶点u邻接到顶点v，v邻接自u，边 与顶点u和v相关联。在G3中，与顶点1相关联的边为 , 和 。在许多应用中，可以给图的边分配权重。这些权重可以表示距离、时间以及代价等信息。这类图称为加权图。JYP8 设G和G为两个图。如果V(G) V(G)且E(G) E(G)，则G是G的子图。 G1的一些子图如下：JYP9 G3的一些子图如下：JYP10 对于无向图G，如果 (u, i1), (i1, i2), , (ik, v) 是属于E(G)的边，则称顶点序列 u, i1, i2, , ik, v是从u到

5、v的路径。对于有向图G，如果 , , , 是属于E(G)的边，则称顶点序列 u, i1, i2, , ik, v是从u到v的路径。对于不加权图，一条路径的长度是该路径上边的条数。对于加权图，一条路径的长度是该路径上各边的权重之和。JYP11 若在一条路径的顶点序列中，除了起点和终点以外，所有顶点都互不相同，则称该路径为简单路径。 例如，在G1中，0, 1, 3, 2 是简单路径，而0, 1, 3, 1却不是；在G3中，0, 1, 2是简单有向路径，而1, 0, 1, 2却不是。起点和终点相同的简单路径称为环。 例如，0, 1, 2, 0 是G1中的一个环，0, 1, 0是G3中的一个有向环。J

6、YP12 在无向图G中，称两个顶点u和v是连通的当且仅当G中存在一条从u到v的路径。称无向图G是连通的当且仅当对于V(G) 中的每一对不同的顶点u和v，G中都存在一条从u到v的路径。JYP13 G1和G2是连通的，而下面的G4却不是：JYP14 无向图G的一个连通分量H是其最大连通子图。这里最大是指，G中不存在既连通又真包含H的子图。 例如，G4有两个连通分量：H1和H2。称有向图G是强连通的当且仅当对于V(G) 中的每一对不同的顶点u和v，G中不仅存在一条从u到v的有向路径而且存在一条从v到u的有向路径。 G3不是强连通的，因为其中不存在从顶点2到1的路径。有向图G的一个强连通分量是其最大强

7、连通子图。JYP15 G3的两个强连通分量是：一个顶点的度是与该顶点相关联的边的条数。在G是有向图的情况下，顶点v的入度是以v为头的边的条数，顶点v的出度是以v为尾的边的条数。 例如，G1中顶点0的度是3。G3的顶点1的入度为1，出度为2，度为3。 JYP16 设图G有n个顶点，e条边，di是顶点i的度，则树是一个连通的无环图。JYP17无向图的抽象数据类型定义：template class Graph / 对象: 由一个非空的顶点集合和一个无向边/集合构成，每条边是一个顶点对public: Graph ( );/ 建立一个空图 void InsertVertex (Vertex v); /

8、将顶点v插入图中，v无/ 相关联的边 void InsertEdge (Vertex u,Vertex v); / 将边 (u, v) 插入图中 void DeleteVertex (Vertex v); / 删除顶点v 及所有关联的边 void DeleteEdge (Vertex u,Vertex v); / 删除边 (u, v) Boolean IsEmpty ( ); / 判断图的顶点集合是否为空 List Adjacent(Vertex v); / 返回由所有与v邻接的顶/ 点构成的表; JYP186.2 图的表示 下面讨论三种最常用的表示，即邻接矩阵，邻接表和邻接多表。具体采用何种

9、表示取决于实际应用对图的功能的需求。6.2.1 邻接矩阵 设G = (V, E) 是一个有n个顶点的图，n1。G的邻接矩阵A是一个n n的二维数组，且满足： 1 当且仅当 (i, j)（或）是E(G)中 的一条边Aij = 0 否则JYP19 G1和G3的邻接矩阵： 注意，无向图的邻接矩阵是对称的，有向图的邻接矩阵则不一定是对称的。JYP20 G4的邻接矩阵：JYP21 根据邻接矩阵，很容易判断是否存在一条关联任意两个顶点i和j的边。 对于无向图，顶点i的度是矩阵的第i行元素之和。 对于有向图，顶点i的出度是第i行元素之和，入度则是第i列元素之和。 在边(i, j)（或）加权的情况下，Aij既

10、可用于表示边的存在，又可用于保存权重信息。JYP22 采用邻接矩阵，即使回答“图G中有多少条边？”这样的基本问题也需要O(n2)时间。 设e是图G中边的条数，当e n2时，如果采用只存储图G中存在的边的表示方法，则可使求解上述问题所需的时间减少为O(e+n)。 由此产生了邻接表。JYP236.2.2 邻接表 将邻接矩阵的n行表示为n个链接表。图G中的每一个顶点都有一个表。表i的结点表示顶点i所邻接到的所有顶点，如下所示： 每个结点至少有两个字段：data和link。data存放邻接自顶点i的顶点号。JYP24G1的邻接表：JYP25G3的邻接表：JYP26G4的邻接表：JYP27 注意，每个表

11、中的顶点不必有序。每个表有一个头结点。全部头结点顺序存储，以便随机访问任意顶点的邻接表。 基于邻接表的类Graph：class Graph private: List* HeadNodes; int n;public: Graph (const int vertices = 0): n(vertices) HeadNodes = new Listn; ;JYP28设有n个顶点和e条边无向图需要n个头结点和2e个表结点。顶点i的度可通过计数表i中的结点个数确定。整个图的边数可用O(e+n)时间确定。JYP29有向图需要n个头结点和e个表结点。顶点i的出度可通过计数表i中的结点个数确定。为了确定任

12、意顶点的入度，可先将数组cn初始化为0，然后遍历邻接表。每访问到一个data值为i的结点，就将ci累加1。遍历完成后，ci即为顶点i的入度，0in1。整个图的边数也可用O(e+n)时间确定。JYP30 如果经常需要访问邻接到顶点i的顶点，则可以再建立图的反向邻接表。每一个顶点都有一个表。表i表示邻接到顶点i的所有顶点，如下所示：JYP31G3的反向邻接表如下所示：JYP32 还可以简化稀疏矩阵的链表表示结构，用于表示图。这时，每个结点表示一条边，并有四个字段。结点结构为：其中，tail和head分别表示边的尾顶点和头顶点。通过col，将具有相同头的边结点链接起来（起反向邻接表作用）；通过row

13、，将具有相同尾的边结点链接起来（起邻接表作用）。头结点仍然顺序存储。 JYP33采用这种方法，G3表示为下面的正交表结构： 在以上表示中，当需要保存边的权重信息时，可以在结点中增加字段weight。JYP346.2.3 邻接多表 邻接表用于无向图时，每条边 (u, v) 表示为两个结点。 在有的应用中，要求不论从哪个顶点访问一条边，都要将这条边打上已访问标记。为此，可以以边为中心，构建图的邻接表，从而形成邻接多表。 在邻接多表中，一个结点正好与一条边对应，但每个结点处于两个表中（分别为边的两个顶点相应的邻接表）。此结点结构为：JYP35其中，m是边的访问标记，path1用于链接含顶点verte

14、x1的边的结点，path2用于链接含顶点vertex2的边的结点。基于邻接多表的类Graph可如下定义：enum Boolean FALSE, TRUE;class Graph;/ 向前声明class GraphEdge friend Graph;private: Boolean m; int vertex1, vertex2; GraphEdge *path1, *path2;JYP36typedef GraphEdge *EdgePtr;class Graph private: EdgePtr *HeadNodes; int n;public: Graph(const int);Graph

15、:Graph(const int vertices = 0) : n(vertices) HeadNodes = new EdgePtrn; / 建立头结点数组 for (int i = 0; i n; i+) HeadNodesi = 0;JYP37G1的邻接多表如下： JYP38 假设结点p表示的边含顶点u和v，则已知u求v需要如下判断： if ( pvertex1 = u ) v = pvertex2; else v = pvertex1; 将一条边加入邻接多表的操作只需要O(1)时间，如下列程序所示：void Graph:InsertEdge (int u, int v ) / 将边(

16、u, v) 加入/ 邻接多表 GraphEdge *p = new GraphEdge;/ 建立一个新的边结点 pm = FALSE; pvertex1 = u; pvertex2 = v; ppath1 = HeadNodes u; ppath2 = HeadNodes v; HeadNodes u = HeadNodes v = p;JYP396.3 连通图的遍历 给定一个有n个顶点的连通图G = (V, E) 和V(G) 中的一个顶点v，对图G的遍历是指，从v出发，访问V(G) 中所有从v（经过E(G) 中的边）可到达的顶点，且只访问每个顶点一次。 由于图中可能存在环路，为防止重复访问顶

17、点，需设置一个访问标记数组visitedn。JYP40连通图遍历的两种最基本的方法： 深度优先搜索 广度优先搜索 虽然这些方法既适用于无向图又适用于有向图，但为了简化分析，假设下面讨论的是无向图。JYP416.3.1 深度优先搜索 深度优先搜索: 首先访问起始顶点v; 接着在与v邻接的顶点中选一个未被访问过的顶点w，再以w为起始顶点启动新的深度优先搜索; 当到达一个所有邻接顶点都被访问过的顶点u时，则回退到最近刚被访问过并有一个未被访问过的邻接顶点x的顶点，再以x为起始顶点启动新的深度优先搜索; 当不存在从任何已访问过的顶点可到达的未被访问顶点时，搜索结束。JYP42 下列程序给出了实现以上过

18、程的递归算法:void Graph:DFS ( ) / 驱动程序 visited = new Booleann;/ 设visited已说明为Graph的/ Boolean* 数据成员 for (int i = 0; i n; i+) visitedi = FALSE; / 初始化，所有/ 顶点都未被访问 DFS (0);/ 从顶点0开始搜索 delete visited; JYP43void Graph:DFS (const int v) / 递归核心，访问所有先前未 / 被访问过，且可从v到达的顶点 visitedv = TRUE; for (每一个与v邻接的顶点w) / 具体代码与图的表示

19、有关 if (!visitedw ) DFS (w);JYP44 例6.1 考虑下面的图G5：JYP45 假设DFS(v) 按顶点号升序选取与v邻接的顶点w。如果从顶点0出发作深度优先搜索，则G中顶点被访问的顺序为：0，1，3，7，4，5，2，6。 如果用顶点编号表示被访问顶点，（顶点编号）表示检查先前已被访问过的顶点，（回退到x）表示回退到顶点x，则实际的搜索轨迹为： 0，1，（0），3，（1），7，（3），4，（1），（7），（回退到7），5，2，（0），（5），6，（2），（7），（回退到2），（回退到5），（7），（回退到7），（6），（回退到3），（回退到1），（4），（回退到0），

20、（2）。JYP46 分析：假设图G有e条边，由于G是连通的，所以en1。 若采用邻接表表示，算法可顺着顶点v的邻接表找到所有与v邻接的顶点w。在每个顶点v上只调用DFS一次，需要O(dv)时间，这里dv是顶点v的度。 整个搜索访问n个顶点，所需时间为O( ) = O(e)。 若采用邻接矩阵表示，确定所有与v邻接的顶点w需要O(n)时间，总的搜索时间为O(n2)。 JYP476.3.2 广度优先搜索 广度优先搜索: 首先访问起始顶点v； 接着依次访问所有与v邻接的未被访问过的顶点； 然后再依次访问所有与这些新被访问的顶点邻接的未被访问过的顶点，如此继续，直到所有顶点都被访问为止。JYP48 可用

21、一个队列q保存需要访问的顶点，下列程序给出了实现以上过程的算法：void Graph:BFS (int v) / 从顶点v开始 visited = new Booleann; / 设visited已说明为Graph的/ Boolean* 数据成员 for (int i = 0; i n; i+) visitedi = FALSE; / 初始化， / 所有顶点都未被访问 visitedv = TRUE; Queue q;/ q是一个队列 q.Add(v); / 将顶点v加到队列q中JYP49while (!q.IsEmpty ( ) v = *q.Delete(v); / 从队列q中删除顶点 f

22、or (每一个与v邻接的顶点w) / 具体代码与图的表示有关 if (!visitedw ) visitedw = TRUE; q.Add(w); / while结束 delete visited; JYP50 例6.2 仍然考虑图G5，并假设其邻接表的结点按相应顶点号升序排列。 如果从顶点0出发作广度优先搜索，则首先访问顶点0，接着访问顶点1和2，然后访问顶点3，4，5和6，最后访问顶点7。JYP51 分析：每个顶点加入队列一次，所以while循环迭代n次。 若采用邻接表表示，该循环的总代价为O( ) = O(e)，这里dv是顶点v的度。 若采用邻接矩阵表示，确定所有与v邻接的顶点w需要O(

23、n)时间，总的时间为O(n2)。 JYP526.3.3 生成树 由于图G是连通的，所以从任意顶点出发的深度优先或广度优先搜索都将访问G中所有顶点，并将E(G)划分为两个集合：T和N。 T是搜索过程中所用到的边的集合，又称为树边集合；N是图中其余边的集合，又称为非树边集合。 初始设置T = ，并将语句 T = T (v, w) 插入DFS和BFS的if子句中，可求得T。 T中的边构成了一棵包含G的所有顶点的树。任何只由G的边构成，并包含G的所有顶点的树称为G的生成树。JYP53 由深度优先搜索形成的生成树称为深度优先生成树，下图是从G5的顶点0开始作深度优先搜索形成的生成树：JYP54 由广度优

24、先搜索形成的生成树称为广度优先生成树，下图是从G5的顶点0开始作广度优先搜索形成的生成树：JYP55 若将非树边 (v, w) 加入任何生成树T中，则会形成环路。该环路由边 (v, w) 和T中从w到v的路径构成。 例如，将 (1, 4) 加入前面的深度优先生成树中后形成的环为1，3，7，4，1。 此性质可用于建立独立的电路方程式。 作为第二个性质，生成树是G的最小子图G，使得V(G) = V(G) 且G是连通的。任何有n个顶点的连通图至少有n1条边，而有n1条边的连通图都是树。JYP566.4 图的连通性 6.4.1 连通分量 对于可能不连通的无向图G，可以通过调用DFS或BFS并检查是否存

25、在任何未被访问的顶点来判定G是否连通。 设v是尚未被访问的顶点，反复调用DFS(v) 或BFS(v) 即可生成G的连通分量。JYP57 下面是生成G的连通分量的算法：void ponents ( ) / 求图的连通分量 visited = new Booleann;/ 设visited已说明为Graph/ 的Boolean* 数据成员 for (int i = 0; i n; i+) visitedi = FALSE; / 初始化，/ 所有顶点都未被访问 for ( i = 0; i n; i+) if (!visitedi ) DFS (i); / 求包含顶点i的连通分量 ponent( )

26、; delete visited; JYP58 函数 ponent输出最近一次调用DFS访问的所有顶点，以及关联这些顶点的所有边。 分析：若采用邻接表表示，DFS的总时间为O(n + e)。如果DFS产生一个本次搜索新访问的顶点表，再利用邻接表，则输出连通分量的顶点以及相关联的边的总时间为O(n + e)。for循环的控制和判断需要O(n)时间。因此，生成全部连通分量的时间为O(n + e)。 若采用邻接矩阵表示，算法所需要的时间为O(n2)。JYP596.4.2 双连分量 双连分量在连通性方面比一般的连通分量具有更高的要求，生成双连分量的操作也更复杂一些。 假设无向图G是连通的，下面给出双连

27、分量的正式定义。 定义：G的顶点v是一个关节点当且仅当从G中删除v及其关联的边后，剩下的图至少有两个连通分量。JYP60 例如，在下面的连通图G6中，顶点1，4和7是关节点。JYP61 定义：双连通图是没有关节点的连通图。 图G5是双连通的，但图G6不是双连通的。 在表示通信网络的图中，边表示通信链路，顶点表示通信站点，关节点显然是薄弱环节。 定义：一个连通图G的双连分量是G的最大双连通子图。 JYP62 图G6包含四个双连分量，如下所示： JYP63 不难发现，同一个图的两个双连分量最多有一个共同顶点。由此可推出，一条边不可能出现在两个或两个以上的双连分量中。因此，图G的双连分量划分E(G)

28、。 图G的双连分量可利用G的任何深度优先生成树求得。JYP64 图G6的以顶点0为根的深度优先生成树如下：JYP65其中，非树边用虚线表示。顶点旁的数字称为该顶点的深度优先数，简称为dfn。一个顶点的dfn表示该顶点在深度优先搜索中被访问的顺序。 例如，在前面的G6生成树中，dfn(0) = 1，dfn(1) = 2，以及dfn(7) = 5。 注意，在深度优先生成树中，如果顶点u是v的祖先，则dfn(u) dfn(v)。JYP66 相对于生成树T，当且仅当u是v的祖先或v是u的祖先时，非树边 (u, v) 才是一条回边。 例如，(4, 1) 和 (6, 7) 是回边。 不是回边的非树边称为横

29、边。根据深度优先搜索的规律，相对于任意一个图的任何深度优先生成树，该图不可能有横边。JYP67 因此，深度优先生成树的根是关节点的充分必要条件是它至少有两个子女。 任何其它顶点u是关节点的充分必要条件是u至少有一个子女w，使得经过只由w，w的后代以及一条回边构成的路径不可能到达u的祖先，因为删除顶点u及其关联的边将使w及其后代与u的祖先断开联系。JYP68 假设顶点w的祖先包括w本身。 为了表示一个顶点经过其后代以及一条回边所能到达的最高祖先，对于图G的每个顶点w，定义low(w) 为从w经过其后代以及一条回边所能到达的最高祖先的dfn。 显然，low(w)是从w经过其后代以及一条回边所能到达

30、的顶点的dfn中最低的，并可由以下公式计算： low(w) = min dfn(w), min low(x)| x是w的一个子女, min dfn(x)| (w, x) 是一条回边JYP69 于是，u是关节点的充分必要条件是：u或者是至少有两个子女的深度优先生成树的根，或者u不是根结点但有一个子女w，使得low(w)dfn(u)。 下面是G6的以顶点0为根的深度优先生成树中各顶点的dfn和low值： 顶点01234567 dfn12734685 low12522555JYP70 修改DFS可得到计算一个连通图各顶点的dfn和low值的函数DfnLow：void Graph:DfnLow (co

31、nst int x ) / 在顶点x开始DFS num = 1; / num是Graph 的类型为int的数据成员 dfn = new intn; low = new intn; / dfn和low都是Graph 的 / 类型为int *的数据成员 for ( int i = 0; i n; i+ ) dfni = lowi = 0; DfnLow ( x, -1 ); / x是根，其双亲是伪顶点-1 delete dfn; delete low;JYP71void Graph:DfnLow ( int u, int v ) / 从u开始深度优先搜索并 / 计算dfn和low。v是u的双亲 d

32、fnu = lowu = num+; for (每一个与u邻接的顶点w) / 具体代码与图的表示有关 if (dfnw = 0) / w 是未被访问顶点 DfnLow (w, u); lowu = min2 (lowu, loww); / min2(x,y)返回x和y的 / 较小者 else if (w != v) lowu = min2 ( lowu, dfnw ); / 回边。注 / 意(v, u)不是回边JYP72 注意，在深度优先生成树中，若v是u的双亲，则 (u, v) 一定不是回边。 函数DfnLow(u, v)的参数v就是为区分这种情况而设的。 深度优先搜索的第一个顶点x无双亲，

33、因此对其的调用形式为DfnLow(x, 1)。 函数DfnLow(u, v)用到的另一个函数min2返回其两个参数的较小者。JYP73 在DfnLow的基础上进一步处理，可以将连通图的边划分为双连分量。 注意，当DfnLow(w, u)返回后，loww已计算好。如果lowwdfnu，则可确定一个新的双连分量。 通过将搜索时首次遇到的边存入栈中，可以求得一个双连分量的全部边。JYP74 设深度优先搜索最近访问的顶点是u，且顶点w与u邻接，则在以下两种情况中，(u, w)是首次遇到的边： （1）w是未被访问的顶点 （2）w是已被访问的顶点而且是u的祖先 由于未被访问的顶点的dfn值初始化为0，祖先

34、的dfn值小于后代的，所以两种情况都可归结为dfnw dfnu。 JYP75 函数Biconnected实现了上述过程：void Graph:Biconnected ( ) num = 1; dfn = new intn; low = new intn; for ( int i = 0; i 1。 dfnu = lowu = num+;JYP76 for (每一个与u邻接的顶点w) / 具体代码与图的表示有关 if (v != w & dfnw = dfnu) cout “新双连分量：” endl; do 从栈S删除一条边; 设此边为 (x, y); cout x , y 0个顶点，e条边。

35、最典型的构造最小生成树的算法： 克鲁斯卡尔（Kruskal）算法 普瑞姆（Prim）算法JYP79 这两个算法都采用了一种称为贪心方法的设计策略。 贪心方法分阶段构造最优解。 在每个阶段，根据一定的准则做出当时可能的最佳决策。由于后续阶段不可更改本阶段的决策，所以必须保证该决策将导致可行的解，即满足问题规定的约束。JYP80 具体应用到构造最小生成树的情况，应采用最小代价准则，而问题的解必须满足下列约束： （1）只能选用图中的边 （2）正好用n 1条边 （3）所选用的边不形成环路。JYP816.5.1 克鲁斯卡尔算法 设T是构造中的最小生成树，克鲁斯卡尔算法通过每次往T中加入一条边构造最小生成

36、树。 加入T的边按代价不减少的顺序选择。 如果一条边与已在T中的边不形成环路，则将其加入T中。 如果G是连通的，则选入T中的边正好是n 1条。JYP82 例6.3 构造下图的最小生成树JYP83初始时未选任何边： 加入边 (1, 6) 后：JYP84加入边(4, 5)后： 加入边(1, 2)后：JYP85加入边 (5, 6) 后： 这时，在尚未考虑的边中，(2, 6) 的代价最小，但 (2, 6) 的加入将在生成树中形成环路，因此将其放弃。JYP86加入边(0, 5)后： 下一条需考虑的边是 (4, 6)，由于 (4, 6) 的加入将在生成树中形成环路，因此将其放弃。JYP87最终，加入边(3

37、, 4) 后：JYP88 克鲁斯卡尔算法的框架 ：T = ;while (T包含的边少于n-1条) & (E非空) 从E中选一条代价最小的边 (v, w); 从E中删除 (v, w); if (v, w)不会在T中形成环路) 将 (v, w) 加入T中; else 放弃 (v, w);if (T包含的边少于n-1条) cout “不存在最小生成树” endl;JYP89 初始时，集合E包含图G的全部边。 如果将E组织为最小堆，则选择并删除代价最小的边可用O(log e) 时间完成。构造最小堆只需O(e) 时间。 算法最多选择并删除e条边，其总代价为O(e log e)。 将T中同一个连通分量的

38、顶点组织为一个集合。如果两个顶点v和w处于同一个集合，则边 (v, w) 的加入将在T中形成环路。利用并查集算法，判断e条边的总时间为O(e.(e, n)。 因此，算法的时间复杂性为O(e log e)。JYP90 定理6.1：对于任意给定的无向连通图G，克鲁斯卡尔算法构造G的一棵最小代价生成树。 证明：我们需要证明：（a）只要存在生成树，克鲁斯卡尔算法就能构造一棵生成树；（b）所构造的生成树代价最小。 对于（a），注意克鲁斯卡尔算法只放弃形成环路的边，而删除一个连通图的环路中的一条边所得到的图仍然是连通的。 因此，如果G一开始是连通的，则T和E的边总是构成一个连通图，算法不可能以E = 且|

39、T| 0）。注意k也是在U中而不在T中的边的条数。 可通过将U转换为T证明T和U代价相同。JYP92 这种转换经过k个步骤。每经过一个步骤，在T中而不在U中的边的条数减少1，且转换后U的代价不变。最终，经过k步转换，U的代价和初始时相同，但已完全由T的边构成。这意味着T具有最小代价。 每一步转换需将T中的一条边e加到U中，并从U删除一条边f。边e和f按下列方法选择： （1） 设e是在T中而不在U中的代价最小的边。由于k 0，这样的边一定存在。 （2） e加入U后将形成唯一的环路。设f是该环路中不在T中的边。由于T中无环路，此环路一定存在一条不在T中的边。JYP93 按照e和f的选择方法，V =

40、 U + e f是一棵生成树，且T有k 1条边不在V中。 下面需要证明代价(V) = 代价(U)。 显然，代价(V) =代价(U) + 代价(e) 代价(f)。 代价(e)不会小于代价(f)，否则生成树V的代价比U的还小，而这是不可能的。JYP94 假设代价(e) 代价(f)，则克鲁斯卡尔算法在e之前考察f。由于f不在T中，算法在考察时一定放弃了f。因此，f与T中代价小于等于代价(f) 的边一定形成了环路。由于e是在T中而不在U中的代价最小的边，T中代价小于等于代价(f) 的边都在U中，因而U中存在环路。但U是生成树，不可能有环路。可见，假设代价(e) 代价(f)导致矛盾。 于是，唯一可能的是

41、代价(e) = 代价(f)。 因此，代价(V) = 代价(U)。JYP956.5.2 普瑞姆算法 设TV是最小生成树的已选顶点集合，T是最小生成树的已选边集合。普瑞姆算法首先任选图G中一个顶点u，将u加入TV中。 然后将一条代价最小的边 (u, v) 加入T中，使得T (u, v)仍然是一棵树。 重复上述步骤，直到T包含n 1条边为止。 注意，(u, v) 关联的两个顶点必有一个在TV中，另一个不在TV中。JYP96 普瑞姆算法的框架:TV = 0;/ 从顶点0开始构造，假设G至少有一个顶点for (T = ; T包含的边少于n -1条; 将(u, v)加入T) 令 (u, v) 为满足 u

42、TV 且 v TV 的代价最小的边; if (不存在这样的边) break; 将v加入TV;if (T包含的边少于n-1条) cout “不存在最小生成树” endl ;JYP97 用普瑞姆算法构造下图的最小生成树的过程：JYP98JYP99JYP100JYP101 设 是不属于TV的顶点集合。 对于任何v ，定义nearv为TV中使 cost(nearv, v)最小的顶点（若(v, w)E，则设cost(v, w) = ），则 cost(nearv,v) = 。 下一个加入TV的顶点v应满足：v ，且cost(nearv,v) = 。下一条加入T的边自然是 (nearv,v)。JYP102

43、设w是 中与v邻接的顶点。顶点v加入TV之后，如果cost(nearw,w) cost(v, w)，则将nearw改为v。 由此可以有效地实现普瑞姆算法。 如果用邻接矩阵costij表示图G，则算法的时间复杂性是O(n2)，因为算法总共选n 1个顶点，每选一个顶点v及处理v对nearw（w 且w与v邻接）的影响最多只需O(n)时间。JYP103 如果用邻接表表示图G并利用斐波纳契堆，则可使算法的性能更好。对于v ，定义distv = cost(nearv,v)，可理解为顶点v到已构造的部分最小生成树的最近距离。 每次往TV中加入一个顶点，算法都需要确定顶点v，使得v ，且distv = 。这对

44、应于 上的删除最小元素操作。 由于v加入TV， 中与v邻接的顶点的dist值可能减少。这对应于 上的关键字减少操作。JYP104 关键字减少操作的总次数最多是图中边的条数。删除最小元素操作的总次数是n 1。 初始时， 含n 1个顶点。如果以dist为关键字，将 组织为斐波纳契堆，则需要n 1次插入操作初始化斐波纳契堆。 接着需要执行n 1次删除最小元素操作和最多e次关键字减少操作。所有这些操作的代价是各操作的分摊代价之和，即 O(n log n + e)。 因此，算法的时间复杂性变为O(n log n + e)。当e远小于n2时，这显然是一种改进。JYP1056.6 最短路径和传递闭包 一条路

45、径的长度定义为该路径的边长之和。路径的开始顶点称为源点，最后一个顶点称为终点。6.6.1 边长非负时的单源点到所有终点的最短路径 问题：给定一个有向图G = (V, E)和一个源点v，以及图中各条边的长度length(i, j)，且length(i, j)0，求从v到G中其余各顶点的最短路径。JYP106 观察图6.22(a)的有向图：JYP107 以顶点0为源点，从0到1的最短路径是0, 5, 6, 1，其长度为19。虽然这一路径由三条边构成，但它还是比只含一条边的0, 1路径短。 从0到3不存在路径。 图6.22(b)给出了从0到1，2，4，5和6的最短路径。 这些路径按长度不减少顺序列出

46、。JYP108 S 最短路径已找到的终点（包括源点v）的集合。 对于 w S，定义distw为从v出发，只经过S中的顶点，到达w的最短路径的长度。 当按长度不减少顺序生成最短路径时，可以发现： （1）若下一条最短路径是到顶点u的，则该路径始于v，终于u，并且中间只经过S中的顶点。 为此必须证明始于顶点v的最短路径中的所有中间顶点都在S中。JYP109 假设该路径中存在一个顶点w且w S，则从v到u的路径由从v到w和从w到u两段路径构成，如下图所示：JYP110 这一条经过w的路径长度一定比不经过w的短，否则就没必要经过w。 由于每条边的长度都是非负的，所以从v到w的路径长度 distu。 而此

47、时从v到w的最短路径尚未确定，这与按长度不减少顺序生成最短路径的假设矛盾。 因此，不存在不在S中的中间顶点。JYP111 （2）根据dist定义和（1），下一条最短路径的终点u必须满足： distu = 如果多个不在S中的顶点的dist都具有同样的最小值，则可任选其中之一。 （3）顶点u按（2）的条件被选中后即成为S的成员，相应的从v到u的最短路径也被确定。JYP112 这时，对于任何不属于S且邻接自u的顶点w，distw可能减少。若确实减少，则一定是由于存在一条从v到u，再从u到w的更短路径，如下图所示：JYP113 从v到u的路径一定是从v到u的最短路径，而从u到w的路径就是边。 因此从v

48、到w的路径长度为distu + length(u, w)。 假设从u到w的路径含有任何属于S的中间顶点x，如下图所示：JYP114则该路径不可能使distw更短。因为： （a）路径vux的长度 distx （b）路径vuxw的长度 路径vxw的长度 distwJYP115 由上观察可得最短路径算法。 设G的n个顶点编号为0, 1, , n 1。 集合S用Boolean数组s表示。 到终点w（0w n 1）的最短路径所经过的最后一个顶点用pathw记载。 设图G本身由长度邻接矩阵表示，则lengthij是边的长度。若E且ij，则将lengthij设置为LARGEINT。lengthii可设置为任

49、何非负数。JYP116 类Graph的定义如下：class Graph private: int lengthnmaxnmax; int distnmax; int pathnmax; Boolean snmax;public: void ShortestPath(const int, const int); int choose(const int); JYP117 函数ShortestPath给出了算法的实现：1 void Graph:ShortestPath(const int n, const int v) 2 for (int i = 0; i n; i+) 3 si = FALSE

50、; disti = lengthvi; 4 if ( i != v & disti LARGEINT) pathi = v; else pathi = 1;5 6 sv = TRUE; distv = 0;7 for (i = 0; i n-2; i+) / 确定从v开始的n 1条路径8 int u = choose(n); / 选择u，使得对于所有sx = / FALSE，distu = 最小的distx9 su = TRUE;JYP11810 for ( int w = 0; w n; w+)11 if (!sw)12 if (distu + lengthuw distw) distw =

51、 distu + lengthuw; pathw = u; 13 / for (i = 0;) 结束14 JYP119 分析：第2行的for循环需要O(n)时间。第7行的for循环执行n 2次，每次需要O(n)时间用于第8行的选择和第10到12行的更新dist值。因此，该循环的总时间是O(n2)。 整个算法的时间是O(n2)。 即使采用邻接表，第10到12行的总时间可减少到O(e)（因为只有邻接自u的顶点的dist可能变化），第8行的总时间仍然是O(n2)。 JYP120 例6.4 对于图6.22(a)，ShortestPath的运行情况：JYP121 根据path，很容易推算出从源点0到终点

52、u的最短路径。 以终点4为例，path4 = 6，path6 = 5，path5 = 0，反过来排列，可得路径0, 5, 6, 4，这就是从源点0到终点4的最短路径，其长度为dist4 = 28。JYP122 应用斐波纳契堆和邻接表，可使算法的时间复杂性减少为O(n log n + e)。 每次迭代，都需要确定顶点u，使得u ，且distu = 。这对应于上的删除最小元素操作。 由于u加入S， 中与u邻接的顶点的dist值可能减少。这对应于上的关键字减少操作。JYP123 初始时， 含n 1个顶点。如果以dist为关键字，将 组织为斐波纳契堆，则需要n 1次插入操作。 接着需要执行n 2次删除

53、最小元素操作和最多e次关键字减少操作。 所有这些操作的代价是各操作的分摊代价之和，即 O(n log n + e)。 因此，算法的时间复杂性是O(n log n + e)。 当e远小于n2时，这种实现显然更好。 JYP124 如果图中存在边长为负的情况，则ShortestPath不一定给出正确结果。 例如，在下图中设v = 0是源点，则算法先计算dist2 = 5，并确定从0到2的最短路径是0, 2，再计算dist1 = 7。而实际上从0到2的最短路径是0, 1, 2，其长度为2。JYP1256.6.2 所有顶点对之间的最短路径 问题：找到所有顶点对u和v（u v）之间的最短路径。 对于边长非

54、负的图，可以每一个顶点作为源点，将问题转化为n个单源点到所有终点的最短路径问题，求解所需总时间为O(n3)。 如果采用斐波纳契堆，则所需总时间为O(n2 log n + n e)。 对于边长可能为负，但不存在长度为负的环路的图，可以利用动态规划的方法得到一个概念更加简单且时间复杂性也是O(n3)的算法。 JYP126 定义Akij为经过的中间顶点标号不大于k的从i到j的最短路径的长度，则An-1ij是图G中从i到j的最短路径的长度。 A-1ij = lengthij 。 求所有顶点对之间的最短距离算法的基本思想： 从A-1开始，连续生成矩阵A0，A1，An-1。JYP127 如果已生成Ak-1

55、，那么对于任意顶点对i和j，可以根据以下两种情况之一生成Ak： （1）经过的中间顶点标号不大于k的从i到j的最短路径不经过顶点k，因此其长度是Ak-1ij。 （2）该最短路径经过顶点k。该路径由从i到k的子路径和从k到j的子路径构成。由于不存在长度为负的环路，所以经过顶点k不可能使这些子路径更短。因此，这些子路径一定是经过的中间顶点标号不大于k 1的从i到k和从k到j的最短路径，它们的长度分别是Ak-1ik 和Ak-1kj。JYP128 因此，对于k0，有 ： Akij = min Ak-1ij，Ak-1ik + Ak-1kj 设从i到j的最短路径中j前面的顶点为pathij，则pathij前

56、面的顶点为pathipathij，整个路径为：i = pathmij，pathm-1ij，pathij，j（假设路径中有m + 1个顶点）。 若从i到j的最短路径经过顶点k，则该路径中j前面的顶点一定是从k到j的子路径中j前面的顶点，因此pathij = pathkj。当从i到j的最短路径只是一条边时，pathij = i。JYP129 算法AllLengths计算An-1并生成pathij：1 void Graph:AllLengths(const int n) / 在类Graph定义中将 / path修改为pathnmax nmax，并增加数据成员a 2 for (int i = 0; i

57、 n; i+)3 for (int j = 0; j n; j+) 4 aij = lengthij; / 初始化a5 if ( i != j & aij LARGEINT) pathij = i; else pathij = 1;6 7 for ( int k = 0; k n; k+) / 经过的中间顶点标号不大于k8 for ( i = 0; i n; i+) / 所有顶点对9 for ( j = 0; j n; j+)JYP13010 if (aik + akj 0的从i到j的路径则A+ij =1，否则A+ij =0。 定义：图G的自反传递闭包矩阵A*是一个矩阵，且满足：如果存在一条长

58、度0的从i到j的路径则A*ij =1，否则A*ij =0。 JYP135 对于下面的有向图：其A+和A*如下一页所示。显然，A+和A*的差别仅在对角线上，A*ii =1总是成立的。JYP136JYP137 简化函数AllLengths，将其中的length和a改为Boolean数组， lengthij = TRUE当且仅当 是G的边，可得到算法TransitiveClose：1 void Graph:TransitiveClose(const int n) 2 for (int i = 0; i n; i+)3 for (int j = 0; j n; j+)4 aij = lengthij;

59、 / 初始化a5 for ( int k = 0; k n; k+) / 经过的中间顶点标号不大于k6 for ( i = 0; i n; i+) / 所有顶点对7 for ( j = 0; j n; j+)8 aij = aij | aik & akj;9 JYP138 算法结束时，最终的a就是A+。将A+中对角线元素全部设置为1则可得到A*。 无向图的传递闭包更容易计算： 处于同一个连通分量中的任何两个顶点之间存在一条路径 可以先求出图的连通分量，再确定A+，总的时间为O(n2)。对于同一个连通分量中的两个不同顶点i和j，A+ij = 1。A+ii = 1当且仅当i所在的分量包含至少两个顶

60、点。 JYP1396.7 活动网络 6.7.1 AOV网络 一个工程可以分解为若干个子工程，这些子工程称为活动。 活动之间可能存在先后关系。用有向图可以更清楚地表示活动之间的关系。 定义：一个用顶点表示活动，边表示活动之间的先后关系的有向图称为AOV（activity-on-vertex）网络。JYP140 定义：在一个AOV网络G中，如果存在一条从顶点i到顶点j的有向路径，则顶点i是顶点j的前驱，相应地，顶点j是顶点i的后继。如果是G的一条边，则顶点i是顶点j的直接前驱，相应地，顶点j是顶点i的直接后继。 定义：拓扑顺序是图中所有顶点组成的一种线性序列，使得对于图中任意两个顶点i和 j，如果