第第10章章图图图图(graph)是是一一种种比比线线性性表表、树树更更为为复复杂杂的的数数据据结结构构。在在线线性性表表中中，数数据据元元素素之之间间呈呈线线性性关关系系，即即每每个个元元素素只只有有一一个个直直接接前前驱驱和和一一个个直直接接后后继继。图图的的应应用用领领域域十十分分广广泛泛，如如化化学学分分析析、工工程程设设计计、遗遗传传学学、人人工工智智能能等等。本本章章主主要要介介绍绍图图的的定定义义、图图的的存存储储结结构构、图图的的遍遍历历、最小生成树、关键路径和最短路径。最小生成树、关键路径和最短路径。 本章重点：本章重点： 1 1、图的定义及性质、图的定义及性质 2 2、图的邻接矩阵和邻接表表示、图的邻接矩阵和邻接表表示 3 3、图的各种遍历、图的各种遍历 4 4、最小生成树、最小生成树 5 5、关键路径、关键路径 6 6、最短路径、最短路径10.1图的定义与相关概念图的定义与相关概念图图G也是由数据元素集合也是由数据元素集合V与边的集合与边的集合E构成的。在图中，数据元构成的。在图中，数据元素通常称为顶点（素通常称为顶点（Vertex）。其中，顶点集合）。其中，顶点集合V不能为空，边表示不能为空，边表示顶点之间的关系。顶点之间的关系。若若E，则，则表示从顶点表示从顶点x到顶点到顶点y存在一条弧存在一条弧（Arc），），x称为弧尾（称为弧尾（tail）或起始点（）或起始点（initialnode），），y称为弧称为弧头（头（head）或终端点（）或终端点（terminalnode）。这样的图被称为有向图）。这样的图被称为有向图（digraph）。）。如果如果E且有且有E，即，即E是对称的，则用无序对是对称的，则用无序对(x,y)代替有序对代替有序对和和，表示，表示x与与y之间存在一条边之间存在一条边（edge），这样的图称为无向图（），这样的图称为无向图（undigraph）。如图）。如图10.1所示。所示。10.1图的定义与相关概念图的定义与相关概念图图G的形式化定义为：的形式化定义为：G=(V,E)，其中，其中，V=x|x数据元素集数据元素集合合，E=|Path(x,y)/(xV,yV)。Path(x,y)表示表示的意义或信息。的意义或信息。在图在图10.1中，有向图中，有向图G1可以表示为可以表示为G1=(V1,E1)，其中，顶点的，其中，顶点的集合为集合为V1=a,b,c,d，边的集合为，边的集合为E1=,。无向图。无向图G2可可以表示为以表示为G2=(V2,E2)，其中，顶点的集合为，其中，顶点的集合为V2=a,b,c,d，边的集，边的集合为合为E2=(a,b),(a,c),(a,d),(b,c),(c,d)。10.1图的定义与相关概念图的定义与相关概念1邻接点邻接点对于无向图对于无向图G=(V,E)，若边，若边(vi,vj)E，则称，则称vi和和vj互为邻接点互为邻接点（adjacent），即），即vi和和vj相邻接。边相邻接。边(vi,vj)依附于顶点依附于顶点vi和和vj，或，或者说者说(vi,vj)与顶点与顶点vi、vj相关联。对于有向图相关联。对于有向图G=(V,A)，若弧，若弧A，则称顶点，则称顶点vi邻接到顶点邻接到顶点vj，顶点，顶点vj邻接自顶点邻接自顶点vi。弧。弧和顶点和顶点vi、vj相关联。相关联。无向图无向图G2的边的集合为的边的集合为E=(a,b),(a,c),(a,d),(b,c),(c,d)，顶点顶点a和和b互为邻接点，边互为邻接点，边(a,b)依附于顶点依附于顶点a和和b。顶点。顶点c和和d互为邻互为邻接点，边接点，边(c,d)依附于顶点依附于顶点c和和d。有向图。有向图G1的弧的集合为的弧的集合为A=,，顶点，顶点a邻接到邻接到顶点顶点b，弧，弧与顶点与顶点a和和b相关联。顶点相关联。顶点c邻接自顶点邻接自顶点d，弧，弧与顶点与顶点d和和c相关联。相关联。10.1图的定义与相关概念图的定义与相关概念2顶点的度顶点的度对于无向图，顶点对于无向图，顶点v的度是指与的度是指与v相关联的边的数目，记作相关联的边的数目，记作TD(v)。对于。对于有向图，以顶点有向图，以顶点v为弧头的数目称为顶点为弧头的数目称为顶点v的入度的入度(indegree)，记作，记作ID(v)。以顶点。以顶点v为弧尾的数目称为为弧尾的数目称为v的出度的出度(outdegree)，记作，记作OD(v)。顶点。顶点v的度的度(degree)为为TD(v)=ID(v)+OD(v)。无向图无向图G2中顶点中顶点a的度为的度为3，顶点，顶点b的度为的度为2，顶点，顶点c的度为的度为3，顶点，顶点d的度的度为为2。有向图。有向图G1的弧的集合为的弧的集合为A=,，顶点，顶点a、b、c和和d的入度分别为的入度分别为1、2、2和和1，顶点，顶点a、b、c和和d的出度分别为的出度分别为2、1、2和和1，顶点，顶点a、b、c和和d的度分别为的度分别为3、3、4和和2。若图的顶点的个数为若图的顶点的个数为n，边数或弧数为，边数或弧数为e，顶点，顶点vi的度记作的度记作TD(vi)，则顶，则顶点的度与弧或者边数满足关系：点的度与弧或者边数满足关系：e=10.1图的定义与相关概念图的定义与相关概念3路径路径无向图无向图G中，从顶点中，从顶点v到顶点到顶点v的路径（的路径（path）是从）是从v出发，经出发，经过一系列的顶点序列到达顶点过一系列的顶点序列到达顶点v。如果。如果G是有向图，则路径也是有向是有向图，则路径也是有向的，路径的长度是路径上弧或边的数目。第一个顶点和最后一个顶的，路径的长度是路径上弧或边的数目。第一个顶点和最后一个顶点相同的路径称为回路或环（点相同的路径称为回路或环（cycle）。序列中顶点不重复出现的路）。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点外，其他顶点不径称为简单路径。除了第一个顶点和最后一个顶点外，其他顶点不重复出现的回路，称为简单回路或简单环。重复出现的回路，称为简单回路或简单环。在图在图10.1所示的有向图所示的有向图G1中，顶点序列中，顶点序列adca构成了一构成了一个简单回路。在无向图个简单回路。在无向图G2中，从顶点中，从顶点a到顶点到顶点c所经过的路径为所经过的路径为a，d和和c（或（或a、b、c）。）。10.1图的定义与相关概念图的定义与相关概念4子图子图假设存在两个图假设存在两个图G=V,E和和G=V,E，若，若G的顶点和关系都是的顶点和关系都是V的子集，即有的子集，即有VV，EE，则，则G为为G的子图。如图的子图。如图10.2所示。所示。10.1图的定义与相关概念图的定义与相关概念5连通图和强连通图连通图和强连通图对于无向图对于无向图G，如果从顶点，如果从顶点vi到顶点到顶点vj存在路径，则称存在路径，则称vi到到vj是连通是连通的。如果对于图中任意两个顶点的。如果对于图中任意两个顶点vi、vjV，vi和和vj都是连通的，则称都是连通的，则称G是连通图（是连通图（connectedgraph）。无向图中的极大连通子图称为连通）。无向图中的极大连通子图称为连通分量。无向图分量。无向图G3与连通分量如图与连通分量如图10.3所示。所示。10.1图的定义与相关概念图的定义与相关概念对于有向图对于有向图G，如果对每一对顶点，如果对每一对顶点vi和和vj，且，且vivj，从，从vi到到vj和和vj到到vi都存在路径，则都存在路径，则G为强连通图。有向图中的极大强连通子图称为为强连通图。有向图中的极大强连通子图称为有向图的强连通分量。有向图有向图的强连通分量。有向图G4与强连通分量如图与强连通分量如图10.4所示。所示。10.1图的定义与相关概念图的定义与相关概念6完全图完全图若图的顶点数目是若图的顶点数目是n，图的边（弧）的数目是，图的边（弧）的数目是e。若不存在顶点到。若不存在顶点到自身的边或弧，即若存在自身的边或弧，即若存在，则有，则有vivj。对于无向图，边数。对于无向图，边数e的取值范围为的取值范围为0n(n-1)/2。将具有。将具有n(n-1)/2条边的无向图称为完全条边的无向图称为完全图（图（completedgraph）或无向完全图。对于有向图，弧数）或无向完全图。对于有向图，弧数e的取值的取值范围是范围是0n(n-1)。将具有。将具有n(n-1)条弧的有向图称为有向完全图。条弧的有向图称为有向完全图。10.1图的定义与相关概念图的定义与相关概念7稀疏图和稠密图稀疏图和稠密图具有具有enlogn条弧或边的图，称为稀疏图。反之，称为稠密图。条弧或边的图，称为稀疏图。反之，称为稠密图。8生成树生成树一个连通图的生成树是一个极小连通子图，它含有图的全部顶点，但一个连通图的生成树是一个极小连通子图，它含有图的全部顶点，但只有足以构成一棵树的只有足以构成一棵树的n-1条边。如果在该生成树中添加一条边，则条边。如果在该生成树中添加一条边，则一定会在图中出现一个环。一棵具有一定会在图中出现一个环。一棵具有n个顶点的生成树仅有个顶点的生成树仅有n-1条边，如条边，如果少于果少于n-1条边，则该图是非连通的。多于条边，则该图是非连通的。多于n-1条边，则一定有环的出条边，则一定有环的出现。反过来，具有现。反过来，具有n-1条边的图不一定能构成生成树。一个图的生成树条边的图不一定能构成生成树。一个图的生成树不一定是唯一的。图不一定是唯一的。图10.5是无向图是无向图G5中最大连通分量的一棵生成树。中最大连通分量的一棵生成树。10.1图的定义与相关概念图的定义与相关概念9网网在图的边或弧上，有时标有与它们相关的数，这种与图的边或弧相关在图的边或弧上，有时标有与它们相关的数，这种与图的边或弧相关的数称作权（的数称作权（weight）。这些权可以表示从一个顶点到另一个顶点的）。这些权可以表示从一个顶点到另一个顶点的距离或代价。这种带权的图称作网（距离或代价。这种带权的图称作网（network）。一个网如图）。一个网如图10.6所所示。示。10.1图的定义与相关概念图的定义与相关概念10.1.3 10.1.3 图的抽象数据类型图的抽象数据类型1数据对象集合数据对象集合图的数据对象为图的各个顶点和边的集合。图中的顶点是没有先后次图的数据对象为图的各个顶点和边的集合。图中的顶点是没有先后次序的。图分为有向图和无向图，图中结点之间的关系用弧或边表示，通序的。图分为有向图和无向图，图中结点之间的关系用弧或边表示，通过弧或边相连的顶点相邻接或相关联。过弧或边相连的顶点相邻接或相关联。图中顶点之间是多对多的关系，即任何一个顶点可以有与之邻接或关图中顶点之间是多对多的关系，即任何一个顶点可以有与之邻接或关联的顶点。联的顶点。10.1图的定义与相关概念图的定义与相关概念2基本操作集合基本操作集合（1）CreateGraph(&G)：图的创建。根据顶点和边或弧构造一个图：图的创建。根据顶点和边或弧构造一个图G。（3）DestroyGraph(&T)：销毁图的操作。如果图：销毁图的操作。如果图G存在，则将图存在，则将图G销毁。销毁。（4）LocateVertex(G,v)：返回顶点：返回顶点v在图的位置。在图在图的位置。在图G中查找顶点中查找顶点v，如，如果找到该顶点，返回顶点在图果找到该顶点，返回顶点在图G中的位置。中的位置。（5）GetVertex(G,i)：返回图：返回图G中序号中序号i对应的值。对应的值。i是图是图G某个顶点的序号，某个顶点的序号，返回图返回图G中序号中序号i对应的值。对应的值。（6）FirstAdjVertex(G,v)：返回：返回v的第一个邻接顶点。在图的第一个邻接顶点。在图G中查找中查找v的第一的第一个邻接顶点，并将其返回。如果在个邻接顶点，并将其返回。如果在G中没有邻接顶点，则返回中没有邻接顶点，则返回-1。10.1图的定义与相关概念图的定义与相关概念（7）NextAdjVertex(G,v,w)：返回：返回v的下一个邻接顶点。在图的下一个邻接顶点。在图G中查找中查找v的下一个邻接的下一个邻接顶点，即顶点，即w的第一个邻接顶点，找到返回其值，否则，返回的第一个邻接顶点，找到返回其值，否则，返回-1。（8）InsertVertex(&G,v)：图的顶点插入操作。在图：图的顶点插入操作。在图G中增加新的顶点中增加新的顶点v，并将图的顶，并将图的顶点数增点数增1。（9）DeleteVertex(&G,v)：图的顶点删除操作。将图：图的顶点删除操作。将图G中的顶点中的顶点v及相关联的弧删除。及相关联的弧删除。（10）InsertArc(&G,v,w)：图的弧插入操作。在图：图的弧插入操作。在图G中增加弧中增加弧。对于无向图，。对于无向图，还要插入弧还要插入弧。（11）DeleteArc(&G,v,w)：图的弧删除操作。在图：图的弧删除操作。在图G中删除弧中删除弧。对于无向图，。对于无向图，还要删除弧还要删除弧。（12）DFSTraverseGraph(G)：图的深度遍历操作。从图中的某个顶点出发，对图进行：图的深度遍历操作。从图中的某个顶点出发，对图进行深度遍历。深度遍历。（13）BFSTraverseGraph(G)：图的广度遍历操作。从图中的某个顶点出发，对图进行：图的广度遍历操作。从图中的某个顶点出发，对图进行广度遍历。广度遍历。10.2图的存储结构图的存储结构10.2.1 邻接矩阵（数组表示法）1什么是图的邻接矩阵什么是图的邻接矩阵图的邻接矩阵可利用两个数组实现：一个一维数组用来存储图中的图的邻接矩阵可利用两个数组实现：一个一维数组用来存储图中的顶点信息；另一个二维数组用来存储图中的顶点之间的关系，该二维顶点信息；另一个二维数组用来存储图中的顶点之间的关系，该二维数组被称为邻接矩阵。如果图是一个无权图，则邻接矩阵表示为：数组被称为邻接矩阵。如果图是一个无权图，则邻接矩阵表示为：对于带权图，有对于带权图，有10.2图的存储结构图的存储结构在图在图10.1中，两个图弧和边的集合分别为中，两个图弧和边的集合分别为A=,和和E=(a,b),(a,c),(a,d),(b,c),(c,d)。它们的邻接矩阵表示如图。它们的邻接矩阵表示如图10.7所示。所示。带权图的邻接矩阵表示如图带权图的邻接矩阵表示如图10.8所示。所示。10.2图的存储结构图的存储结构图的邻接矩阵存储结构描述如下：图的邻接矩阵存储结构描述如下：#defineINFINITY65535/*65535被认为是一个无穷大的值被认为是一个无穷大的值*/#defineMaxSize50/*最大顶点个数最大顶点个数*/typedefenumDG,DN,UG,UNGraphKind;/*图的类型图的类型*/typedefstructVRTypeadj;/*对于无权图，用对于无权图，用1表示相邻，表示相邻，0表示不相邻表示不相邻*/InfoPtr*info;/*与弧或边的相关信息与弧或边的相关信息*/ArcNode,AdjMatrixMaxSizeMaxSize;typedefstruct/*图的类型定义图的类型定义*/VertexTypevexMaxSize;/*用于存储顶点用于存储顶点*/AdjMatrixarc;/*邻接矩阵，存储边或弧的信息邻接矩阵，存储边或弧的信息*/intvexnum,arcnum;/*顶点数和边（弧）的数目顶点数和边（弧）的数目*/GraphKindkind;/*图的类型图的类型*/MGraph;其中，数组其中，数组vex用于存储图中的顶点信息，如用于存储图中的顶点信息，如a、b、c、d，arcs用于存储图中用于存储图中顶点信息。顶点信息。10.2图的存储结构图的存储结构2邻接矩阵应用举例邻接矩阵应用举例【例【例10_1】试编写一个算法，采用邻接矩阵创建一个如图】试编写一个算法，采用邻接矩阵创建一个如图10.8所所示的有向网示的有向网G。分析：主要考察图的邻接矩阵表示与算法实现。图的创建包括两分析：主要考察图的邻接矩阵表示与算法实现。图的创建包括两个部分：一个是创建顶点，顶点信息可存储到一个向量（一维数组）个部分：一个是创建顶点，顶点信息可存储到一个向量（一维数组）中；一个是创建弧的信息，包括弧的相关顶点和权值，可存储到二中；一个是创建弧的信息，包括弧的相关顶点和权值，可存储到二维数组中，其中，二维数组的两个下标分别表示两个相关顶点在矩维数组中，其中，二维数组的两个下标分别表示两个相关顶点在矩阵中的行号和列号，权值存入到数组中。阵中的行号和列号，权值存入到数组中。10.2图的存储结构图的存储结构10.2.2 邻接表邻接表（邻接表（adjacencylist）是图的一种链式存储方式。采用邻接表）是图的一种链式存储方式。采用邻接表表示图一般需要两个表结构：边表和表头结点表。表示图一般需要两个表结构：边表和表头结点表。边表：在邻接表中，对图中的每个顶点都建立一个单链表，第边表：在邻接表中，对图中的每个顶点都建立一个单链表，第i个个单链表中的结点表示依附于顶点单链表中的结点表示依附于顶点vi的边（对有向图来说是以顶点的边（对有向图来说是以顶点vi为为尾的弧），这种链表称为边表，其中结点称为弧结点，弧结点由尾的弧），这种链表称为边表，其中结点称为弧结点，弧结点由3个个域组成：邻接点域（域组成：邻接点域（adjvex）、数据域（）、数据域（info）和指针域）和指针域（nextarc）。其中，邻接点域表示与相应的表头顶点邻接点的位置，）。其中，邻接点域表示与相应的表头顶点邻接点的位置，数据域存储与边或弧的信息，指针域用来指示下一个边或弧的结点。数据域存储与边或弧的信息，指针域用来指示下一个边或弧的结点。10.2图的存储结构图的存储结构表头结点表：在每个链表前面设置一个头结点，除了设有存储各表头结点表：在每个链表前面设置一个头结点，除了设有存储各个顶点信息的数据域（个顶点信息的数据域（data）外，还设有指向链表中第一个结点的）外，还设有指向链表中第一个结点的链域（链域（firstarc），我们把这种表称为表头结点表，相应地，结点称），我们把这种表称为表头结点表，相应地，结点称为表头结点。通常情况下，表头结点采用顺序存储结构实现，这样为表头结点。通常情况下，表头结点采用顺序存储结构实现，这样可以随机地访问任意顶点。可以随机地访问任意顶点。边表结点和表头结点的结构如图边表结点和表头结点的结构如图10.10所示。所示。10.2图的存储结构图的存储结构图图10.1所示的图所示的图G1和和G2用邻接表表示如图用邻接表表示如图10.11所示。所示。图图10.8所示的带权图的邻接表如图所示的带权图的邻接表如图10.12所示。所示。10.2图的存储结构图的存储结构图的邻接表存储结构描述如下：图的邻接表存储结构描述如下：#defineMaxSize50/*最大顶点个数最大顶点个数*/typedefenumDG,DN,UG,UNGraphKind;/*图的类型：有向图、有向图的类型：有向图、有向网、无向图和无向网网、无向图和无向网*/typedefstructArcNode/*边结点的类型定义边结点的类型定义*/intadjvex;/*弧指向的顶点的位置弧指向的顶点的位置*/InfoPtr*info;/*与弧相关的信息与弧相关的信息*/structArcNode*nextarc;/*指示下一个与该顶点相邻接的顶点指示下一个与该顶点相邻接的顶点*/ArcNode;typedefstructVNode/*头结点的类型定义头结点的类型定义*/VertexTypedata;/*用于存储顶点用于存储顶点*/ArcNode*firstarc;/*指示第一个与该顶点邻接的顶点指示第一个与该顶点邻接的顶点*/VNode,AdjListMaxSize;10.2图的存储结构图的存储结构typedefstruct/*图的类型定义图的类型定义*/AdjListvertex;intvexnum,arcnum;/*图的顶点数目与弧的数目图的顶点数目与弧的数目*/GraphKindkind;/*图的类型图的类型*/AdjGraph;如果无向图如果无向图G中有中有n个顶点和个顶点和e条边，则图采用邻接表表示，需要条边，则图采用邻接表表示，需要n个头结点和个头结点和2e个表结点。在个表结点。在e远小于远小于n(n-1)/2时，采用邻接表存储表时，采用邻接表存储表示显然要比采用邻接矩阵表示更能节省空间。示显然要比采用邻接矩阵表示更能节省空间。10.2图的存储结构图的存储结构有有时时为为了了便便于于求求某某个个顶顶点点的的入入度度，需需要要建建立立一一个个有有向向图图的的逆逆邻邻接接链链表表，也也就就是是为为每每个个顶顶点点vi建建立立一一个个以以vi为为弧弧头头的的链链表表。在在邻邻接接表表中中，边边表表结结点点的的邻邻接接点点域域的的值值为为i的的个个数数，就就是是顶顶点点vi的的入入度度。因因此此如如果果要要求求某某个个顶顶点点的的入入度度，则则需需要要对对整整个个邻邻接接表表进进行行遍遍历历。图图10.1所示的有向图所示的有向图G1的逆邻接链表如图的逆邻接链表如图10.13所示。所示。10.2图的存储结构图的存储结构【例【例10_2】编写一个创建如图】编写一个创建如图10.1所示的无向图（假设采用邻接表表示图所示的无向图（假设采用邻接表表示图）。）。分析：主要考察图的邻接表存储结构。图的创建包括两个部分：创建表头分析：主要考察图的邻接表存储结构。图的创建包括两个部分：创建表头结点和边表结点。其中，表头结点利用一个数组实现，数组包括两个域：一结点和边表结点。其中，表头结点利用一个数组实现，数组包括两个域：一个保存顶点的值；一个是指针，用于指向与顶点相关联的顶点对应结点。代个保存顶点的值；一个是指针，用于指向与顶点相关联的顶点对应结点。代码如下：码如下：for(i=0;ivexnum;i+)/*将顶点存储在表头结点中将顶点存储在表头结点中*/scanf(%s,G-vertexi.data);G-vertexi.firstarc=NULL;/*将相关联的顶点置为空将相关联的顶点置为空*/10.2图的存储结构图的存储结构10.2.3 十字链表十字链表（十字链表（orthogonallist）是有向图的另一种链式存储结构，）是有向图的另一种链式存储结构，它可以看作是将有向图的邻接表与逆邻接链表结合起来的得到的一它可以看作是将有向图的邻接表与逆邻接链表结合起来的得到的一种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点也有一个结点，这些结点的结构如图应于每个顶点也有一个结点，这些结点的结构如图10.15所示。所示。弧结点包含弧结点包含5个域：尾域个域：尾域tailvex、头域、头域headvex、infor域和两个域和两个指针域指针域hlink、tlink。其中，尾域。其中，尾域tailvex用于表示弧尾顶点在图中用于表示弧尾顶点在图中的位置，头域的位置，头域headvex表示弧头顶点在图中的位置，表示弧头顶点在图中的位置，info域表示弧域表示弧的相关信息，指针域的相关信息，指针域hlink指向弧头相同的下一个条弧，指向弧头相同的下一个条弧，tlink指向弧指向弧尾相同的下一条弧。尾相同的下一条弧。10.2图的存储结构图的存储结构顶点结点包含顶点结点包含3个域：个域：data域和域和firstin、firstout域，其中，域，其中，data域域存储与顶点相关的信息，如顶点的名称，存储与顶点相关的信息，如顶点的名称，firstin和和firstout是两个指针是两个指针域，分别指向以该顶点为弧头和弧尾的第一个弧度结点。域，分别指向以该顶点为弧头和弧尾的第一个弧度结点。有向图有向图G1的十字链表存储表示如图的十字链表存储表示如图10.16所示。所示。10.2图的存储结构图的存储结构有向图的十字链表存储结构描述如下：有向图的十字链表存储结构描述如下：#defineMaxSize50/*最大顶点个数最大顶点个数*/typedefstructArcNode/*弧结点的类型定义弧结点的类型定义*/intheadvex,tailvex;/*弧的头顶点和尾顶点位置弧的头顶点和尾顶点位置*/InfoPtr*info;/*与弧相关的信息与弧相关的信息*/struct*hlink,*tlink;/*指示弧头和弧尾相同的结点指示弧头和弧尾相同的结点*/ArcNode;typedefstructVNode/*顶点结点的类型定义顶点结点的类型定义*/VertexTypedata;/*用于存储顶点用于存储顶点*/ArcNode*firstin,*firstout;/*分别指向顶点的第一条入弧和出弧分别指向顶点的第一条入弧和出弧*/VNode;typedefstruct/*图的类型定义图的类型定义*/VNodevertexMaxSize;intvexnum,arcnum;/*图的顶点数目与弧的数目图的顶点数目与弧的数目*/OLGraph;10.2图的存储结构图的存储结构10.2.4 10.2.4 邻接多重链表邻接多重链表邻接多重链表（邻接多重链表（adjacencymultilist）是无向图的另一种链式）是无向图的另一种链式存储结构。在无向图的邻接表存储表示中，虽然很容易求得顶点和存储结构。在无向图的邻接表存储表示中，虽然很容易求得顶点和边的各种信息，但是对于每一条边（边的各种信息，但是对于每一条边（vi，vj）都有两个结点，分别在）都有两个结点，分别在第第i个和第个和第j个链表中，这给图的某些操作带来不变，例如，要删除一个链表中，这给图的某些操作带来不变，例如，要删除一条边，此时需要找到表示同一条边的两个顶点。因此，在进行这一条边，此时需要找到表示同一条边的两个顶点。因此，在进行这一类操作时，采用邻接多重链表比较合适，邻接多重链表是将图的一类操作时，采用邻接多重链表比较合适，邻接多重链表是将图的一条边用一个结点表示。它的结点结构如图条边用一个结点表示。它的结点结构如图10.17所示。所示。10.2图的存储结构图的存储结构无向图无向图G2的多重链表如图的多重链表如图10.18所示。所示。10.2图的存储结构图的存储结构无向图的多重链表存储结构描述如下：无向图的多重链表存储结构描述如下：#defineMaxSize50/*最大顶点个数最大顶点个数*/typedefstructEdgeNode/*边结点的类型定义边结点的类型定义*/intmark,ivex,jvex;/*访问标志和边的两个顶点位置访问标志和边的两个顶点位置*/InfoPtr*info;/*与边相关的信息与边相关的信息*/struct*ilink,*jlink;/*指示与边顶点相同的结点指示与边顶点相同的结点*/EdgeNode;typedefstructVNode/*顶点结点的类型定义顶点结点的类型定义*/VertexTypedata;/*用于存储顶点用于存储顶点*/EdgeNode*firstedge;/*指向依附于顶点的第一条边指向依附于顶点的第一条边*/VexNode;typedefstruct/*图的类型定义图的类型定义*/VexNodevertexMaxSize;intvexnum,edgenum;/*图的顶点数目与边的数目图的顶点数目与边的数目*/AdjMultiGraph;10.3图的遍历图的遍历与树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶与树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。这一过程就叫做图的遍历点，且使每一个顶点仅被访问一次。这一过程就叫做图的遍历（traversinggraph）。）。10.3.1 图的深度优先搜索1什么是图的深度搜索什么是图的深度搜索图的深度优先搜索（图的深度优先搜索（depth_firstsearch）遍历类似于树的先）遍历类似于树的先根遍历，是树的先根遍历的推广。图的深度优先遍历的思想是：假根遍历，是树的先根遍历的推广。图的深度优先遍历的思想是：假设初始状态是图中所有顶点未曾被访问，从图中某个顶点设初始状态是图中所有顶点未曾被访问，从图中某个顶点v0出发，出发，访问顶点访问顶点v0。然后依次从。然后依次从v0的未被访问的邻接点出发深度优先遍历的未被访问的邻接点出发深度优先遍历图，直至图中所有和图，直至图中所有和v0有路径相通的顶点都被访问到；若此时图中有路径相通的顶点都被访问到；若此时图中还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复执行上述过程，直到图中所有的顶点都被访问过。重复执行上述过程，直到图中所有的顶点都被访问过。10.3图的遍历图的遍历图图的的深深度度优优先先搜搜索索遍遍历历过过程程如如图图10.18所所示示。实实箭箭头头表表示示访访问问顶顶点的方向，虚箭头表示回溯，数字表示访问或回溯的次序。点的方向，虚箭头表示回溯，数字表示访问或回溯的次序。10.3图的遍历图的遍历2图的深度优先搜索遍历的算法实现图的深度优先搜索遍历的算法实现图的深度优先遍历（邻接表实现）的算法描述如下。图的深度优先遍历（邻接表实现）的算法描述如下。intvisitedMaxSize; /*访问标志数组访问标志数组*/voidDFSTraverse(AdjGraphG)/*从第从第1个顶点起，深度优先搜索遍历图个顶点起，深度优先搜索遍历图G*/intv;for(v=0;vG.vexnum;v+)visitedv=0;/*访问标志数组初始化为未被访问访问标志数组初始化为未被访问*/for(v=0;v=0;w=NextAdjVertex(G,G.vertexv.data,G.vertexw.data)if(!visitedw)DFS(G,w);/*递归调用递归调用DFS对对v的尚未访的尚未访问的序号为问的序号为w的邻接顶点的邻接顶点*/10.3图的遍历图的遍历如如果果该该图图是是一一个个无无向向连连通通图图或或者者该该图图是是一一个个强强连连通通图图，则则只只需需要要调调 用用 一一 次次 DFS(G,v)就就 可可 以以 遍遍 历历 整整 个个 图图 ， 否否 则则 需需 要要 多多 次次 调调 用用DFS(G,v)。 在在 遍遍 历历 图图 时时 ， 对对 图图 中中 的的 每每 个个 顶顶 点点 至至 多多 调调 用用 一一 次次DFS(G,v)函函数数，因因为为一一旦旦某某个个顶顶点点被被标标志志为为已已被被访访问问，就就不不再再从从它它出出发发进进行行搜搜索索。因因此此，遍遍历历图图的的过过程程实实质质上上是是对对每每个个顶顶点点查查找找其其邻邻接接点点的的过过程程。其其时时间间耗耗费费取取决决于于所所采采用用的的存存储储结结构构。当当用用二二维维数数组组表表示示邻邻接接矩矩阵阵作作为为图图的的存存储储结结构构时时，查查找找每每个个顶顶点点的的邻邻接接点点所所需需时时间间为为O(n2)，其其中中n为为图图中中的的顶顶点点数数。当当以以邻邻接接表表作作为为图图的的存存储储结结构构时时，查查找找邻邻接接点点的的时时间间为为O(e)，其其中中，e为为无无向向图图边边的的数数目目或或有有向向图图弧弧的的数数目目。由由此此，当当以以邻邻接接表表作作为为存存储储结结构构时时，深深度度优优先先搜搜索索遍遍历图的时间复杂度为历图的时间复杂度为O(n+e)。10.3图的遍历图的遍历另一种写法是：另一种写法是：voidDFS(AdjGraphG,intv)/*从顶点从顶点v出发递归深度优先搜索遍历图出发递归深度优先搜索遍历图G*/ArcNode*p;visitedv=1;/*访问标志设置为已访问访问标志设置为已访问*/Visit(G.vertexv.data); /*访问第访问第v个顶点个顶点*/p=G.vertexv.firstarc;/*取取v的边表头指针，的边表头指针，p指向指向v的邻接点的邻接点*/while(p)/*依次搜索依次搜索v的邻接点的邻接点*/if(!visitedp-adjvex)/*若若v尚未被访问尚未被访问*/DFS(G,p-adjvex);/*以以v的邻接点纵深搜索的邻接点纵深搜索*/p=p-nextarc;/*找找v的下一个邻接点的下一个邻接点*/10.3图的遍历图的遍历以邻接表作为存储结构，查找以邻接表作为存储结构，查找v的第一个邻接点的算法实现如下。的第一个邻接点的算法实现如下。intFirstAdjVertex(AdjGraphG,VertexTypev)/*返回顶点返回顶点v的第一个邻接顶点的序号的第一个邻接顶点的序号*/ArcNode*p;intv1;v1=LocateVertex(G,v);/*v1为顶点为顶点v在图在图G中的序号中的序号*/p=G.vertexv1.firstarc;if(p)/*如果顶点如果顶点v的第一的第一个邻接点存在，返回邻接点的序号，否则返回个邻接点存在，返回邻接点的序号，否则返回-1*/returnp-adjvex;elsereturn-1;10.3图的遍历图的遍历以邻接表作为存储结构，查找以邻接表作为存储结构，查找v的相对于的相对于w的下一个邻接点的算法实现如下。的下一个邻接点的算法实现如下。intNextAdjVertex(AdjGraphG,VertexTypev,VertexTypew)/*返回返回v的相对于的相对于w的下一个邻接顶点的序号的下一个邻接顶点的序号*/ArcNode*p,*next;intv1,w1;v1=LocateVertex(G,v);/*v1为顶点为顶点v在图在图G中的序号中的序号*/w1=LocateVertex(G,w);/*w1为顶点为顶点w在图在图G中的序号中的序号*/for(next=G.vertexv1.firstarc;next;)if(next-adjvex!=w1)next=next-nextarc;p=next;/*p指向顶点指向顶点v的邻接顶点的邻接顶点w的结点的结点*/if(!p|!p-nextarc)/*如果如果w不存在或不存在或w是最后一个邻接点，是最后一个邻接点，则返回则返回-1*/return-1;elsereturnp-nextarc-adjvex;/*返回返回v的相对于的相对于w的下一个邻的下一个邻接点的序号接点的序号*/10.3图的遍历图的遍历10.3.2 图的广度优先搜索1什么是图的广度优先搜索遍历什么是图的广度优先搜索遍历图的广度优先搜索图的广度优先搜索(breadth_firstsearch)遍历类似于树的层次遍历类似于树的层次遍历过程。图的广度优先搜索遍历的思想是：从图的某个顶点遍历过程。图的广度优先搜索遍历的思想是：从图的某个顶点v出发，出发，在访问了在访问了v之后依次访问之后依次访问v的各个未曾访问过的邻接点，然后分别从的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问他们的邻接点，并使这些邻接点出发依次访问他们的邻接点，并使“先被访问的顶点的先被访问的顶点的邻接点邻接点”先于先于“后被访问的顶点的邻接点后被访问的顶点的邻接点”被访问，直至图中所有被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有顶点未被访已被访问的顶点的邻接点都被访问到。若此时图中还有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中的所有顶点都被访问到为止。直至图中的所有顶点都被访问到为止。10.3图的遍历图的遍历 例如，图例如，图G6的广度优先搜索遍历的过程如图的广度优先搜索遍历的过程如图10.19所示。其中，所示。其中，箭头表示广度遍历的方向，旁边的数字表示遍历的次序。箭头表示广度遍历的方向，旁边的数字表示遍历的次序。因此，图因此，图G6的广度优先搜索遍历序列为的广度优先搜索遍历序列为a、b、c、d、e、f、g、h、i。10.3图的遍历图的遍历2图的广度优先遍历的算法实现图的广度优先遍历的算法实现与深度优先搜索类似，在图的广度优先的遍历过程中也需要一个与深度优先搜索类似，在图的广度优先的遍历过程中也需要一个访问标志数组访问标志数组visitedMaxSize，用来表示顶点是否被访问过。初，用来表示顶点是否被访问过。初始时，将图中的所有顶点的标志数组始时，将图中的所有顶点的标志数组visitedvi都初始化为都初始化为0，表，表示顶点未被访问。从第示顶点未被访问。从第1个顶点个顶点v0出发，访问该顶点并将标志数组置出发，访问该顶点并将标志数组置为为1。然后将。然后将v0入队，当队列不为空时，将队头元素（顶点）出队，入队，当队列不为空时，将队头元素（顶点）出队，依次访问该顶点的所有邻接点，同时将标志数组对应位置为依次访问该顶点的所有邻接点，同时将标志数组对应位置为1，并将，并将其邻接点依次入队。依次类推，直到图中的所有顶点都已被访问过。其邻接点依次入队。依次类推，直到图中的所有顶点都已被访问过。10.3图的遍历图的遍历图的广度优先搜索遍历的算法实现如下。图的广度优先搜索遍历的算法实现如下。voidBFSTraverse(AdjGraphG)/*从第从第1个顶点出发，按广度优先非递归遍历图个顶点出发，按广度优先非递归遍历图G*/intv,front,rear;ArcNode*p;intqueueMaxSize;/*定义一个队列定义一个队列Q*/front=rear=-1;/*初始化队列初始化队列Q*/for(v=0;vG.vexnum;v+)/*初始化标志位初始化标志位*/visitedv=0;v=0;visitedv=1;/*设置访问标志为设置访问标志为1，表示已经被访问过，表示已经被访问过*/Visit(G.vertexv.data);rear=(rear+1)%MaxSize;10.3图的遍历图的遍历queuerear=v;/*v入队列入队列*/while(frontadjvex=0)/*如果该顶点未被访问过如果该顶点未被访问过*/visitedp-adjvex=1;Visit(G.vertexp-adjvex.data);rear=(rear+1)%MaxSize;queuerear=p-adjvex;p=p-nextarc;/*p指向下一个邻接点指向下一个邻接点*/10.3图的遍历图的遍历10.3.3 图的遍历应用举例【例【例10_3】编写一个算法，要求对图】编写一个算法，要求对图10.18中的无向图中的无向图G6进行进行深度优先搜索遍历和广度优先搜索遍历（假设图采用邻接表存储）。深度优先搜索遍历和广度优先搜索遍历（假设图采用邻接表存储）。10.4图的连通性问题图的连通性问题10.4.1 无向图的连通分量与最小生成树在对无向图进行遍历时，对于连通图，仅需从图的任何一个顶在对无向图进行遍历时，对于连通图，仅需从图的任何一个顶点出发，进行深度优先搜索或广度优先搜索，就可访问到图中的所点出发，进行深度优先搜索或广度优先搜索，就可访问到图中的所有顶点。对于非连通图，则需从多个顶点出发进行搜索，而每一次有顶点。对于非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。各个连通分量中的顶点集。10.4图的连通性问题图的连通性问题图图10.3中的非连通图中的非连通图G3的邻接表如图的邻接表如图10.21所示。图所示。图G3是非连通图且有是非连通图且有3个连通分量，因此在对图个连通分量，因此在对图G3进行深度优先遍历时，需要从图的至少进行深度优先遍历时，需要从图的至少3个顶个顶点（顶点点（顶点a、顶点、顶点g和顶点和顶点i）出发，才能完成对图中的每个顶点的访问。对）出发，才能完成对图中的每个顶点的访问。对图图G3进行深度遍历，经过进行深度遍历，经过3次递归调用得到的次递归调用得到的3个序列分别为：（个序列分别为：（1）a、b、c、d、m、e、f；（；（2）g、h；（；（3）i、j、k、l。这。这3个顶点集分别加上依个顶点集分别加上依附于这些顶点的边，就构成了非连通图附于这些顶点的边，就构成了非连通图G3的两个连通分量，如图的两个连通分量，如图10.3（b）所示。所示。10.4图的连通性问题图的连通性问题设设E（G）为为连连通通图图G中中所所有有边边的的集集合合，则则从从图图中中任任一一顶顶点点出出发发遍遍历历图图时时，必必定定将将E(G)分分成成两两个个集集合合T（G）和和B（G），其其中中T（G）是是遍遍历历图图过过程程中中经经过过的的边边的的集集合合，B（G）是是剩剩余余边边的的集集合合。显显然然，T（G）和和图图G中中所所有有顶顶点点一一起起构构成成连连通通图图G的的极极小小连连通通子子图图，根根据据10.1节节的的定定义义，它它是是连连通通图图的的一一棵棵生生成成树树。由由深深度度优优先先搜搜索索得得到到的的为为深深度度优优先先生生成成树树对对于于连连通通图图，由由广广度度优优先先搜搜索索得得到到的的为为广广度度优优先先生生成成树树。图图10.22就就是是对对应应图图G6的的深深度度优优先先生生成成树树和广度优先生成树。和广度优先生成树。10.4图的连通性问题图的连通性问题对对于于非非连连通通图图，从从某某一一个个顶顶点点出出发发，对对图图进进行行深深度度优优先先搜搜索索遍遍历历或或者者广广度度优优先先搜搜遍遍历历，按按照照访访问问路路径径会会得得到到若若干干棵棵生生成成树树，这这些些生生成成树树放放在在一一起起就就构构成成了了森森林林。对对图图G3进进行行深深度度优优先先搜搜索索得得到到的的森森林林如图如图10.23所示。所示。10.4图的连通性问题图的连通性问题10.4.2 最小生成树许多应用问题都是一个求无向连通图的最小生成树问题。假设要许多应用问题都是一个求无向连通图的最小生成树问题。假设要在在n个城市之间铺设光缆，主要目标是要使这个城市之间铺设光缆，主要目标是要使这n个城市的任意两个个城市的任意两个之间都可以通信，且使铺设光缆的总费用最低。之间都可以通信，且使铺设光缆的总费用最低。在每两个城市之间都可以铺设光缆，在每两个城市之间都可以铺设光缆，n个城市之间，最多可能铺个城市之间，最多可能铺设设n(n-1)/2条光缆，但铺设光缆的费用很高，且各个城市之间铺设条光缆，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，那么，如何在这些可能的线路中选择光缆的费用不同，那么，如何在这些可能的线路中选择n-1条，以使条，以使总的费用最少呢？总的费用最少呢？10.4图的连通性问题图的连通性问题用连通网来表示用连通网来表示n个城市及个城市及n个城市间可能铺设的光缆，其中网的个城市间可能铺设的光缆，其中网的顶点表示城市，边表示两个城市之间的光缆线路，赋予边的权值表顶点表示城市，边表示两个城市之间的光缆线路，赋予边的权值表示相应的造价。对于示相应的造价。对于n个顶点的连通网可以建立许多不同的生成树，个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选择一条这样一每一棵生成树都可以是一个通信网。现在，我们要选择一条这样一棵生成树，也就是使总的造价最少。这个问题就是构造连通网的最棵生成树，也就是使总的造价最少。这个问题就是构造连通网的最小代价生成树（小代价生成树（minimumcostspanningtree）(简称为最小生简称为最小生成树成树)问题。其中一棵生成树的代价就是树上所有边的代价之和。代问题。其中一棵生成树的代价就是树上所有边的代价之和。代价在网中通过权值来表示，一个生成树的代价就是生成树各边的代价在网中通过权值来表示，一个生成树的代价就是生成树各边的代价之和。价之和。最小生成树有多种算法，其中大多数算法都利用了最小生成树的最小生成树有多种算法，其中大多数算法都利用了最小生成树的简称为简称为MST性质：性质：假设一个连通网假设一个连通网N=(V,E)，V是顶点的集合，是顶点的集合，E是边的集合，是边的集合，V有有一个非空子集一个非空子集U。如果。如果(u,v)是一条具有最小权值的边，其中，是一条具有最小权值的边，其中，uU，vV-U，那么一定存在一棵包含边，那么一定存在一棵包含边(u,v)的最小生成树。的最小生成树。10.4图的连通性问题图的连通性问题下面用反证法证明以上下面用反证法证明以上MST性质。性质。假设所有的最小生成树都不存在这样的一条边假设所有的最小生成树都不存在这样的一条边(u,v)。设。设T是连通是连通网网N中的一棵最小生成树，如果将边中的一棵最小生成树，如果将边(u,v)加入到加入到T中，根据生成树中，根据生成树的定义，的定义，T一定出现包含一定出现包含(u,v)的回路。另外的回路。另外T中一定存在一条边中一定存在一条边(u,v)的权值大于或等于的权值大于或等于(u,v)的权值，如果删除边的权值，如果删除边(u,v)，则得到一棵代价小于或等于则得到一棵代价小于或等于T的生成树的生成树T。T是包含边是包含边(u,v)的最小的最小生成树，这与假设矛盾。由此，性质得证。生成树，这与假设矛盾。由此，性质得证。10.4图的连通性问题图的连通性问题普里姆（普里姆（prim）算法和克鲁斯卡尔（）算法和克鲁斯卡尔（kruskal）算法就是利用）算法就是利用MST性质构造的最小生成树算法。性质构造的最小生成树算法。1普里姆算法普里姆算法假设假设N=V,E是连通网，是连通网，TE是是N的最小生成树边的集合。执行以的最小生成树边的集合。执行以下操作：下操作：（1）初始时，令）初始时，令U=u0(u0V)，TE=。（2）对于所有的边）对于所有的边uU，vV-U的边的边(u,v)E，将一条代价最，将一条代价最小的边小的边(u0,v0)放到集合放到集合TE中，同时将顶点中，同时将顶点v0放进集合放进集合U中。中。（3）重复执行步骤（）重复执行步骤（2），直到），直到U=V为止。为止。这时，边集合这时，边集合TE一定有一定有n-1条边，条边，T=V,TE就是连通网就是连通网N的最的最小生成树。小生成树。10.4图的连通性问题图的连通性问题例如，图例如，图10.24就是利用普里姆算法构造最小生成树的过程。就是利用普里姆算法构造最小生成树的过程。10.4图的连通性问题图的连通性问题初初始始时时，集集合合U=a，集集合合V-U=b,c,d,e,f，边边集集合合为为。只只有有一一个个元元素素aU，将将a从从U中中取取出出，比比较较顶顶点点a与与集集合合V-U中中顶顶点点构构成成的的代代价价最最小小边边，在在(a,b)、(a,c)、(a,d)中中，(a,c)的的权权值值最最小小，故故将将顶顶点点c加加入入到到集集合合U中中，边边(a,c)加加入入到到TE中中，此此时时有有U=a,c，V-U=b,d,e,f，TE=(a,c)。目目前前集集合合U的的元元素素与与集集合合V-U的的元元素素构构成成的的所所有有边边为为(a,b)、(a,d)、(b,c)、(c,d)、(c,e)和和(c,f)，其其中中代代价价最最小小的的边边为为(c,f)，故故把把顶顶点点f加加入入到到集集合合U中中，边边(c,f)加加 入入 到到 TE中中 ， 此此 时时 有有 U=a,c,f， V-U=b,d,e，TE=(a,c),(c,f)。依次类推，直到所有的顶点都加入到。依次类推，直到所有的顶点都加入到U中。中。10.4图的连通性问题图的连通性问题为实现这个算法需附设一个辅助数组为实现这个算法需附设一个辅助数组closeedgeMaxSize，以，以记录记录U到到V-U最小代价的边。对于每个顶点最小代价的边。对于每个顶点vV-U，在辅助数组中，在辅助数组中存在一个相应分量存在一个相应分量closeedgev，它包括两个域，它包括两个域adjvex和和lowcost，其中，其中，adjvex域用来表示该边中属于域用来表示该边中属于U中的顶点，中的顶点，lowcost域存储该边对应的权值。用公式描述为：域存储该边对应的权值。用公式描述为：closeedgev.lowcost=Min(cost(u,v)|uU)表表10.1普里姆算法各个参数的变化普里姆算法各个参数的变化10.4图的连通性问题图的连通性问题【例【例10_4】创建一个如图】创建一个如图10.24所示的无向网所示的无向网N，然后利用普里，然后利用普里姆算法求无向网的最小生成树。姆算法求无向网的最小生成树。分析：主要考察普里姆算法生成网的最小生成树算法。数组分析：主要考察普里姆算法生成网的最小生成树算法。数组closedge有两个域：有两个域：adjvex域和域和lowcost域。其中，域。其中，adjvex域用域用来存放依附于集合来存放依附于集合U的顶点，的顶点，lowcost域用来存放数组下标对应的顶域用来存放数组下标对应的顶点到顶点点到顶点(adjvex中的值中的值)的最小权值。因此，查找无向网的最小权值。因此，查找无向网N中的最中的最小权值的边就是在数组小权值的边就是在数组lowcost中找到最小值，输出生成树的边后，中找到最小值，输出生成树的边后，要将新的顶点对应的数组值赋值为要将新的顶点对应的数组值赋值为0，即将新顶点加入到集合，即将新顶点加入到集合U。依。依次类推，直到所有的顶点都加入到集合次类推，直到所有的顶点都加入到集合U中。中。10.4图的连通性问题图的连通性问题这个程序中最难理解的是数组这个程序中最难理解的是数组closedge的变化，数组的变化，数组closedge的的adjvex域存放的是每条边的起始点名字，域存放的是每条边的起始点名字，closedge的下标表示每条边的终的下标表示每条边的终结点下标，结点下标，closedge表示边的最小代价。在表示边的最小代价。在MiniSpanTree_PRIM算法中，算法中，先确定集合先确定集合U的元素，即出发顶点，代码如下：的元素，即出发顶点，代码如下：k=LocateVex(G,u);然后对然后对closedge进行初始化，即把初始顶点赋给进行初始化，即把初始顶点赋给closedge的的adjvex域，域，最小代价边赋给最小代价边赋给lowcost域，并将第一个顶点加入域，并将第一个顶点加入U集。例如，当集。例如，当u=a时，时，有有k=0，初始化后，初始化后，closedge数组的值如图数组的值如图10.26(1)所示，代码如下。所示，代码如下。for(j=0;jG.vexnum;+j)/辅助数组初始化辅助数组初始化if(j!=k)strcpy(closedgej.adjvex,u);closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0;/初始时初始时,U=u10.4图的连通性问题图的连通性问题调用函数调用函数MiniNum求代价最小的边，求代价最小的边，k为终结点的序号，例如，为终结点的序号，例如，图图10.24中的无向网中的无向网N第一条代价最小的边为第一条代价最小的边为(a,c)，则有，则有k=2，所，所以以closedge2.adjvex为为a，G.vexs2为为c，输出，输出(a,c)，并将第，并将第k个顶点加入个顶点加入U集。代码如下。集。代码如下。for(i=1;iG.vexnum;+i)/选择其余选择其余G.vexnum-1个顶点个顶点k=MiniNum(closedge,G);/求出求出T的下一个结点：第的下一个结点：第K顶顶点点printf(%s-%s)n,closedgek.adjvex,G.vexsk);/输出生成树的边输出生成树的边closedgek.lowcost=0;/第第K顶点并入顶点并入U集集10.4图的连通性问题图的连通性问题更新更新closedge数组中的数组中的lowcost域，使其为当前状况下边的代价最小，域，使其为当前状况下边的代价最小，代码如下。代码如下。for(j=0;jG.vexnum;+j)if(G.arcskj.adjclosedgej.lowcost)/新顶点并入新顶点并入U集后重新选择最小边集后重新选择最小边strcpy(closedgej.adjvex,G.vexsk);closedgej.lowcost=G.arcskj.adj;10.4图的连通性问题图的连通性问题数组数组closedge的的adjvex域和域和lowcost域的变化情况如图域的变化情况如图10.26所示。所示。10.4图的连通性问题图的连通性问题2克鲁斯卡尔算法克鲁斯卡尔算法克鲁斯卡尔算法从另一途径求网的最小生成树，连通网为克鲁斯卡尔算法从另一途径求网的最小生成树，连通网为N=V,E，则令最小生成树的初始状态为只有，则令最小生成树的初始状态为只有n个顶点而无边的非个顶点而无边的非连通图连通图T=V,，图中每个顶点自成一个连通分量。在，图中每个顶点自成一个连通分量。在E中选择代中选择代价最小的边，若该边依附的顶点落在价最小的边，若该边依附的顶点落在T中不同的连通分量中，则将此中不同的连通分量中，则将此边加入到边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，中，否则舍去此边而选择下一条代价最小的边。依次类推，直至直至T中所有顶点都在同一连通分量上为止。中所有顶点都在同一连通分量上为止。例如，图例如，图10.24所示的无向图所示的无向图N利用卡鲁斯卡尔算法构造最小生利用卡鲁斯卡尔算法构造最小生成树的过程如图成树的过程如图10.27所示。所示。10.5有向无环图有向无环图10.5.1 AOV网与拓扑排序1什么是什么是AOV网网几乎所有的工程都可分为若干个称为活动的子工程，而这些子工几乎所有的工程都可分为若干个称为活动的子工程，而这些子工程之间，通常受一些条件的制约，如某些子工程的开始必须在另一程之间，通常受一些条件的制约，如某些子工程的开始必须在另一些子工程完成之后才能进行。若用图的顶点表示活动，用弧表示活些子工程完成之后才能进行。若用图的顶点表示活动，用弧表示活动之间的优先关系的有向无环图称为动之间的优先关系的有向无环图称为AOV网（网（activityonvertexnetwork），即顶点表示活动的网。），即顶点表示活动的网。在在AOV网中，若从顶点网中，若从顶点vi到顶点到顶点vj之间存在一条有向路径，则顶之间存在一条有向路径，则顶点点vi是顶点是顶点vj的前驱，顶点的前驱，顶点vj为顶点为顶点vi的后继。若的后继。若是有向网是有向网的一条弧，则称顶点的一条弧，则称顶点vi是顶点是顶点vj的直接前驱，顶点的直接前驱，顶点vj是顶点是顶点vi的直接的直接后继。后继。10.5有向无环图有向无环图例如，一个软件工程专业的学生必须修完一系列基本课程才能毕例如，一个软件工程专业的学生必须修完一系列基本课程才能毕业，其中有些课程是基础课，它独立于其他课程，如高等数学，业，其中有些课程是基础课，它独立于其他课程，如高等数学，而另一些课程必须在学完它的基础先修课程才能开始，如在学习完而另一些课程必须在学完它的基础先修课程才能开始，如在学习完程序设计基础和离散数学之后才能开始学习数据结构。程序设计基础和离散数学之后才能开始学习数据结构。这些先决条件定义了课程之间的优先次序。软件专业的课程及先决这些先决条件定义了课程之间的优先次序。软件专业的课程及先决条件如表条件如表10.2所示。所示。 表10.2 软件工程专业课程关系表10.5有向无环图有向无环图这这些些课课程程之之间间的的关关系系用用有有向向图图可可以以更更清清楚楚的的表表示示，如如图图10.28所所示。图中的弧表示课程之间的制约关系。示。图中的弧表示课程之间的制约关系。10.5有向无环图有向无环图2拓扑排序拓扑排序拓扑排序的方法如下：拓扑排序的方法如下：（1）在有向图中任意选择一个没有前驱的顶点即顶点入度为零，将该顶点）在有向图中任意选择一个没有前驱的顶点即顶点入度为零，将该顶点输出；输出；（2）从图中删除该顶点和所有以它为尾的弧；）从图中删除该顶点和所有以它为尾的弧；（3）重复执行步骤（）重复执行步骤（1）和（）和（2），直至所有顶点均已被输出，或者当前），直至所有顶点均已被输出，或者当前图中不存在无前驱的顶点为止（说明有向图中存在环）。图中不存在无前驱的顶点为止（说明有向图中存在环）。按照以上方法，可得到图按照以上方法，可得到图10.28所示的有向图的两个拓扑序列所示的有向图的两个拓扑序列(当然还可当然还可构造其他的拓扑序列构造其他的拓扑序列)为：为：(C1,C6,C10,C7,C2,C3,C4,C5,C8,C9)和和(C2,C1,C3,C4,C5,C9,C10,C6,C7,C8)图图10.29是展示了一个完整的拓扑序列的构造过程。其拓扑序列为：是展示了一个完整的拓扑序列的构造过程。其拓扑序列为：V1、V2、V4、V3、V5、V6。10.5有向无环图有向无环图10.5.2 AOE网与关键路径AOV网描述了活动之间的优先关系，是一个定性的研究，而网描述了活动之间的优先关系，是一个定性的研究，而AOE网就是一个定量的研究。如整个工程的最短完成时间、各个子网就是一个定量的研究。如整个工程的最短完成时间、各个子工程影响整个工程的程度、每个子工程的最短完成时间和最长完成工程影响整个工程的程度、每个子工程的最短完成时间和最长完成时间，都需要利用时间，都需要利用AOE网的相关知识来解决，通过研究事件与活动网的相关知识来解决，通过研究事件与活动之间的关系，从而可以确定整个工程的最短完成时间，明确活动之之间的关系，从而可以确定整个工程的最短完成时间，明确活动之间的相互影响，确保整个工程的顺利进行。间的相互影响，确保整个工程的顺利进行。1什么是什么是AOE网网AOE网（网（activityonedge）即边表示活动的网。）即边表示活动的网。AOE网是一网是一个带权的有向无环图，其中，顶点表示事件（个带权的有向无环图，其中，顶点表示事件（event），弧表示活），弧表示活动，权表示活动持续的时间，权值表示子工程的活动需要的时间。动，权表示活动持续的时间，权值表示子工程的活动需要的时间。通常，可用通常，可用AOE网估算工程的完成时间。网估算工程的完成时间。10.5有向无环图有向无环图图图10.30是是一一个个具具有有11个个活活动动的的AOE网网，其其中中v1，v2，v9表表示示9个个事事件件，表表示示11个个活活动动，a1，a2，a11表表示示活活动动的的执执行行时时间间。进进入入顶顶点点的的有有向向弧弧表表示示的的活活动动已已经经完完成成，从从顶顶点点出出发发的的有有向向弧弧表表示示的的活活动动可可以以开开始始。顶顶点点v1表表示示整整个个工工程程的的开开始始，v9表表示示整整个个工工程程的的结结束束。顶顶点点v5表表示示活活动动a4、a5已已经经完完成成，活活动动a7和和a8可可以以开开始始。完完成成活活动动a1和和活活动动a2分分别别需需要要6天和天和4天。天。10.5有向无环图有向无环图2关键路径关键路径AOE网需要研究的问题是：（网需要研究的问题是：（1）完成整个工程至少需要多少时）完成整个工程至少需要多少时间？（间？（2）哪些活动是影响工程进度的关键？）哪些活动是影响工程进度的关键？由于在由于在AOE网中有些活动可以并行进行，所以完成工程的最短网中有些活动可以并行进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度，这里所说的路径长度时间是从开始点到完成点的最长路径的长度，这里所说的路径长度是指路径上各个活动持续时间之和。最长的路径就是关键路径是指路径上各个活动持续时间之和。最长的路径就是关键路径（criticalpath）。）。在在AOE网中，有些活动是可以并行执行的，关键路径其实就是网中，有些活动是可以并行执行的，关键路径其实就是完成工程的最短时间所经过的路径。关键路径表示了完成工程的最完成工程的最短时间所经过的路径。关键路径表示了完成工程的最短工期。短工期。10.5有向无环图有向无环图（1）事件）事件vi的最早发生时间的最早发生时间ve(i)：从源点到顶点：从源点到顶点vi的最长路径长的最长路径长度，称为事件度，称为事件vi的最早发生时间，记作的最早发生时间，记作ve(i)。求解。求解ve(i)可以从源点可以从源点ve(0)=0开始，按照拓扑排序规则根据递推得到：开始，按照拓扑排序规则根据递推得到：ve(i)=Maxve(k)+dut()|T,1in-1其中，其中，T是所有以第是所有以第i个顶点为弧头的弧的集合，个顶点为弧头的弧的集合，dut()表表示弧示弧对应的活动的持续时间。例如，已知对应的活动的持续时间。例如，已知v2的最早发生时间的最早发生时间为为ve(2)=6，v3的最早发生时间为的最早发生时间为ve(3)=4，活动，活动a4和和a5的持续时的持续时间为间为1，故，故v5的最早发生时间为的最早发生时间为ve(5)=Max(6+1,4+1)=7。如图。如图10.31所示。所示。10.5有向无环图有向无环图（2）事件）事件vi的最晚发生时间的最晚发生时间vl(i)：在保证整个工程正常完成的前：在保证整个工程正常完成的前提下，活动的最迟开始时间，记作提下，活动的最迟开始时间，记作vl(i)。在求解事件。在求解事件vi的最早发生的最早发生时间时间ve(i)的前提的前提vl(n-1)=ve(n-1)下，从汇点开始，向源点推进得下，从汇点开始，向源点推进得到到vl(i)：vl(i)=Minvl(k)-dut()|S,0in-2其中，其中，S是所有以第是所有以第i个顶点为弧尾的弧的集合，个顶点为弧尾的弧的集合，dut()表示表示弧弧对应的活动的持续时间。对应的活动的持续时间。（3）活动）活动ai的最早开始时间的最早开始时间e(i)：如果弧：如果弧表示活动表示活动ai，当事件当事件vk发生之后，活动发生之后，活动ai才开始。因此，事件才开始。因此，事件vk的最早发生时间的最早发生时间也就是活动也就是活动ai的最早开始时间，即的最早开始时间，即e(i)=ve(k)。10.5有向无环图有向无环图（4）活活动动ai的的最最晚晚开开始始时时间间l(i)：在在不不推推迟迟整整个个工工程程完完成成时时间间的的基基础础上上，活活动动ai最最迟迟必必须须开开始始的的时时间间。如如果果弧弧表表示示活活动动ai，持持续续时时间间为为dut()，则则活活动动ai的的最最晚晚开开始始时时间间l(i)=vl(j)-dut()。例例如如，因因事事件件v8的的最最晚晚开开始始时时间间为为14，活活动动a8的的持持续时间为续时间为7，所以，所以a8的最晚开始时间为的最晚开始时间为14-7=7。如图。如图10.32所示。所示。（5）活活动动ai的的松松弛弛时时间间：活活动动ai的的最最晚晚开开始始时时间间与与最最早早开开始始时时间间之差就是活动之差就是活动ai的松弛时间，记作的松弛时间，记作l(i)-e(i)。10.5有向无环图有向无环图求关键路径的算法如下：求关键路径的算法如下：（1）对网中的顶点进行拓扑排序，如果得到的拓扑序列顶点个数）对网中的顶点进行拓扑排序，如果得到的拓扑序列顶点个数小于网中顶点数，则说明网中有环存在，不能求关键路径，终止算小于网中顶点数，则说明网中有环存在，不能求关键路径，终止算法。否则，从源点法。否则，从源点v0开始，求出各个顶点的最早发生时间开始，求出各个顶点的最早发生时间ve(i)。（2）从汇点）从汇点vn出发出发vl(n-1)=ve(n-1)，按照逆拓扑序列求其它顶，按照逆拓扑序列求其它顶点的最晚发生时间点的最晚发生时间vl(i)。（3）由各顶点的最早发生时间）由各顶点的最早发生时间ve(i)和最晚发生时间和最晚发生时间vl(i)，求出每，求出每个活动个活动ai的最早开始时间的最早开始时间e(i)和最晚开始时间和最晚开始时间l(i)。（4）找出所有满足条件）找出所有满足条件e(i)=l(i)的活动的活动ai，ai即是关键活动。即是关键活动。10.5有向无环图有向无环图利利用用AOE网网的的关关键键路路径径算算法法，图图10.30中中的的网网中中顶顶点点对对应应事事件件最最早早发发生生时时间间ve、最最晚晚发发生生时时间间vl及及弧弧对对应应活活动动最最早早发发生生时时间间e、最最晚晚发生时间如图发生时间如图10.33所示。所示。10.5有向无环图有向无环图关关键键路路径径经经过过的的顶顶点点是是满满足足条条件件ve(i)=vl(i)，即即当当事事件件的的最最早早发发生生时时间间与与最最晚晚发发生生时时间间相相等等时时，该该顶顶点点一一定定在在关关键键路路径径之之上上。同同样样，关关键键活活动动者者的的弧弧满满足足条条件件e(i)=l(i)，即即当当活活动动的的最最早早开开始始时时间间与与最最晚晚开开始始时时间间相相等等时时，该该活活动动一一定定是是关关键键活活动动。因因此此，要要求求关关键键路路径径，需需要要首首先先求求出出网网中中每每个个顶顶点点的的对对应应事事件件的的最最早早开开始始时时间间，然然后后再再推推出出事事件件的的最最晚晚开开始始时时间间和和活活动动的的最最早早、最最晚晚开开始始时时间间，最最后后再判断顶点是否在关键路径之上，得到网的关键路径。再判断顶点是否在关键路径之上，得到网的关键路径。10.5有向无环图有向无环图10.5.3 关键路径应用举例【例【例10_5】编写算法，创建如图】编写算法，创建如图10.30所示的所示的AOE网，并求网网，并求网中顶点的拓扑序列和有向网的关键路径。中顶点的拓扑序列和有向网的关键路径。分析：主要考察有向网的拓扑排序和关键路径的计算。先计算出分析：主要考察有向网的拓扑排序和关键路径的计算。先计算出顶点对应事件的最早发生时间顶点对应事件的最早发生时间vei，然后由，然后由vei和顶点的逆拓扑和顶点的逆拓扑序列得到其它参数，最后得到关键路径。序列得到其它参数，最后得到关键路径。10.6最短路径最短路径10.6.1 从某个顶点到其余各顶点的最短路径1迪杰斯特拉算法迪杰斯特拉算法-从某个顶点到其余顶点的最短路径从某个顶点到其余顶点的最短路径带权有向图带权有向图G7从从v0出发到其它各个顶点的最短路径如图出发到其它各个顶点的最短路径如图10.35所示。所示。10.6最短路径最短路径如何求得这些路径呢？伟大的计算机科学家迪杰斯特拉如何求得这些路径呢？伟大的计算机科学家迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序求最短路径算法。）提出了一个按路径长度递增的次序求最短路径算法。它的基本思想是根据路径长度递增求解从顶点它的基本思想是根据路径长度递增求解从顶点v0到其它各顶点的最到其它各顶点的最短路径。短路径。设有一个带权有向图设有一个带权有向图D=(V,E)，定义一个数组，定义一个数组dist，数组中的每，数组中的每个元素个元素disti表示顶点表示顶点v0到顶点到顶点vi的最短路径长度。则长度为的最短路径长度。则长度为distj=Mindisti|viV的路径表示从顶点的路径表示从顶点v0出发到顶点出发到顶点vj的最短路径。也就是说，在所的最短路径。也就是说，在所有的顶点有的顶点v0到顶点到顶点vj的路径中，的路径中，distj是最短的一条路径。而数组是最短的一条路径。而数组dist的初始状态是：如果从顶点的初始状态是：如果从顶点v0到顶点到顶点vi存在弧，则存在弧，则disti是弧是弧的权值；否则，的权值；否则，disti的值为的值为。10.6最短路径最短路径假设假设S表示求出的最短路径对应终点的集合。在按递增次序已经表示求出的最短路径对应终点的集合。在按递增次序已经求出从顶点求出从顶点v0出发到顶点出发到顶点vj的最短路径之后，那么下一条最短路径，的最短路径之后，那么下一条最短路径，即从顶点即从顶点v0到顶点到顶点vk的最短路径或者是弧的最短路径或者是弧，或者是经过集，或者是经过集合合S中某个顶点然后到达顶点中某个顶点然后到达顶点vk的路径。从顶点的路径。从顶点v0出发到顶点出发到顶点vk的最的最短路径长度或者是弧短路径长度或者是弧的权值，或者是的权值，或者是distj与与vj到到vk的权的权值之和。值之和。求最短路径长度满足：终点为求最短路径长度满足：终点为vx的最短路径或者是弧的最短路径或者是弧，或者是中间经过集合或者是中间经过集合S中某个顶点然后到达顶点中某个顶点然后到达顶点vx的所经过的路径。的所经过的路径。下面用反证法证明此结论。假设该最短路径有一个顶点下面用反证法证明此结论。假设该最短路径有一个顶点vzS，则最短，则最短路径为路径为(v0,vz,vx)。但是，这种情况是不可能出现的。因为最。但是，这种情况是不可能出现的。因为最短路径是按照路径长度的递增顺序产生的，所以长度更短的路径已短路径是按照路径长度的递增顺序产生的，所以长度更短的路径已经出现，其终点一定在集合经出现，其终点一定在集合S中。因此假设不成立，结论得证。中。因此假设不成立，结论得证。10.6最短路径最短路径例如，从图例如，从图10.35可以看出，可以看出，(v0,v4)是从是从v0到到v4的最短路径，的最短路径，(v0,v4,v3)是从是从v0到到v3的最短路径，经过了顶点的最短路径，经过了顶点v4；(v0,v4,v3,v5)是从是从v0到到v5的最短路径，经过了顶点的最短路径，经过了顶点v3。因此，在一般情况下，下一条最短路径的长度一定是因此，在一般情况下，下一条最短路径的长度一定是distj=Mindisti|viV-S其中，其中，disti或者是弧或者是弧上的权值，或者是上的权值，或者是distk(vkS)与弧与弧的权值之和。的权值之和。10.6最短路径最短路径根据以上分析，可以得到如下描述的算法。根据以上分析，可以得到如下描述的算法。（1）假设用带权的邻接矩阵）假设用带权的邻接矩阵arc表示带权的有向图，表示带权的有向图，arcij表示弧表示弧上的权值。若上的权值。若不存在，则置不存在，则置arcij为为。S为已找到从为已找到从v出发的最短路径的终点的集合，初始时，出发的最短路径的终点的集合，初始时，S只包括源点只包括源点v0，即，即S=v0，V-S包括除包括除v0以外的图中的其它顶点。以外的图中的其它顶点。v0到其它顶点的路径初始化为到其它顶点的路径初始化为disti=G.arc0i.adj。（2）选择距离顶点）选择距离顶点vi最短的顶点最短的顶点vj，使得，使得distj=Mindisti|viV-Sdistj表示从表示从v0到到vj最短路径长度，最短路径长度，vj表示对应的终点。表示对应的终点。（3）修改从）修改从v0到到顶点到到顶点vi的最短路径长度，其中的最短路径长度，其中viS。如果有。如果有distk+G.arckidisti，则修改，则修改disti，使得，使得disti=distk+G.arcki.adj。（4）重复执行（）重复执行（2）和（）和（3），直到求出所有从），直到求出所有从v0到其它顶点的最短路径长到其它顶点的最短路径长度。度。10.6最短路径最短路径利利用用以以上上迪迪杰杰斯斯特特拉拉算算法法求求最最短短路路径径的的思思想想，图图10.35所所示示图图G7的的带带权权邻邻接接矩矩阵阵和和从从顶顶点点v0到到其其它它顶顶点点的的最最短短路路径径求求解解过过程程如如图图10.36所示。所示。10.6最短路径最短路径【例例10_6】创创建建一一个个如如图图10.35所所示示的的有有向向网网N，输输出出该该有有向向网网N中从中从v0开始到其它各顶点的最短路径及最短路径长度。开始到其它各顶点的最短路径及最短路径长度。10.6最短路径最短路径10.6.2 10.6.2 每一对顶点之间的最短路径每一对顶点之间的最短路径如果要计算每一对顶点之间的最短路径，需每次以一个顶点为出如果要计算每一对顶点之间的最短路径，需每次以一个顶点为出发点，将迪杰斯特拉算法重复执行发点，将迪杰斯特拉算法重复执行n次，就可以得到每一对顶点的最次，就可以得到每一对顶点的最短路径。总的时间复杂度为短路径。总的时间复杂度为O(n3)。下面介绍由另一位伟大的计算。下面介绍由另一位伟大的计算机科学家弗洛伊德（机科学家弗洛伊德（Floyd）提出的另一个算法，其时间复杂度也是）提出的另一个算法，其时间复杂度也是O(n3)，但形式简单些。，但形式简单些。10.6最短路径最短路径1各个顶点之间的最短路径算法思想各个顶点之间的最短路径算法思想弗洛伊德算法的思想是：弗洛伊德算法的思想是：假设求顶点假设求顶点vi到顶点到顶点vj的最短路径。如果从顶点的最短路径。如果从顶点vi到顶点到顶点vj有弧，有弧，则从则从vi到到vj存在一条长度为存在一条长度为arcij的路径，但该路径不一定是的路径，但该路径不一定是vi到到vj的最短路径，还需进行的最短路径，还需进行n次试探。首先需要从顶点次试探。首先需要从顶点v0开始，如果有开始，如果有路径路径(vi,v0,vj)存在，则比较路径存在，则比较路径(vi,vj)和和(vi,v0,vj)，选择两者中最，选择两者中最短的一个且中间顶点的序号不大于短的一个且中间顶点的序号不大于0的最短路径。的最短路径。10.6最短路径最短路径假假如如在在路路径径上上再再增增加加一一个个顶顶点点v1，也也就就是是说说，如如图图(vi,v1)和和(v1,vj)分分别别是是当当前前找找到到的的中中间间顶顶点点的的序序号号不不大大于于0的的最最短短路路径径，那那么么(vi,v1,vj)就就有有可可能能是是从从vi到到vj的的中中间间顶顶点点的的序序号号不不大大于于1的的最最短短路路径径。把把它它和和已已经经得得到到的的从从vi到到vj中中间间顶顶点点序序号号不不大大于于0的的最最短短路路径径相相比比较较，从从中中选选择择中中间间顶顶点点的的序序号号不不大大于于1的的最最短短路路径径之之后后，在增加在增加1个顶点个顶点v2，继续进行试探。，继续进行试探。10.6最短路径最短路径依次类推，在一般情况下，若依次类推，在一般情况下，若(vi,vk)和和(vk,vj)分别是从分别是从vi到到vk和从和从vk到到vj的中间顶点的序号不大于的中间顶点的序号不大于k-1的最短路径，则将的最短路径，则将(vi,vk,vj)和已经得到的从和已经得到的从vi到到vj且中间顶点序号不大于且中间顶点序号不大于k-1的的最短路径相比较，其长度较短者就是从最短路径相比较，其长度较短者就是从vi到到vj的中间顶点的序号不大的中间顶点的序号不大于于k的最短路径。经过的最短路径。经过n次比较，可以得到从次比较，可以得到从vi到到vj的中间顶点序号的中间顶点序号不大于不大于n-1的最短路径。依照这种方法，可以得到各个顶点之间的最的最短路径。依照这种方法，可以得到各个顶点之间的最短路径。短路径。假设采用邻接矩阵存储带权有向图假设采用邻接矩阵存储带权有向图G，则各个顶点之间的最短路则各个顶点之间的最短路径可以保存咋一个径可以保存咋一个n阶方阵阶方阵D中，中，10.6最短路径最短路径根根据据弗弗洛洛伊伊德德算算法法，图图10.38所所示示的的带带权权有有向向图图G8的的每每一一对对顶顶点点之间的最短路径之间的最短路径P和最短路径长度和最短路径长度D求解过程如图求解过程如图10.39所示。所示。10.6最短路径最短路径10.6.3 最短路径应用举例带权图（权值非负，表示边连接的两个顶点间的距离）的最短路带权图（权值非负，表示边连接的两个顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决问题的方法：初始顶点到目标顶点之间存在路径，现有一种解决问题的方法：（1）设最短路径初始时仅包含初始顶点，令当前顶点）设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；为初始顶点；（2）选择离）选择离u最近且尚未在最短路径中的一个顶点最近且尚未在最短路径中的一个顶点v，加入到最短，加入到最短路径中，修改当前顶点路径中，修改当前顶点u=v；（3）重复执行步骤（）重复执行步骤（1）和（）和（2），直到），直到u是目标顶点为止。是目标顶点为止。请问上述方法能否求得最短路径？若该方法可行，请证明之；否请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，举例说明。则，举例说明。【分析】该题目是【分析】该题目是2009年的考研题，主要考察最短路径的掌握情年的考研题，主要考察最短路径的掌握情况。上述方法不一定能求出最短路径。例如，下图中：况。上述方法不一定能求出最短路径。例如，下图中：10.7图的应用举例图的应用举例【例【例10_7】有一个邻接表存储的图】有一个邻接表存储的图G，分别设计实现以下要求的算，分别设计实现以下要求的算法：法：（1）求出图）求出图G中每个顶点的出度；中每个顶点的出度；（2）求出图）求出图G中出度最大的一个顶点，输出该顶点的编号；中出度最大的一个顶点，输出该顶点的编号；（3）计算图）计算图G中出度为零的顶点数；中出度为零的顶点数；（4）判断图）判断图G中是否存在边中是否存在边。分析：主要考察大家对图的邻接表存储特点和基本操作掌握情况。分析：主要考察大家对图的邻接表存储特点和基本操作掌握情况。从图的表头结点出发，依次访问边表结点，并进行计数，就可得到从图的表头结点出发，依次访问边表结点，并进行计数，就可得到相应每个顶点的出度。问题（相应每个顶点的出度。问题（1）、（）、（2）、（）、（3）可归结为一个问）可归结为一个问题，其中求某个顶点的出度可以写成一个函数题，其中求某个顶点的出度可以写成一个函数OutDegree(AdjGraphG,intv)，在求（，在求（1）、（）、（2）、（）、（3）的问）的问题时，可调用该函数实现。题时，可调用该函数实现。10.7图的应用举例图的应用举例【例【例10_8】设计一个算法，判断无向图】设计一个算法，判断无向图G是否为一棵树。是否为一棵树。【分析】一个无向图【分析】一个无向图G是一棵树的条件是：是一棵树的条件是：G必须是无回路的连通必须是无回路的连通图或是有图或是有n-1条边的连通图，这里我们采用后者作为判断条件。条边的连通图，这里我们采用后者作为判断条件。10.8小结小结图中元素之间是一种多对多的关系。图中元素之间是一种多对多的关系。图由顶点和边（弧）构成，根据边的有向和无向可以将图分为两种：有图由顶点和边（弧）构成，根据边的有向和无向可以将图分为两种：有向图和无向图。将带权的有向图称为有向网，带权的无向图称为无向网。向图和无向图。将带权的有向图称为有向网，带权的无向图称为无向网。图的存储结构有图的存储结构有4种：邻接矩阵存储结构、邻接表存储结构、十字链表存种：邻接矩阵存储结构、邻接表存储结构、十字链表存储结构和邻接多重表存储结构。储结构和邻接多重表存储结构。图的遍历分为两种：广度优先搜索和深度优先搜索。图的广度优先搜索图的遍历分为两种：广度优先搜索和深度优先搜索。图的广度优先搜索遍历类似于树的层次遍历，图的深度优先搜索遍历类似于树的先根遍历。遍历类似于树的层次遍历，图的深度优先搜索遍历类似于树的先根遍历。一个连通图的生成树是指一个极小连通子图，假设图中有一个连通图的生成树是指一个极小连通子图，假设图中有n个顶点，则它个顶点，则它包含图中包含图中n个顶点和构成一棵树的个顶点和构成一棵树的n-1条边。条边。构造最小生成树的算法主要有两个：普里姆算法和库鲁斯卡尔算法。构造最小生成树的算法主要有两个：普里姆算法和库鲁斯卡尔算法。关键路径是指路径最长的路径，关键路径表示了完成工程的最短工期。关关键路径是指路径最长的路径，关键路径表示了完成工程的最短工期。关键路径的活动称为关键活动，关键活动可以决定整个工程完成任务的日期。键路径的活动称为关键活动，关键活动可以决定整个工程完成任务的日期。非关键活动不能决定工程的进度。非关键活动不能决定工程的进度。最短路径是指从一个顶点到另一个顶点路径长度最小的一条路径。最短最短路径是指从一个顶点到另一个顶点路径长度最小的一条路径。最短路径的算法主要有两个：迪杰斯特拉算法和弗洛伊德算法。路径的算法主要有两个：迪杰斯特拉算法和弗洛伊德算法。