《数据结构与算法分析》课件第6章

第6章图6.1图的基本概念6.2图的存储方法6.3图的遍历6.4生成树和最小生成树6.5最短路径6.6拓扑排序6.7关键路径

6.1图的基本概念

图(G)是一种非线性数据结构，它由两个集合V(G)和E(G)组成，形式上记为G=(V，E)。其中，V(G)是顶点(Vertex)的非空有限集合；E(G)是V(G)中任意两个顶点之间的关系集合，又称为边(Edge)的有限集合。当G中的每条边有方向时，则称G为有向图。有向边通常用由两个顶点组成的有序对来表示，记为〈起始顶点，终止顶点〉。有向边又称为弧，因此，弧的起始顶点就称为弧尾；终止顶点称为弧头。例如，图6-1(a)给出了一个有向图的示例，该图的顶点集和边集分别为

V(G1)={A,B,C}

E(G1)={<A,B>,<B,A>,<B,C>,<A,C>}图6-1有向图和无向图示例若G中的每条边是无方向的，则称G为无向图。这时两个顶点之间最多只存在一条边。无向边用两个顶点组成的无序对表示，记为(顶点1，顶点2)。图6-1(b)给出了一个无向图的示例，该图的顶点集和边集分别为

V(G2)={A,B,C}

E(G2)={(A,B),(B,C),(C,A)} 

={(B,A),(C,B),(A,C)}

在下面讨论的图中，我们不考虑顶点到其自身的边，也不允许一条边在图中重复出现，如图6-2所示。图6-2本章中不考虑的图边示例在这两条假设条件的约束下，图的边和顶点之间存在以下的关系：

(1)一个无向图，它的顶点数n和边数e满足0≤e≤n(n-1)

/2的关系。如果e=n(n-1)/2，则该无向图称为完全无向图。

(2)一个有向图，它的顶点数n和边数e满足0≤e≤n(n-1)的关系。如果e=n(n-1)，则称该有向图为完全有向图。

(3)若图中的顶点为n，边数为e，如果e<nlbn，则该图为稀疏图；否则为稠密图。如果有两个同类型的图G1=(V1,E1)和G2=(V2,E2)，存在关系V1

V2，E1

E2，则称G1是G2的子图。图6-3给出了G1和G2的子图示例。图6-3子图示例如果图G中有n个顶点，e条边，且每个顶点的度为D(vi)

(1≤i≤n)，则存在以下关系：

(6-1)

在一个图中，如果图的边或弧具有一个与它相关的数时，这个数就称为该边或弧的权。权常用来表示一个顶点到另一个顶点的距离或耗费。如果图中的每条边都具有权时，这个带权图被称为网络，简称为网。图6-4给出了一个网络示例。图6-4网络示例例如，在图6-1(b)中，(A，B，C)是一条路径。而在图6-1(a)中，(A，C，B)就不是一条路径。对于无权图，沿路径所经过的边数称为该路径的长度。而对于有权图，则取沿路径各边的权之和作为此路径的长度。在图6-4中，顶点1到顶点4的路径长度为8。

若路径中的顶点不重复出现，则这条路径被称为简单路径。起点和终点相同并且路径长度不小于2的简单路径，被称为简单回路或者简单环。例如，图6-1(b)所示无向图中，顶点序列(A，B，C)是一条简单路径，而(A，B，C，A)则是一个简单环。在一个有向图中，若存在一个顶点v，从该顶点有路径可到达图中其他的所有顶点，则称这个有向图为有根图；v称为该图的根。例如，图6-1(a)就是一个有根图，该图的根是A和B。

在无向图G中，若顶点vi和vj(i≠j)有路径相通，则称vi和vj是连通的。如果v(G)中的任意两个顶点都连通，则称G是连通图；否则为非连通图。例如图6-1(b)就是一个连通图。

无向图G中的极大连通子图称为G的连通分量。对任何连通图而言，连通分量就是其自身；非连通图可有多个连通分量。

图6-5给出了一个无向图和它的两个连通分量。图6-5无向图及其连通分量

