1、第第6 6章章 图图本章概述本章概述 图是一种重要的非线性结构，并且是一种比线性图是一种重要的非线性结构，并且是一种比线性表和树更为复杂的数据结构。图的特点是每个顶点都表和树更为复杂的数据结构。图的特点是每个顶点都可以与其他顶点相连；在图结构中，每个顶点的地位可以与其他顶点相连；在图结构中，每个顶点的地位是一样的，图中任意两个顶点之间都可以相关。是一样的，图中任意两个顶点之间都可以相关。图的应用极为广泛，特别是图论的迅速发展，使图的应用极为广泛，特别是图论的迅速发展，使得图的应用已渗入到运筹学、逻辑学、计算机科学及得图的应用已渗入到运筹学、逻辑学、计算机科学及语言学等其他分支学科中。语言学等其
2、他分支学科中。6.1 6.1 图的定义和术语图的定义和术语 图是由一个顶点集图是由一个顶点集V V和一个弧集和一个弧集R R构成的数据结构。构成的数据结构。图的抽象数据类型数学表述为：图的抽象数据类型数学表述为：Graph=Graph=（V V，R R），），且且VRVR t|th|t，hVhV且且P(tP(t，h)h)其中，其中，VRVR表示两个顶点之间的关系，表示两个顶点之间的关系，th表示从表示从t t到到h h的一条弧，的一条弧，P(tP(t，h)h)定义了弧定义了弧 th的意义。的意义。图中的数据元素通常称为顶点（图中的数据元素通常称为顶点（vertexvertex）。）。V V是顶
3、点的有穷非空集合。是顶点的有穷非空集合。VRVR表示两个顶点之间的关系的集合。表示两个顶点之间的关系的集合。若若tVRhVR，则，则th表示从表示从t t到到h h的一条弧，且称的一条弧，且称t t为为弧尾弧尾（tailtail），），h h为为弧头弧头(head)(head)，此时的图称为，此时的图称为有向有向图图。若若tVRhVR必有必有hVR,tVR,即即VRVR是对称的，则是对称的，则用无序对（用无序对（t t，h h）代替这两个有序对，表示）代替这两个有序对，表示t t和和h h这两个这两个顶点之间的一条边，此时的图称为顶点之间的一条边，此时的图称为无向图无向图。下图下图(a)(a)
4、所示为无向图，所示为无向图，(b)(b)所示为有向图。所示为有向图。【例【例6-16-1】使用集合的表示方法，上面的两个图可以用如】使用集合的表示方法，上面的两个图可以用如下的方法表示：下的方法表示：Ga=(Va,EaGa=(Va,Ea)；Gb=(Vb,EbGb=(Vb,Eb)VaVa=1,2,3,4=1,2,3,4；Ea=(1,2),(1,3),(1,4),(2,3)Ea=(1,2),(1,3),(1,4),(2,3)VbVb=1,2,3,4,5=1,2,3,4,5；EbEb=,=,注意：注意：无向图的顶点无序偶对使用一对圆括号表示，无向图的顶点无序偶对使用一对圆括号表示，有向图的顶点有序偶
5、对使用一对尖括号表示。有向图的顶点有序偶对使用一对尖括号表示。每条边都是有向边的图，称为每条边都是有向边的图，称为有向图有向图；每条边都；每条边都是无向边的图，称为是无向边的图，称为无向图无向图。既有有向边又有无向边。既有有向边又有无向边的图，称为的图，称为混合图混合图。用用n n表示图中顶点的数目，用表示图中顶点的数目，用e e表示图中边的数目。表示图中边的数目。不考虑顶点到自身的边，对于无向图，不考虑顶点到自身的边，对于无向图，e e的取值范的取值范围是围是0n(n-1)/20n(n-1)/2，具有，具有n(n-1)/2n(n-1)/2条边的无向图称为条边的无向图称为无无向完全图向完全图。
6、对于有向图，对于有向图，e e的取值范围是的取值范围是0n(n-1)0n(n-1)，具有，具有n(n-1)n(n-1)条边的有向图称为条边的有向图称为有向完全图有向完全图。在工程应用中，边数。在工程应用中，边数e e小于小于nlognlog n n的图称为的图称为稀疏图稀疏图，反之称为，反之称为稠密图稠密图。假设有两个图假设有两个图G=(VG=(V，E)E)和和G=(V,E)G=(V,E)，如果，如果 V VV V且且E EE E，则称，则称GG为为G G的子图。的子图。下图所示是子图的一些例子。下图所示是子图的一些例子。子图是在原图上删去若干条边或若干个点剩下的图。子图是在原图上删去若干条边
7、或若干个点剩下的图。删边指删去图中的某一条边但仍保留边的顶点。删边指删去图中的某一条边但仍保留边的顶点。删点指删去图中某一点以及与这点相连的所有边。删点指删去图中某一点以及与这点相连的所有边。图中删去一点所得的子图称为图中删去一点所得的子图称为主子图主子图。设有一个设有一个n n阶无向图，在其中添加一些边后，可使其成阶无向图，在其中添加一些边后，可使其成为为n n阶完全图阶完全图。由这些新添加的边和其顶点构成的图称为原图的由这些新添加的边和其顶点构成的图称为原图的补补图图。对于无向图对于无向图G=(VG=(V，E)E)，顶点，顶点v v的度是和的度是和v v相连的边的相连的边的数目，记为数目，
8、记为D(vD(v)。对于有向图对于有向图G=(VG=(V，R)R)，以顶点，以顶点t t为弧头的弧的数目称为弧头的弧的数目称为顶点为顶点t t的的入度入度，记为，记为ID(tID(t)；以顶点；以顶点t t为弧尾的弧的数为弧尾的弧的数目称为顶点目称为顶点t t的的出度出度，记为，记为OD(tOD(t)；顶点；顶点t t的度记为的度记为D(t)=ID(t)+OD(tD(t)=ID(t)+OD(t)。特殊情况下，度数为零的顶点称为特殊情况下，度数为零的顶点称为孤立点孤立点，度数为，度数为1 1的顶点称为的顶点称为悬挂点悬挂点。一般地，如果顶点一般地，如果顶点vivi的度记为的度记为D D（vivi
9、），那么一个有），那么一个有n n个顶点，个顶点，e e条边的图，满足如下关系：条边的图，满足如下关系：定理定理1 1：设图：设图G G是具有是具有v v个顶点，个顶点，e e条边的无向图，则有条边的无向图，则有D(vD(v)=2e)=2e。定理定理2 2：设图：设图G G是具有是具有v v个顶点，个顶点，e e条边的有向图，则有条边的有向图，则有ID(v)=OD(vID(v)=OD(v)=e)=e。11()2niieDv 路径长度路径长度是路径上边的数目或弧的数目。是路径上边的数目或弧的数目。一条边的两端重合，称为一条边的两端重合，称为自回路自回路。第一个顶点和最后一个顶点相同的路径称为回第
10、一个顶点和最后一个顶点相同的路径称为回路路或或环环。在顶点序列中，顶点不重复出现的路径称为在顶点序列中，顶点不重复出现的路径称为简单路径简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为出现的回路，称为简单回路简单回路或或简单环简单环。在无向图在无向图G=(VG=(V，E)E)中，如果存在一条从顶点中，如果存在一条从顶点v v到到顶点顶点w w的路径，则称的路径，则称从从v v到到w w可达可达。如果图中任意两点是可达的，则称如果图中任意两点是可达的，则称v v和和w w是是连通连通的，的，否则不连通。否则不连通。对于图中
11、任意两个顶点对于图中任意两个顶点v v、wVwV，v v和和w w都是连通都是连通的，则称的，则称G G是是连通图连通图。有向图有向图G=VG=R中，如果对于每一对中，如果对于每一对t t、hVhV，从从t t到到h h和从和从h h到到t t都存在路径，则称都存在路径，则称G G是是强连通图强连通图。有向图中的极大强连通子图称为有向图的有向图中的极大强连通子图称为有向图的强连通分量强连通分量。例如，下图不是强连通图，但它有两个强连通分量。例如，下图不是强连通图，但它有两个强连通分量。在图的顶点或边上表明某种信息的数称为权，含有在图的顶点或边上表明某种信息的数称为权，含有权的图，称为权的图，称
12、为赋权图赋权图。例如，下图就是一个赋权图。例如，下图就是一个赋权图。最短路径问题的算法：最短路径问题的算法：先求出到某一顶点的最短路径，然后利用这个结先求出到某一顶点的最短路径，然后利用这个结果再去确定到另一顶点的最短路径，如此继续下去，果再去确定到另一顶点的最短路径，如此继续下去，直到找到最短路径为止。直到找到最短路径为止。如果图中存在一条通过图中各边一次且仅一次的如果图中存在一条通过图中各边一次且仅一次的回路，则称此回路为回路，则称此回路为欧拉回路欧拉回路，具有欧拉回路的图称，具有欧拉回路的图称为为欧拉图欧拉图。如果图中存在一条通过图中各边一次且仅一次的如果图中存在一条通过图中各边一次且仅
13、一次的通路，则称此通路为通路，则称此通路为欧拉通路欧拉通路，具有欧拉通路的图称，具有欧拉通路的图称为为半欧拉图半欧拉图。定理定理3 3：一个无向连通图是欧拉图的充要条件是图：一个无向连通图是欧拉图的充要条件是图中各点的度数为偶数。中各点的度数为偶数。定理定理4 4：一个无向连通图是半欧拉图的充要条件是：一个无向连通图是半欧拉图的充要条件是图中至多有两个奇数度点。图中至多有两个奇数度点。定理定理5 5：设图：设图G G是有向连通图，图是有向连通图，图G G是欧拉图的充是欧拉图的充要条件是图中每个顶点的入度和出度相等。要条件是图中每个顶点的入度和出度相等。定理定理6 6：设图：设图G G是有向连通
14、图，图是有向连通图，图G G是半欧拉图的是半欧拉图的充要条件是至多有两个顶点的出度和入度不相等，其充要条件是至多有两个顶点的出度和入度不相等，其中一个顶点的入度比它的出度大中一个顶点的入度比它的出度大1 1，另一个顶点的入度，另一个顶点的入度比它的出度小比它的出度小1 1，而其他顶点的入度和出度相等。，而其他顶点的入度和出度相等。一个连通图的生成树是一个极小的连通子图，它一个连通图的生成树是一个极小的连通子图，它含有图中全部顶点，但只有构成一棵树的含有图中全部顶点，但只有构成一棵树的n-1n-1条边。条边。一棵有一棵有n n个顶点的生成树有且仅有个顶点的生成树有且仅有n-1n-1条边。条边。如
15、果一个图有如果一个图有n n个顶点和小于个顶点和小于n-1n-1条边，则图一定条边，则图一定是非连通图，如果它多于是非连通图，如果它多于n-1n-1条边，则一定有环。条边，则一定有环。6.26.2 图的存储结构图的存储结构 设设G=G=（V V，E E）是具有）是具有n n个顶点的图，则个顶点的图，则G G的邻接矩阵的邻接矩阵定义为：定义为：【例【例6-26-2】将下图】将下图(a)(a)所示的无向图和图所示的无向图和图(b)(b)所示的有所示的有向图用邻接矩阵表示。向图用邻接矩阵表示。1(,),0(,),v wv wEAv wv wv wE若或若或6.2.1 6.2.1 邻接矩阵邻接矩阵 解
16、：以上无向图和有向图分别用邻接矩阵解：以上无向图和有向图分别用邻接矩阵M1M1和和M2M2表示如下：表示如下：设设G=G=（V V，E E）是具有）是具有n n个顶点的赋权图，则个顶点的赋权图，则G G的邻接矩的邻接矩阵定义为：阵定义为：10 1 1 11 0 1 11 1 0 01 1 0 0M20 1 0 0 01 0 0 0 10 1 0 1 01 0 0 0 00 0 0 1 0M,(,),0(,),v wv wv wv wEpA v wv wv wE若或 其中:表示边上的权值。p或若或【例【例6-36-3】将下图所示的赋权图用邻接矩阵表示。】将下图所示的赋权图用邻接矩阵表示。解：赋权
17、图可以用邻接矩阵解：赋权图可以用邻接矩阵M M3 3或或M M4 4表示如下：表示如下：30 5 0 7 0 00 0 4 0 0 08 0 0 0 0 90 0 5 0 0 60 0 0 5 0 03 0 0 0 1 0M45748956531M 图的邻接矩阵存储结构的描述形式如下：图的邻接矩阵存储结构的描述形式如下：#define MAX_VERTEX_NUMBER 100#define MAX_VERTEX_NUMBER 100 最大顶点数最大顶点数typedef char VertexTypetypedef char VertexType;顶点类型顶点类型typedef inttype
18、def int edge;edge;边上的权值类型边上的权值类型typedef struct MGraphtypedef struct MGraph存储图的结构体存储图的结构体 VertexType vArrayMAX_VERTEX_NUMBERVertexType vArrayMAX_VERTEX_NUMBER;顶点数组顶点数组edge eArrayMAX_VERTEX_NUMBERMAX_VERTEX_NUMBERedge eArrayMAX_VERTEX_NUMBERMAX_VERTEX_NUMBER;邻接矩阵邻接矩阵intint n;n;顶点数顶点数intint e;e;边数边数;算法
19、算法6.16.1是在邻接矩阵存储结构是在邻接矩阵存储结构MGraphMGraph上对图构造上对图构造的实现算法。的实现算法。注意注意：在简单应用中，可直接用二维数组作为邻：在简单应用中，可直接用二维数组作为邻接矩阵，顶点数和边数均可省略。接矩阵，顶点数和边数均可省略。对于无向图，顶点对于无向图，顶点vivi的度是邻接矩阵中第的度是邻接矩阵中第i i行（或行（或第第i i列）的元素之和。列）的元素之和。对于有向图，顶点对于有向图，顶点vivi的度是邻接矩阵中第的度是邻接矩阵中第i i行和第行和第i i列的元素之和，且第列的元素之和，且第i i行的元素之和为顶点行的元素之和为顶点vivi的出度，的
20、出度，第第i i列的元素之和为顶点列的元素之和为顶点vivi的入度。的入度。对于图中的每个顶点对于图中的每个顶点vivi，把所有邻接于，把所有邻接于vivi的顶点的顶点vjvj链成一个带头结点的单链表，这个单链表称为顶点链成一个带头结点的单链表，这个单链表称为顶点vivi的邻的邻接表。接表。邻接表的结构由两部分组成：邻接表的结构由两部分组成：头结点：用于存储顶点信息和指向表结点的指针；头结点：用于存储顶点信息和指向表结点的指针；表结点：用于存储头结点中顶点相邻接的顶点信息和表结点：用于存储头结点中顶点相邻接的顶点信息和指向表结点的指针。指向表结点的指针。6.2.2 6.2.2 邻接表邻接表【例
21、【例6-46-4】给出下图中无向图】给出下图中无向图G G的邻接表表示。的邻接表表示。解：无向图解：无向图G G的邻接表表示如下图所示。的邻接表表示如下图所示。注意注意：在编程时，头结点以数组的形式存储，表：在编程时，头结点以数组的形式存储，表结点以单链表的形式存储。显然，在稀疏图中，用邻结点以单链表的形式存储。显然，在稀疏图中，用邻接表存储比用邻接矩阵存储节省存储空间。接表存储比用邻接矩阵存储节省存储空间。【例【例6-56-5】给出下图中有向图】给出下图中有向图G G的邻接表表示。的邻接表表示。解：有向图解：有向图G G的邻接表表示如下图所示。的邻接表表示如下图所示。为了方便确定顶点的入度，
22、可以建立有向图的逆为了方便确定顶点的入度，可以建立有向图的逆邻接表，下图就是例【邻接表，下图就是例【6-56-5】中有向图的逆邻接表。】中有向图的逆邻接表。在邻接表上容易找到任一顶点的第一个邻接点和在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点之间是否有边下一个邻接点，但要判定任意两个顶点之间是否有边相连，则要搜索单链表，不如邻接矩阵方便。相连，则要搜索单链表，不如邻接矩阵方便。图的邻接表存储结构的表示形式如下：图的邻接表存储结构的表示形式如下：#define MAX_VERTEX_NUMBER 100#define MAX_VERTEX_NUMBER 100 最
23、大顶点数最大顶点数typedef char VertexTypetypedef char VertexType;顶点类型顶点类型typedef struct eNodetypedef struct eNode 表结点表结点int adjVerint adjVer;eNode eNode*pNextpNext;typedef struct vNodetypedef struct vNode 头结点头结点VertexTypeVertexType vertex;vertex;eNode eNode*pFirstpFirst;typedef struct ALGraphtypedef struct A
24、LGraph 邻接表结构体邻接表结构体vNode adjListMAX_VERTEX_NUMBERvNode adjListMAX_VERTEX_NUMBER;头结点数组头结点数组intint n;n;顶点数顶点数intint e;e;边数边数;算法算法6.26.2是在邻接表存储结构是在邻接表存储结构ALGraphALGraph上对图的构上对图的构造的实现算法。造的实现算法。注意注意：通常头结点以顺序结构存储，表结点以链：通常头结点以顺序结构存储，表结点以链式结构存储。式结构存储。6.3 6.3 图的遍历图的遍历 设图设图G G中的所有顶点均未被访问过，在图中的所有顶点均未被访问过，在图G G
25、中任选一个中任选一个顶点顶点v v为初始出发点，则深度优先搜索描述如下：为初始出发点，则深度优先搜索描述如下：首先访问初始出发点首先访问初始出发点v v，并将其标记为已访问过，然后，并将其标记为已访问过，然后依次从依次从v v出发遍历出发遍历v v的每个邻接点的每个邻接点w w。若邻接点。若邻接点w w未曾访问过，未曾访问过，则以则以w w为新的出发点继续进行深度优先搜索，直至图中所有为新的出发点继续进行深度优先搜索，直至图中所有和出发点和出发点v v有路径相通的顶点均已被访问过为止。若此时图有路径相通的顶点均已被访问过为止。若此时图中仍有未访问的顶点，则另选一个未访问的顶点作为新的出中仍有未
26、访问的顶点，则另选一个未访问的顶点作为新的出发点重复上述过程，直至图中所有顶点均已被访问为止。发点重复上述过程，直至图中所有顶点均已被访问为止。6.3.1 6.3.1 深度优先搜索深度优先搜索 以下图以下图(a)(a)为例来说明深度优先搜索的过程。遍历过为例来说明深度优先搜索的过程。遍历过程如图程如图(b)(b)所示。所示。假定假定A A是初始出发点，首先访问是初始出发点，首先访问A A。因因A A有两个邻接点有两个邻接点B B，C C均未被访问，选择均未被访问，选择B B作为新的作为新的出发点。出发点。找找B B的未访问过的邻接点，与的未访问过的邻接点，与B B邻接的有邻接的有A A，D D
27、，E E，A A已被访问过，已被访问过，D D，E E未被访问，选择未被访问，选择D D作为新的出发点。作为新的出发点。重复上述搜索过程依次访问重复上述搜索过程依次访问H H，E E。访问访问E E之后，由于与之后，由于与E E相邻的顶点均被访问，搜索退相邻的顶点均被访问，搜索退回到回到H H。由于由于H H，D D，B B都没有未被访问的邻接点，所以搜索过都没有未被访问的邻接点，所以搜索过程连续地从程连续地从H H退回到退回到D D，再退回到，再退回到B B，最后退回到，最后退回到A A。选择选择A A未被访问过的邻接点未被访问过的邻接点C C，继续往下搜索，依次，继续往下搜索，依次访问访问
28、C C，F F，G G，I I，从而遍历了图中全部顶点。，从而遍历了图中全部顶点。由此，得到顶点的访问序列为：由此，得到顶点的访问序列为：ABDHECFGIABDHECFGI。深度优先遍历类似树的先序遍历，遍历方法的特点深度优先遍历类似树的先序遍历，遍历方法的特点 是尽可能先对纵深方向进行搜索。是尽可能先对纵深方向进行搜索。整个图的深度优先搜索如整个图的深度优先搜索如算法算法6.36.3和和算法算法6.46.4所示。所示。假设图假设图G G中的所有顶点均未被访问过，在图中的所有顶点均未被访问过，在图G G中任中任选一个顶点选一个顶点v v为初始出发点，则广度优先搜索描述如下：为初始出发点，则广
29、度优先搜索描述如下：首先访问初始出发点首先访问初始出发点v v，并将其标记为已访问过，并将其标记为已访问过，然后依次从然后依次从v v出发遍历出发遍历v v的每个邻接点的每个邻接点w1w1，w2w2，wnwn，然后再依次访问与邻接点然后再依次访问与邻接点w1w1，w2w2，wnwn邻接的所有邻接的所有未曾访问过的顶点。以此类推，直至图中所有和出发未曾访问过的顶点。以此类推，直至图中所有和出发点点v v有路径相通的顶点都已访问完为止。若有路径相通的顶点都已访问完为止。若G G是连通图，是连通图，则遍历完成；否则，在图则遍历完成；否则，在图G G中另选一个未访问的顶点作中另选一个未访问的顶点作为新
30、的出发点继续上述搜索过程，直至为新的出发点继续上述搜索过程，直至G G中所有顶点均中所有顶点均已被访问完为止。已被访问完为止。6.3.2 6.3.2 广度优先搜索广度优先搜索 以下图以下图(a)(a)所示的图为例来说明广度优先搜索的过程。所示的图为例来说明广度优先搜索的过程。遍历过程如图遍历过程如图(b)(b)所示。所示。假定假定A A是初始出发点，首先访问是初始出发点，首先访问A A。因因A A有两个邻接点有两个邻接点B B，C C均未被访问，先选择均未被访问，先选择B B作为作为新的出发点。新的出发点。访问访问B B之后，再访问之后，再访问C C。因因B B的邻接点有的邻接点有A A，D
31、D，E E，其中，其中A A已被访问过，而已被访问过，而D D，E E未被访问，先访问未被访问，先访问D D之后，再访问之后，再访问E E。然后访问然后访问C C的未被访问邻接点的未被访问邻接点F F，G G。最后访问最后访问D D的未曾访问过的邻接点的未曾访问过的邻接点H H和和G G的未曾访问的未曾访问过的邻接点过的邻接点I I，从而遍历了图中全部顶点。，从而遍历了图中全部顶点。由此，得到顶点的访问序列为：由此，得到顶点的访问序列为：ABCDEFGHIABCDEFGHI。广度优先搜索类似于树的按层序遍历，采用的广度优先搜索类似于树的按层序遍历，采用的搜索方法的特点是尽可能先对横向进行搜索。
32、搜索方法的特点是尽可能先对横向进行搜索。整个图的广度优先搜索如整个图的广度优先搜索如算法算法6.56.5和和算法算法6.66.6所所示。示。图的连通分量是指无向图中的极大连通子图，图的连通分量是指无向图中的极大连通子图，而极大连通子图就是指无向图所包含的最多顶点数而极大连通子图就是指无向图所包含的最多顶点数的连通子图。的连通子图。对无向图进行遍历时，对于一个连通图，仅需对无向图进行遍历时，对于一个连通图，仅需从图中任一顶点出发，调用从图中任一顶点出发，调用DFSDFS或或BFSBFS一次便可访问一次便可访问完图中所有顶点。完图中所有顶点。6.3.36.3.3 图的连通分量计算图的连通分量计算
33、对于一个非连通图，则需要多次调用对于一个非连通图，则需要多次调用DFSDFS或或BFSBFS，每，每一次都要得到一个连通分量，调用一次都要得到一个连通分量，调用DFSDFS或或BFSBFS的次数恰的次数恰好是连通分量的个数。好是连通分量的个数。用邻接表对如下图用邻接表对如下图(a)(a)所示的无向非连通图进行存所示的无向非连通图进行存储后，调用深度优先搜索算法，需要储后，调用深度优先搜索算法，需要3 3次调用次调用DFSDFS，从，从而能够得到图的连通分量是而能够得到图的连通分量是3 3，其连通子图见图，其连通子图见图(b)(b)。图(a)图(b)6.4 6.4 图的应用图的应用 生成树（生成
34、树（treetree）各边的权值总和称为该树的权，记）各边的权值总和称为该树的权，记作：作：W(T)=W(u,vW(T)=W(u,v)，W(u,vW(u,v)表示边表示边(u,v(u,v)的权。的权。权值最小的生成树称为图的权值最小的生成树称为图的最小生成树最小生成树（minimum minimum cost spanning treecost spanning tree）,简记为简记为MSTMST。6.4.1 6.4.1 最小生成树最小生成树 最小生成树的性质：最小生成树的性质：设设G=(VG=(V，E)E)是一个连通图，是一个连通图，U U是顶点集是顶点集V V的一个真子的一个真子集。若集
35、。若(u,v(u,v)是具有最小权值的一条边是具有最小权值的一条边(uU,vV(uU,vV-U)-U)，则一定存在则一定存在G G的一棵最小生成树包括此边。的一棵最小生成树包括此边。构造最小生成树的算法有多种，主要有两种：构造最小生成树的算法有多种，主要有两种：普里姆（普里姆（PrimPrim）算法）算法 克鲁斯卡尔（克鲁斯卡尔（KruskalKruskal）算法）算法 它们都是利用它们都是利用MSTMST的性质构造最小生成树的。的性质构造最小生成树的。普里姆算法：普里姆算法：假设假设G=(VG=(V，E)E)是赋权连通图，是赋权连通图，T T是是G G上最小生成树边上最小生成树边的集合。算法
36、从的集合。算法从U=u0(u0V),T=U=u0(u0V),T=开始，重复执行下述开始，重复执行下述操作：在所有操作：在所有uUuU，vVvV-U-U的边的边(u(u，v)Ev)E中找一条权值中找一条权值最小的边最小的边(u0(u0，v0)v0)并入集合并入集合T T，同时，同时v0v0并入并入U U，直至，直至U=VU=V为为止。最后得到最小生成树止。最后得到最小生成树MST=(VMST=(V，T)T)，且，且T T中必有中必有n-1n-1条边。条边。【例【例6-66-6】如下图所示为赋权图按普里姆算法构造一】如下图所示为赋权图按普里姆算法构造一棵最小生成树的过程。棵最小生成树的过程。普里姆
37、算法如普里姆算法如算法算法6.76.7所示。所示。对于【例对于【例6-66-6】中的赋权图，利用算法】中的赋权图，利用算法6.76.7将输出将输出最小生成树的最小生成树的5 5条边，它们分别为条边，它们分别为(A,C)(A,C)、(C,F)(C,F)、(F,D)(F,D)、(C,B)(C,B)、(B,E)(B,E)。注意注意：普里姆算法的时间复杂度是：普里姆算法的时间复杂度是O(nO(n2 2)与图中与图中的边数无关，适用于求稠密图的最小生成树。的边数无关，适用于求稠密图的最小生成树。克鲁斯卡尔算法克鲁斯卡尔算法 ：假设假设G=G=（V V，E E）是赋权连通图，令最小生成树的）是赋权连通图，
38、令最小生成树的初始状态初始状态T T只有只有n n个顶点而无任何一条边，即图中每个个顶点而无任何一条边，即图中每个顶点自成一个连通分量。在顶点自成一个连通分量。在E E中选择权值最小的边，中选择权值最小的边，若该边依附的顶点落在若该边依附的顶点落在T T中不同的连通分量上，则将中不同的连通分量上，则将此边加入到此边加入到T T中，否则舍去此边而选择下一条权值最中，否则舍去此边而选择下一条权值最小的边。重复上述操作，直至小的边。重复上述操作，直至T T中所有顶点都在同一中所有顶点都在同一连通分量上为止。连通分量上为止。【例【例6-76-7】如下图所示为赋权连通图按克鲁斯卡尔算】如下图所示为赋权连
39、通图按克鲁斯卡尔算法构造一棵最小生成树的过程。法构造一棵最小生成树的过程。注意注意：克鲁斯卡尔算法的时间复杂度是：克鲁斯卡尔算法的时间复杂度是O(elogeO(eloge)，与图中的边数有关，适用于求稀疏图的，与图中的边数有关，适用于求稀疏图的最小生成树。最小生成树。图的最短路径问题分为两类：图的最短路径问题分为两类：求从某个源点到其余各顶点的最短路径；求从某个源点到其余各顶点的最短路径；求每一对顶点之间的最短路径。求每一对顶点之间的最短路径。单源点的最短路径问题：给定带权有向图单源点的最短路径问题：给定带权有向图G G和源点和源点v v，求，求从从v v到到G G中其余顶点的最短路径。中其余
40、顶点的最短路径。算法的基本思想：按最短路径长度递增的次序求得各条算法的基本思想：按最短路径长度递增的次序求得各条路径。路径。6.4.2 6.4.2 最短路径最短路径 其中，从源点到顶点其中，从源点到顶点vivi的最短路径是所有最短路的最短路径是所有最短路径中长度最短者。径中长度最短者。长度最短的最短路径的特点：在这条路径上，必长度最短的最短路径的特点：在这条路径上，必定只含一条弧，并且这条弧的权值最小。定只含一条弧，并且这条弧的权值最小。下一条路径长度次短的最短路径的特点：它只可下一条路径长度次短的最短路径的特点：它只可能有两种情况，或者是直接从源点到该点能有两种情况，或者是直接从源点到该点(
41、只含一条只含一条弧弧)；或者是从源点经过顶点；或者是从源点经过顶点v1v1，再到达该顶点，再到达该顶点(由两由两条弧组成条弧组成)。再下一条路径长度次短的最短路径的特点：它可能再下一条路径长度次短的最短路径的特点：它可能有两种情况，或者是直接从源点到该点有两种情况，或者是直接从源点到该点(只含一条弧只含一条弧)；或者是从源点经过顶点或者是从源点经过顶点v1v1，再到达该顶点，再到达该顶点(由两条弧组由两条弧组成成)。其余最短路径的特点：它或者是直接从源点到该点其余最短路径的特点：它或者是直接从源点到该点(只含一条弧只含一条弧)；或者是从源点经过已求得最短路径的顶或者是从源点经过已求得最短路径的
42、顶点，再到达该顶点。点，再到达该顶点。使用最短路径的迪杰斯特拉算法求这些路径。使用最短路径的迪杰斯特拉算法求这些路径。算法描述如下：算法描述如下：设置辅助数组设置辅助数组D D，其中每个分量，其中每个分量DkDk 表示当前所求表示当前所求得的从源点到其余各顶点得的从源点到其余各顶点 k k 的最短路径。的最短路径。DkDk=arcsv0k=arcsv0k，v0v0和和k k之间存在弧；之间存在弧；DkDk=，v0v0和和k k之间不存在弧，其中的最小值即为最短路径的长度。之间不存在弧，其中的最小值即为最短路径的长度。一般情况下，一般情况下，DkDk=或者或者+。（1 1）在所有从源点出发的弧中
43、选取一条权值最小的弧，）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。即为第一条最短路径。（2 2）修改其他各顶点的）修改其他各顶点的DkDk 值。值。（3 3）重复操作（）重复操作（1 1）、（）、（2 2）步骤共）步骤共n-1n-1次。由此求得从次。由此求得从源点到图上其余各顶点的最短路径是依路径长度递源点到图上其余各顶点的最短路径是依路径长度递增的序列。增的序列。迪杰斯特拉算法如迪杰斯特拉算法如算法算法6.86.8所示。所示。偏序指集合中部分成员之间可比较，全序指集合偏序指集合中部分成员之间可比较，全序指集合中所有成员之间均可比较。中所有成员之间均可比较。下图所示的两个
44、有向图，图中弧下图所示的两个有向图，图中弧vw表示表示vwvw，(a)(a)表示偏序关系，图表示偏序关系，图(b)(b)表示全序关系，图表示全序关系，图(a)(a)中的中的顶点顶点B B与顶点与顶点C C无法比较。无法比较。6.4.3 6.4.3 拓扑排序拓扑排序 “拓扑排序拓扑排序”：对有向图进行如下操作：按照有向图给出的次序对有向图进行如下操作：按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次没有限定次序关系的顶点，则可以人为加上任意的次序关系，由此所得顶点的线性序列称之为拓扑有序
45、序序关系，由此所得顶点的线性序列称之为拓扑有序序列。列。例如，上图例如，上图(a)(a)所示的有向图的拓扑有序序列为：所示的有向图的拓扑有序序列为：A A B C D B C D 或或 A C B DA C B D。对于下图所示的有向图，则不能求得它的拓扑对于下图所示的有向图，则不能求得它的拓扑有序序列。因为图中存在一个回路有序序列。因为图中存在一个回路 B,C,DB,C,D。可用拓扑排序对有向图是否存在回路进行检查。可用拓扑排序对有向图是否存在回路进行检查。解决的方法如下：解决的方法如下：（1 1）从有向图中选取一个没有前驱的顶点，并输出之。）从有向图中选取一个没有前驱的顶点，并输出之。（2
46、 2）从有向图中删去此顶点以及所有以它为尾的弧。）从有向图中删去此顶点以及所有以它为尾的弧。重复上述两步，直至全部顶点均已输出，或者当前图中重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况说明有向图中存不存在无前驱的顶点为止。后一种情况说明有向图中存在环。在环。根据上述方法，下图所示为图拓扑有序序列的产生步骤。根据上述方法，下图所示为图拓扑有序序列的产生步骤。图图(a)(a)原图，图原图，图(b)(b)输出输出A A，图，图(c)(c)输出输出C C，图，图(d)(d)输出输出B B，图，图(e)(e)输出输出D D，图，图(f)(f)输出输出E E。得到该有
47、向图的拓扑有序序列为：得到该有向图的拓扑有序序列为：ACBDEFACBDEF。（注：结果不唯一。）（注：结果不唯一。）拓扑排序的算法如拓扑排序的算法如算法算法6.96.9所示。所示。6.5 6.5 实例解析与编程实现实例解析与编程实现【例【例6-86-8】已知如下图所示的有向图，请给出该图的：】已知如下图所示的有向图，请给出该图的：(1)(1)每个顶点的出度和入度。每个顶点的出度和入度。(2)(2)邻接矩阵。邻接矩阵。(3)(3)邻接表。邻接表。(4)(4)逆邻接表。逆邻接表。解：解：(1)(1)每个顶点的出度和入度如下：每个顶点的出度和入度如下：(2)(2)邻接矩阵如下所示：邻接矩阵如下所示
48、：(3)(3)邻接表如下图所示。邻接表如下图所示。(4)(4)逆邻接表如下图所示。逆邻接表如下图所示。【例【例6-96-9】用深度优先遍历和广度优先遍历对如下用深度优先遍历和广度优先遍历对如下图所示的无向图图所示的无向图G G进行遍历进行遍历(从顶点从顶点1 1出发出发)，给出遍历，给出遍历序列，并画出对应的深度优先生成树和广度优先生成序列，并画出对应的深度优先生成树和广度优先生成树。树。解：图中的深度优先序列为解：图中的深度优先序列为1,2,4,7,5,3,8,1,2,4,7,5,3,8,6 6；广度优先序列为；广度优先序列为1,2,3,4,5,6,8,71,2,3,4,5,6,8,7。深度
49、优。深度优先生成树如下图先生成树如下图(a)(a)所示，广度优先生成树如下图所示，广度优先生成树如下图(b)(b)所所示。示。【例【例6-106-10】编程实现邻接矩阵对图的存储。编程实现邻接矩阵对图的存储。参考程序见参考程序见算法例算法例6-10 6-10。该算法的执行时间是该算法的执行时间是O(n+n2+e)O(n+n2+e)，由于，由于en2en2，算法的，算法的时间复杂度是时间复杂度是O(n2)O(n2)。无向图的邻接矩阵是对称矩阵，对于规模大的邻接无向图的邻接矩阵是对称矩阵，对于规模大的邻接矩阵可采取压缩存储方式存储。矩阵可采取压缩存储方式存储。【例【例6-116-11】编程实现邻接
50、表对图的存储。】编程实现邻接表对图的存储。参考程序见参考程序见算法例算法例6-11 6-11。【例【例6-126-12】编程求有向赋权图的最短路径（使用迪编程求有向赋权图的最短路径（使用迪杰斯特拉算法）。杰斯特拉算法）。参考程序见参考程序见算法例算法例6-12 6-12。本章小结本章小结 图由一个非空的有穷顶点集和一个边或弧的有穷图由一个非空的有穷顶点集和一个边或弧的有穷集所构成。集所构成。图有有向图和无向图两种，顶点间的关系是有方图有有向图和无向图两种，顶点间的关系是有方向的图称为有向图，否则称为无向图。向的图称为有向图，否则称为无向图。具有具有n(n-1)/2n(n-1)/2条边的无向图称