6.2图的存储方法

6.2.1邻接矩阵

邻接矩阵是表示图中顶点之间相邻关系的矩阵。对一个有n个顶点的图G，其邻接矩阵是一个n×n阶的方阵，矩阵中的每一行和每一列都对应一个顶点。矩阵中的元素A[i,j]可按以下规则取值：

(6-2)图6-6(a)和(b)所示有向图G1和无向图G2的邻接矩阵分别为A1和A2：图6-6有向图G1和无向图G2示例对于网络，邻接矩阵元素A[i,j]可按以下规则取值：

(6-3)图6-4所示网络的邻接矩阵为6.2.2邻接表

邻接表存储方法是一种顺序存储与链式存储相结合的存储方法。在这种方法中，因为只考虑非零元素，所以当图中的顶点很多而边又很少时，可以节省存储空间。图6-7邻接表和逆邻接表示例

6.3图的遍历

6.3.1深度优先搜索遍历

图的深度优先搜索遍历(DFS)类似于树的先序遍历，是树先序遍历的推广。图6-8深度优先搜索遍历过程当图6-8采用图6-9所示的邻接表表示时，按以上算法进行深度优先搜索遍历得到的序列为A，B，C，E，D。

因为搜索n个顶点的所有邻接点需要对各边表结点扫描一遍，而边表结点的数目为2e，所以算法的时间复杂度为O(2e+n)，空间复杂度为O(n)。

在使用邻接表作为存储结构时，由于图的邻接表表示不是唯一的，因此DFSL算法得到的DFS序列也不是唯一的，它取决于邻接表中边表结点的链接次序。图6-9邻接表的一种表示6.3.2广度优先搜索遍历

图的广度优先搜索遍历(BFS)类似于树的按层次遍历。这种方法的遍历过程是：在假设初始状态是图中所有顶点都未被访问的条件下，从图中某一个顶点vi出发，访问vi；然后依次访问vi的邻接点vj；在所有的vj都被访问之后，再访问vj的邻接点vk；……直到图中所有和初始出发点vi有路径相通的顶点都被访问为止。若该图是非连通的，则选择一个未曾被访问的顶点作为起始点，重复以上过程，直到图中所有顶点都被访问为止。

6.4生成树和最小生成树

在图论中，树是指一个无回路存在的连通图，而一个连通图G的生成树指的是：一个包含了G的所有顶点的树。对于一个有n个顶点的连通图G，其生成树包含了n-1条边，从而生成树是G的一个极小连通的子图。所谓极小是指该子图具有连通所需的最小边数，若去掉其中的一条边，该子图就变成了非连通图；若任意增加一条边，该子图就有回路产生。图6-10生成树的示例图6-11含有(u,v)的回路

1. Prim算法

用Prim算法构造最小生成树的过程是：设G(V,E)是有n个顶点的连通网络，T=(U，TE)是要构造的生成树，初始时U={

}，TE={

}。首先，从V中取出一个顶点u0放入生成树的顶点集U中作为第一个顶点，此时T=({u0}，{

})；然后，从u

U，v

V-U的边(u，v)中找一条代价最小的边(u*,v*)放入TE中，并将v*放入U中,此时T=({u0,v*}，{(u0，v*)})；继续从u

U，v

V-U的边(u,v)中找一条代价最小的边(u*,v*)放入TE中，并将v*放入U中，直到U=V为止。这时T的TE中必有n-1条边，构成所要构造的最小生成树。图6-12Prim算法构造最小生成树的过程在以上算法中，构造第一个顶点所需的时间复杂度是O(n)，求k条边的时间复杂度大约为

(6-4)

其中，O(1)表示某个正常数C。所以式(6-4)的时间复杂度是O(n2)。下面结合图6-13所示的例子再来观察以上算法的工作过程。设选定的第一个顶点为2，其工作过程如下：

(1)将顶点值2写入T[i].fromvex，并将其余顶点值写入相应的T[i].endvex中；然后从dist矩阵中取出第2行写入相应的T[i].length中，得到图6-14(a)。

(2)在图6-14(a)中找出最小权值的边(2，1)，将其交换到下标值为0的单元中；然后从dist阵中取出第1行的权值与相应的T[i].length的值相比较。若取出的权值小于相应T[i].length的值，则进行替换；否则保持不变。图6-13一个网络及其邻接矩阵图6-14T数组变化情况及最小生成树

2. Kruskal算法

Kruskal算法是从另外一条途径来求网络的最小生成树。

用Kruskal算法构造最小生成树的过程是：设G=(V，E)是一个有n个顶点的连通图，令最小生成树的初值状态为只有n个顶点而无任何边的非连通图T=(V，{

})，此时图中每个顶点自成一个连通分量。按照权值递增的顺序依次选择E中的边，若该边依附于T中两个不同的连通分量，则将此边加入TE中；否则舍去此边而选择下一条代价最小的边，直到T中所有顶点都在同一个连通分量上为止。这时的T，便是G的一棵最小生成树。

对于图6-13所示的网络，按Kruskal算法构造最小生成树的过程如图6-15所示。图6-15Kruskal算法构造最小生成树的过程

6.5最短路径

6.5.1从某个源点到其余各顶点的最短路径

对于给定的有向网络G = (V,E)及源点v，计算从v到G的其余各顶点的最短路径。

例如，已知有向网络G如图6-16所示，假定以顶点F为源点，则源点F到其余各顶点A、B、C、D、E的最短路径如表6-1所示。图6-16有向网络G对图6-16所示的有向网络按以上算法思想处理，所求得的从源点F到其余顶点的最短路径的过程如图6-17所示。图6-17Dijkstra算法求最短路径示例6.5.2每一对顶点之间的最短路径

在一个有n个顶点的有向网络G=(V，E)中，求每一对顶点之间的最短路径。可以依次把有向网络G的每个顶点作为源点，重复执行Dijkstra算法n次，从而得到每对顶点之间的最短路径。这种方法的时间复杂度为O(n3)。弗洛伊德(Floyd)于1962年提出了解决这个问题的另外一种算法，它在形式上比较简单，易于理解，而时间复杂度同样为O(n3)。图6-18Floyd算法选代过程中矩阵A和path的变化情况

6.6拓扑排序

无论是一项工程的进行，还是一个产品的生产或一个专业课程的学习，都是由许多按一定次序进行的活动来构成的。这些活动既可以是一个工程中的子工程，一个产品生产中的部件生产，也可以是课程学习中的一门课程。对于这些按一定顺序进行的活动，可以用有向图的顶点表示活动，顶点之间的有向边表示活动间的先后关系，这种有向图称为顶点表示活动网络(ActivityOnVertexnetwork)，简称AOV网。AOV网中的顶点也可带有权值，用于表示一项活动完成所需要的时间。

AOV网中的有向边表示了活动之间的制约关系。例如，计算机软件专业的学生必须学完一系列的课程才能毕业，其中一些课程是基础课，学习基础课程无须先学习其他课程；而另一些课程的学习，则必须在完成其他基础先修课的学习之后才能进行学习。这些课程和课程之间的关系如表6-3所示。它们也可以用图6-19所示的AOV网表示，其中有向边

<Ci，Cj>表示了课程Ci是课程Cj的先修课程。图6-19表示课程先后关系的AOV网图6-20AOV网拓扑排序过程图6-21AOV网G1及其邻接表图6-22链栈的初始逻辑状态图图6-23排序过程中入度域变化示例

6.7关键路径

因为一项工程只有一个开始点和一个结束点，所以AOE网络中只有一个入度为0的顶点(称做源点)表示开始和一个出度为0的顶点(称做汇点)表示结束。同时，AOE网络应该是不存在回路并相对源点连通的网络。图6-24给出了一个AOE网络的例子，它包括了7个事件和10个活动。其中，顶点v1表示整个工程开始；顶点v7表示整个工程结束；边<v1，v2>，<v1，v3>，…，<v6，v7>分别表示一个活动，并分别用a1，a2，