《数据结构第7章最新图.ppt》由会员分享，可在线阅读，更多相关《数据结构第7章最新图.ppt（125页珍藏版）》请在金锄头文库上搜索。
1、第第7章章图图第第7章章图图7.1图的定义与基本术语图的定义与基本术语7.2图的存储结构图的存储结构7.3图的遍历图的遍历7.4图的连通性问题图的连通性问题7.5有向无环图的应用有向无环图的应用7.6最短路径最短路径第第7章章图图图是一种较线性表和树更为复杂的数据结构。图是一种较线性表和树更为复杂的数据结构。线线性性结结构构是是研研究究数数据据元元素素之之间间的的一一对对一一关关系系。在在这这种种结结构构中中，除除第第一一个个和和最最后后一一个个元元素素外外，任任何何一个元素都有一个元素都有唯一的一个直接前驱和直接后继唯一的一个直接前驱和直接后继。树树结结构构是是研研究究数数据据元元素素之之间
2、间的的一一对对多多的的关关系系。在在这这种种结结构构中中，每每个个元元素素对对下下(层层)可可以以有有0个个或或多多个个元元素素相相联联系系，对对上上(层层)只只有有唯唯一一的的一一个个元元素素相相关关，数据元素之间有明显的层次关系。数据元素之间有明显的层次关系。第第7章章图图图图结结构构是是研研究究数数据据元元素素之之间间的的多多对对多多的的关关系系。在在这这种种结结构构中中，任任意意两两个个元元素素之之间间可可能能存存在在关关系系。即即结结点点之之间间的的关关系系可可以以是是任任意意的的，图图中中任任意意元元素素之之间间都都可可能能相相关关。图图的的应应用用极极为为广广泛泛，已已渗渗入入到
3、到诸诸如如语语言言学学、逻逻辑辑学学、物物理理、化化学学、电电讯讯、计计算算机机科科学学以以及及数数学学的的其其它它分分支支。因此十分重要。因此十分重要。第第7章章图图1.图的定义图的定义G1=G1=V1=vV1=v0 0 ,v ,v1 1,v,v2 2,v,v3 3,v,v4 4 E1=(vE1=(v0 0,v,v1 1),(v),(v0 0,v,v3 3),(v),(v1 1,v,v2 2),(v),(v1 1,v,v4 4),(v),(v2 2,v,v3 3)(v)(v2 2,v,v4 4)图图G由两个集合构成，记作由两个集合构成，记作G=其中其中:V（vertex）是）是顶点顶点的非空
4、有限集合的非空有限集合E（edge）是）是边边的有限集合，的有限集合，而边是顶点对而边是顶点对的集合。的集合。 V0V0 V4V4 V3V3 V1V1 V2V2第第7章章图图例例1 1 交通图交通图（公路、铁路）（公路、铁路） 顶点：顶点：地点地点 边：边：连接地点的公路连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示；交通图中的有单行道双行道，分别用有向边、无向边表示；例例2 2 电路图电路图 顶点：顶点：元件元件 边：连接元件之间的线路边：连接元件之间的线路例例3 3 通讯线路图通讯线路图 顶点：顶点：地点地点 边：地点间的连线边：地点间的连线例例4 4 各种各种流程图流
5、程图，如产品的生产流程图，如产品的生产流程图 顶点：工序顶点：工序 边：各道工序之间的顺序关系边：各道工序之间的顺序关系图的应用举例图的应用举例第第7章章图图2.图的基本术语图的基本术语弧弧(Arc)：表示两个顶点：表示两个顶点v和和w之间存在关系，用之间存在关系，用顶点偶对顶点偶对表示。通常根据图的顶点偶对将表示。通常根据图的顶点偶对将图分为有向图和无向图。图分为有向图和无向图。有向图有向图(Digraph)：若图的关系集合：若图的关系集合E(G)中，顶中，顶点偶对点偶对的的v和和w之间是有序的，称图之间是有序的，称图G是有是有向图。在有向图中，若向图。在有向图中，若E(G)，表示从，表示从
6、顶点顶点v到顶点到顶点w有一条弧。其中：有一条弧。其中：v称为弧尾称为弧尾(tail)或始点或始点(initialnode)，w称为弧头称为弧头(head)或终点或终点(terminalnode)。无向图无向图(Undigraph)：若图：若图G的关系集合的关系集合E(G)中，中，顶点偶对顶点偶对的的v和和w之间是无序的，称之间是无序的，称G是无是无向图，用向图，用(v,w)表示。表示。第第7章章图图在在无无向向图图中中，用用无无序序对对(v,w) 表表示示v和和w之之间间的的一一条条边边(Edge)，因此，因此，(v,w)和和(w,v)代表的是同一条边。代表的是同一条边。设设有有向向图图G1
7、和和无无向向图图G2，如如图图7.1所所示示，形形式式化化定定义义分分别是：别是：G1=(V1，E1)V1=a,b,c,d,eE1=,，,G2=(V2，E2)V2=a,b,c,dE2=(a,b),(a,c),(a,d),(b,d),(b,c),(c,d)第第7章章图图完完全全无无向向图图：对对于于无无向向图图，若若图图中中顶顶点点数数为为n，用用e表表示示边边的的数数目目，则则e0，n(n-1)/2。具具有有n(n-1)/2条条边边的的无无向向图图称称为为完完全全无无向向图图。完完全全无无向向图图另另外外的的定定义义是是：对对于于无无向向图图G=(V，E)，若若vi ，vjV，当当vi vj时
8、时，有有(vi, vj)E，即即图图中中任任意意两两个个不不同同的的顶顶点点间间都都有有一一条条无无向向边，这样的无向图称为完全无向图。边，这样的无向图称为完全无向图。第第7章章图图完完全全有有向向图图：对对于于有有向向图图，若若图图中中顶顶点点数数为为n，用用e表表示示边边或或者者弧弧的的数数目目，则则e0，n(n-1)。具具有有n(n-1)条边的有向图称为完全有向图。条边的有向图称为完全有向图。完完全全有有向向图图另另外外的的定定义义是是：对对于于有有向向图图G=(V，E)，若若， vi，vj V，当当， vivj时时，有有EE。即即图图中中任任意意两两个个不不同同的的顶顶点点间间都都有有
9、一一条条边边或或者者弧，这样的有向图称为完全有向图。弧，这样的有向图称为完全有向图。v有有很很少少边边或或弧弧(enlogn)的的图图称称为为稀稀疏疏图图，反反之之称称为为稠密图。稠密图。权权(Weight)：与与图图的的边边和和弧弧相相关关的的数数。权权可可以以表表示示从从一个顶点到另一个顶点的距离或耗费。一个顶点到另一个顶点的距离或耗费。第第7章章图图(a)(a)(b)(b)(c)(c) V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2(b)和和(c)是是(a)的子图。的子图。第第7章章图图
10、顶顶点点的的邻邻接接(Adjacent)：对对于于无无向向图图G=(V,E)，若若边边，(v,w)E，则则称称顶顶点点v和和w互互为为邻邻接接点点，即即v和和w相相邻邻接接。边边(v,w)依依附附与与顶顶点点v和和w，或或者者说说边边(v,w)和和顶顶点点v,w相关联。相关联。顶顶点点v的的度度是是和和顶顶点点v相相关关联联的的边边的的数数目目，记记做做TD(v)TD(v) 。对对于于有有向向图图，以以顶顶点点v为为头头的的弧弧的的数数目目称称为为顶顶点点v的的入入度度，记记做做ID(v)ID(v) ，以以V V为为终终点点有有向向边边数数。以以v为为尾尾的的弧弧的的数数目目称称为为顶顶点点的
11、的出出度度，记记做做OD(v)OD(v)，以以V V为为起起点点有有向向边边数数。对对于于有有向向图图, ,一一个个顶顶点点的的度度为为其其出出度度和和入入度之和。度之和。第第7章章图图 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3顶点顶点入度入度 出度出度度度V0123V1101V2112V3112顶点顶点度度V02V13V23V32V42顶点的度顶点的度第第7章章图图一一般般来来说说，如如果果顶顶点点vi的的度度记记做做TD(TD(vi) )，那那么么一一个个有有n n个个顶顶点点，e e条边的图满足如下关系：条边的图满足如下关系：路路径径G G
12、中中的的顶顶点点序序列列v v1 1,v,v2 2, , ,v,vk k, ,若若各各边边(v(vi i,v,vi+1i+1) ) E,E,则则称该序列是从顶点称该序列是从顶点v v1 1到顶点到顶点v vk k的路径；的路径；回路回路若路径的顶点和终点相同，则称回路。若路径的顶点和终点相同，则称回路。简单路径简单路径在一条路径中在一条路径中,若除起点和终点外若除起点和终点外,所有顶点各所有顶点各不相同不相同,则该路径为简单路径；则该路径为简单路径；简单回路简单回路由简单路径组成的回路称为简单回路；由简单路径组成的回路称为简单回路； V0V0 V4V4 V3V3 V1V1 V2V2 V0V0
13、V1V1 V2V2 V3V3图图中中路路径径，回回路路，简简单单路路径径，简简单单回回路路是是否唯一？否唯一？第第7章章图图 非非连连通通图图 连连通通图图 强强连连通通图图 非非强强连连通通图图 V0V0 V1V1 V2V2 V3V3 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4在无（有）向图在无（有）向图G=中，如果两个顶点中，如果两个顶点v和和u之间之间有有路径路径，则称这两个顶点是，则称这两个顶点是连通的连通的，若对，若对任何任何两个顶点两个顶点v、u都存在从都存在从v到到u的路径，
14、则称的路径，则称G是连通图。是连通图。对于有向图，如果对于每一对顶点对于有向图，如果对于每一对顶点v和和w，都存在路径，都存在路径，称为强连通图。称为强连通图。连通图、强连通图连通图、强连通图第第7章章图图连通分量连通分量非非连连通通图图 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4连通分量（有向图中为强连通分量）连通分量（有向图中为强连通分量）无向图无向图G的极大连通子图称为的极大连通子图称为G的连通分量的连通分量极大连通子图意思是：该子图是极大连通子图意思是：该子图是G连通子图，将连通子图，将G的任何不在该子图中的顶点加入，子图不再连通；的任何不在该子图中的顶点加入，子图不再
15、连通；第第7章章图图强连通分量强连通分量 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1有向图有向图D的极大强连通子图称为的极大强连通子图称为D的强连通分量的强连通分量极大强连通子图意思是：该子图是极大强连通子图意思是：该子图是D强连通子图，强连通子图，将将D的任何不在该子图中的顶点加入，子图不再是的任何不在该子图中的顶点加入，子图不再是强连通的；强连通的；第第7章章图图连通图连通图 G1G1G1G1的生成树的生成树 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V
16、2生成树生成树包含无向图包含无向图G所有顶点的的极小连通子图称为所有顶点的的极小连通子图称为G的生成树。的生成树。极小连通子图意思是：该子图是极小连通子图意思是：该子图是G的连通子图，在该子图中删除的连通子图，在该子图中删除任何一条边，子图不再连通。如果加一条边，必然形成回路。任何一条边，子图不再连通。如果加一条边，必然形成回路。若若T是是G的生成树当且仅当的生成树当且仅当T满足如下条件：满足如下条件：T是是G的连通子图的连通子图T包含包含G的所有顶点的所有顶点T中无回路中无回路第第7章章图图 需需要要说说明明的的是是一一棵棵有有n n个个结结点点的的生生成成树树有有且且仅仅有有n-1n-1条
17、条边边，如如果果一一个个图图有有n n个个顶顶点点和和小小于于n-1n-1条条边边，则则必必然然非非连连通通的的。如如果果有有对对于于n-1n-1条条边边，则则必必然然有有环。但是，有环。但是，有n-1n-1条边的图不一定是生成树。条边的图不一定是生成树。第第7章章图图1设无向图的顶点个数为设无向图的顶点个数为n，则该图最多有（，则该图最多有（）条边。）条边。An-1Bn(n-1)/2Cn(n+1)/2D0EN22一个一个n个顶点的连通无向图，其边的个数至少为（个顶点的连通无向图，其边的个数至少为（）。）。An-1BnCn+1Dnlogn；3n个结点的完全有向图含有边的数目（）。个结点的完全有
18、向图含有边的数目（）。An*nn（n）Cn2Dn*（nl）4一个有一个有n个结点的图，最少有（个结点的图，最少有（）个连通分量，最多有（）个连通分量，最多有（）个连通分量。）个连通分量。A0B1Cn-1Dn5在一个无向图中，所有顶点的度数之和等于所有边数（在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（之和的（）倍。）倍。A1/2B2C1D43.3.课堂练习课堂练习第第7章章图图7.2图的存储结构图的存储结构7.2.1邻接矩阵邻接矩阵(数组数组)表示法表示法图图的的邻邻接接矩矩
19、阵阵表表示示法法（AdjacencyMatrix）也也称称作作数数组组表表示示法。它采用法。它采用两个数组两个数组来表示图：来表示图：一一个个是是用用于于存存储储顶顶点点信信息息的的一一维维数数组组；另另一一个个是是用用于于存存储储图图中中顶顶点点之之间间关关联联关关系系的的二二维维数数组组，这这个个关关联联关关系系数数组组被被称称为为邻接矩阵邻接矩阵。若图若图G是一个具有是一个具有n个顶点的无权图，个顶点的无权图，G的邻接矩阵是具有的邻接矩阵是具有如下性质的如下性质的nn矩阵矩阵A：若若或或(vi,vj)VR反之反之第第7章章图图图图7.6图图G1、G2的邻接矩阵的邻接矩阵011000000
20、0011000A1=0101010101010111010001100A2=若图若图G是一个有是一个有n个顶点的网，则它的邻接矩阵是具有如下个顶点的网，则它的邻接矩阵是具有如下性质的性质的nn矩阵矩阵A：若若或或(vi,vj)VR反之反之 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3V0 V1 V2 V3 V4V0 V1 V2 V3第第7章章图图例如：图7.7就是一个有向网N及其邻接矩阵的示例。图图7.7有向网及其邻接矩阵有向网及其邻接矩阵5748956521第第7章章图图邻接矩阵表示法的邻接矩阵表示法的C语言类型描述如下：语言类型描述如下：defi
21、neMAX_VERTEX_NUM10/*最多顶点个数最多顶点个数*/defineINFINITY32768/*表示极大值，表示极大值，即即*/typedefenumDG,DN,UDG,UDNGraphKind;/*图图的的种种类类：DG表表示有向图示有向图,DN表示有向网表示有向网,UDG表示无向图表示无向图,UDN表示无向网表示无向网*/typedefcharVertexType;/*假设顶点数据为字符型假设顶点数据为字符型*/typedefstructArcNodeAdjTypeadj;/*对对于于无无权权图图，用用1或或0表表示示是是否否相相邻邻；对对带带权权图图，则则为权值类型为权值类
22、型*/InfoType*info;该该弧弧相相关关信信息息的的指指针针是是指指一一个个图图中中的的顶顶点点可可以以用用一一个个节节点点表表示示，一一条条弧弧也也可可以以用用一一个个节节点点存存储储，这这个个指指针针指指向向这这个个节节点点，节节点中包含些信息，比如弧两端的端点，弧的权值等点中包含些信息，比如弧两端的端点，弧的权值等ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;第第7章章图图typedefstructVertexType vexsMAX_VERTEX_NUM; /*顶顶点点向向量量*/ArcMatrixarcs;/*邻接矩阵邻接矩阵*
23、/intvexnum,arcnum;/*图的顶点数和弧数图的顶点数和弧数*/GraphKindkind;/*图的种类标志图的种类标志*/MGraph;/*（AdjacencyMatrixGraph）*/第第7章章图图邻接矩阵法的特点如下：邻接矩阵法的特点如下：存存储储空空间间：对对于于无无向向图图而而言言，它它的的邻邻接接矩矩阵阵是是对对称称矩矩阵阵（因因为为若若(vi，vj)E(G)，则则(vj，vi)E(G)），因因此此我我们们可可以以采采用用特特殊殊矩矩阵阵的的压压缩缩存存储储法法，即即只只存存储储其其下下三三角角即即可可，这这样样，一一个个具具有有n个个顶顶点点的的无无向向图图G，它它
24、的的邻邻接接矩矩阵阵需需要要n(n-1)/2个个存存储储空空间间即即可可。但但对对于于有有向向图图而而言言，其其中中的的弧弧是是有有方方向向的的，即即若若E(G)，不不一一定定有有E(G)，因因此此有有向向图图的的邻邻接接矩矩阵阵不不一一定定是是对对称称矩矩阵阵，对对于于有有向向图图的的邻邻接接矩矩阵阵的的存存储储则则需需要要n2个存储空间。个存储空间。第第7章章图图便便于于运运算算：采采用用邻邻接接矩矩阵阵表表示示法法，便便于于判判定定图图中中任任意意两两个个顶顶点点之之间间是是否否有有边边相相连连，即即根根据据Ai,j=0或或1来来判判断断。另另外外还还便便于于求求得得各各个个顶顶点点的的
25、度度。对对于于无无向向图图而而言言，其其邻邻接接矩矩阵阵第第i行行元素之和就是图中第元素之和就是图中第i个顶点的度：个顶点的度：对于有向图而言，其邻接矩阵第对于有向图而言，其邻接矩阵第i行元素之和就是图中第行元素之和就是图中第i个个顶点的出度：顶点的出度：对于有向图而言，其邻接矩阵第对于有向图而言，其邻接矩阵第i列元素之和就是图中第列元素之和就是图中第i个个顶点的入度：顶点的入度：第第7章章图图采采用用邻邻接接矩矩阵阵存存储储法法表表示示图图，很很便便于于实实现现图图的的一一些些基基本本操操作作，如如实实现现访访问问图图G中中v顶顶点点第第一一个个邻邻接接点点的的函函数数FirstAdjVer
26、tex（G，v）可按如下步骤实现：）可按如下步骤实现：(1)首首先先，由由LocateVertex（G，v）找找到到v在在图图中中的的位位置置，即即v在一维数组在一维数组vexs中的序号中的序号i。(2)二二维维数数组组arcs中中第第i行行上上第第一一个个adj域域非非零零的的分分量量所所在在的的列号列号j，便是，便是v的第一个邻接点在图的第一个邻接点在图G中的位置。中的位置。(3)取出一维数组取出一维数组vexsj中的数据信息，即与顶点中的数据信息，即与顶点v邻接的邻接的第一个邻接点的信息。第一个邻接点的信息。对于稀疏图而言，不适于用邻接矩阵来存储，因为这样会对于稀疏图而言，不适于用邻接矩
27、阵来存储，因为这样会造成存储空间的浪费。造成存储空间的浪费。第第7章章图图7.2.2邻接表表示法邻接表表示法图图的的邻邻接接矩矩阵阵表表示示法法(即即图图的的数数组组表表示示法法)，虽虽然然有有其其自自身身的的优优点点，但但对对于于稀稀疏疏图图来来讲讲，用用邻邻接接矩矩阵阵的的表表示示方方法法会会造造成成存存储储空空间间的的很很大大浪浪费费。邻邻接接表表（AdjacencyList）表表示示法法实实际际上上是是图图的的一一种种链链式式存存储储结结构构。它它克克服服了了邻邻接接矩矩阵阵的的弊弊病病，基基本本思思想是想是:（1）对对图图中中每每个个顶顶点点建建立立一一个个单单链链表表，第第i个个单
28、单链链表表中中的的结结点点表示依附于顶点表示依附于顶点i的边，也称之为边表。的边，也称之为边表。（2）每每个个顶顶点点对对应应的的单单链链表表上上附附设设一一个个表表头头结结点点。所所有有的的表表头结点组成了一个表头结点表。头结点组成了一个表头结点表。第第7章章图图(1)表表头头结结点点表表：由由所所有有表表头头结结点点以以顺顺序序结结构构（向向量量）的的形形式式存存储储，以以便便可可以以随随机机访访问问任任一一顶顶点点的的边边链链表表。表表头头结结点点的的结结构构如如图图7.8所所示示。表表头头结结点点由由两两部部分分构构成成，其其中中数数据据域域（data）用用于于存存储储顶顶点点的的名名
29、或或其其它它有有关关信信息息；链链域域（firstarc）用用于于指指向向链链表表中中第第一一个个顶顶点点（即即与与顶顶点点vi邻邻接接的的第一个邻接点）。第一个邻接点）。图图7.8头结点和表结点头结点和表结点datafirstarcadjvexnextarcinfo第第7章章图图图图7.9图的邻接表表示法图的邻接表表示法 A A B B C C D D A A E E D D B B C C第第7章章图图邻接表存储结构的形式化说明如下：邻接表存储结构的形式化说明如下：defineMAX_VERTEX_NUM10/*最多顶点个数最多顶点个数*/typedefenumDG,DN,UDG,UDNG
30、raphKind;/*图的种类图的种类*/typedefstructArcNodeintadjvex;/*该弧指向顶点的位置该弧指向顶点的位置*/structArcNode*nextarc;/*指向下一条弧的指针指向下一条弧的指针*/InfoType*info;/*与该弧相关的信息与该弧相关的信息*/ArcNode;第第7章章图图typedefstructArcNodeintadjvex;/*该弧指向顶点的位置该弧指向顶点的位置*/structArcNode*nextarc;/*指向下一条弧的指针指向下一条弧的指针*/InfoType*info;/*与该弧相关的信息与该弧相关的信息*/ArcN
31、ode;typedefstructVNodeVertexTypedata;/*顶点数据顶点数据*/ArcNode*firstarc;/*指向该顶点第一条弧的指针指向该顶点第一条弧的指针*/Vnode,AdjListMAX_VERTEX_NUM;typedefstructAdjListvertices;intvexnum,arcnum;/*图的顶点数和弧数图的顶点数和弧数*/intkind;/*图的种类标志图的种类标志*/ALGraph;/*基于邻接表的图基于邻接表的图(AdjacencyListGraph)*/第第7章章图图5.建立无向邻接表建立无向邻接表 V0V0 V4V4 V3V3 V1V
32、1 V2V2将图转换为线性输入信息：将图转换为线性输入信息：顶点数为：顶点数为：n=5边数为边数为:e=6边集：边集：010312142324第第7章章图图建立无向邻接表建立无向邻接表思想：如何给存储结构赋值思想：如何给存储结构赋值1.建立顶点数组。读入各顶点数据建立顶点数组。读入各顶点数据data，将，将firstarc域赋域赋NULL。2.建立各顶点的邻接表。读入顶点对建立各顶点的邻接表。读入顶点对,生成两个结点，分生成两个结点，分别插入顶点别插入顶点v,u的邻接表的头部。直至处理完所有的边。的邻接表的头部。直至处理完所有的边。 0 0 1 1 2 2 3 3 4 4m-1m-1V0V0V
33、1V1V2V2V3V3V4V41 13 31 10 01 12 22 20 03 34 42 24 4010312142324第第7章章图图存储空间存储空间对对于于有有n个个顶顶点点，e条条边边的的无无向向图图而而言言，若若采采取取邻邻接接表表作作为为存存储储结结构构，则则需需要要n个个表表头头结结点点和和2e个个边边结结点点。很很显显然然在在边边很很稀稀疏疏（即即e远远小小于于n(n-1)/2时时）的的情情况况下下，用用邻邻接接表表存存储储所所需需的的空间比邻接矩阵所需的空间空间比邻接矩阵所需的空间(n(n-1)/2)要节省得多。要节省得多。无向图的度无向图的度在在无无向向图图的的邻邻接接表
34、表中中，顶顶点点vi的的度度恰恰好好就就是是第第i个个边边链链表表上上结点的个数。结点的个数。第第7章章图图有向图的度有向图的度在在有有向向图图中中，第第i个个边边链链表表上上顶顶点点的的个个数数是是顶顶点点vi的的出出度度，只只需需通通过过表表头头向向量量表表中中找找到到第第i个个顶顶点点的的边边链链表表的的头头指指针针，实实现顺链查找即可。现顺链查找即可。如如要要判判定定任任意意两两个个顶顶点点(vi和和vj)之之间间是是否否有有边边或或弧弧相相连连，则需要搜索所有的边链表，这样比较麻烦。则需要搜索所有的边链表，这样比较麻烦。求求得得第第i个个顶顶点点的的入入度度，也也必必须须遍遍历历整整
35、个个邻邻接接表表，在在所所有有边边链链表表中中查查找找邻邻接接点点域域的的值值为为i的的结结点点并并计计数数求求和和。由由此此可可见见，对对于于用用邻邻接接表表方方式式存存储储的的有有向向图图，求求顶顶点点的的入入度度并并不不方方便便，它需要通过扫描整个邻接表才能得到结果。它需要通过扫描整个邻接表才能得到结果。第第7章章图图一一种种解解决决的的方方法法是是逆逆邻邻接接表表法法，我我们们可可以以对对每每一一顶顶点点vi再再建建立立一一个个逆逆邻邻接接表表，即即对对每每个个顶顶点点vi建建立立一一个个所所有有以以顶顶点点vi为为弧头的弧的表，如图弧头的弧的表，如图7.10所示。所示。图图7.10逆
36、邻接表表示法逆邻接表表示法 1 1 2 2 3 3 4 4第第7章章图图 建建邻邻接接表表时时，若若输输入入的的顶顶点点信信息息即即为为顶顶点点编编号号，(n+e)(n+e)；否则否则(n*e)(n*e)。 在邻接表上在邻接表上容易容易找任何一个顶点的第一个邻接点和下一个邻找任何一个顶点的第一个邻接点和下一个邻接点，接点，但要但要判定任两个顶点之间是否有边或弧，需搜索第判定任两个顶点之间是否有边或弧，需搜索第i i个或个或第第j j个链表，没有邻接矩阵方便。个链表，没有邻接矩阵方便。第第7章章图图课堂练习课堂练习1、已知有向图、已知有向图G，V（G）=1，2，3，4，E（G）=，试画出试画出G
37、的邻接矩阵，并说明，若已知点的邻接矩阵，并说明，若已知点I，如何根据邻接，如何根据邻接矩阵找到与矩阵找到与I相邻的点相邻的点j？2、已知无向图、已知无向图G，V（G）=1，2，3，4，E（G）=（1，2），（），（1，3），（），（2，3），（），（2，4），），（3，4）试画出试画出G的邻接表，并说明，若已知点的邻接表，并说明，若已知点I，如，如何根据邻接表找到与何根据邻接表找到与I相邻的点相邻的点j？第第7章章图图复习复习1、有头结点的单链表、有头结点的单链表4，2，6，5，3，1（1）单链表的建立（头部插入新结点和尾部插入新）单链表的建立（头部插入新结点和尾部插入新结点两种方法）结点两种
38、方法）（2）输出并删除第）输出并删除第i个结点个结点（3）在第）在第i个位置插入新元素个位置插入新元素x第第7章章图图头插法是指将新加入的节点加入到头结点后面。头插法是指将新加入的节点加入到头结点后面。图2.10头插法建立单链表图示第第7章章图图voidCreateList_L(LinkList&L,intn)L=(Linklist)malloc(sizeof(Lnode);L-next=NULL;for(i=n;i0;-i)p=(LinkList)malloc(sizeof(Lnode);scanf(&p-data);p-next=L-next;L-next=p;第第7章章图图新加入的节点插
39、入到表尾新加入的节点插入到表尾。图2.11尾插法建表图示第第7章章图图voidCreateList_L(LinkList&L,intn)L=(Linklist)malloc(sizeof(Lnode);L-next=NULL;LinkListr=L;for(i=n;i0;-i)p=(LinkList)malloc(sizeof(Lnode);scanf(&p-data);r-next=p;r=r-next;p-next=Null;p-next=r-next;r-next=p;r=p;第第7章章图图3.删除删除在链表中删除某元素的示意图如下：在链表中删除某元素的示意图如下：cabp删除步骤（即核
40、心语句）：删除步骤（即核心语句）：q=p-next;/保存保存b的指针，靠它才能指向的指针，靠它才能指向cp-next=q-next;/a、c两结点相连两结点相连free(q)；/删除删除b结点，彻底释放结点，彻底释放p-next思考：思考： 省略省略free(q)语句语句行不行行不行？(p-next)-next第第7章章图图/删除操作删除操作StatusListDelete_L(LinkList&L,inti,Elemtype&e)p=L;j=0;while(p-next&jnext;+j;if(!(p-next)|ji-1)returnERROR;q=p-next;p-next=q-nex
41、t;e=q-data;free(q);returnOK;第第7章章图图在链表中插入一个元素的示意图如下：在链表中插入一个元素的示意图如下：xsbapabp插入步骤（即核心语句）：插入步骤（即核心语句）：Step 1Step 1：s-next=p-next;Step 2Step 2：p-next=s；p-nexts-next元素元素x x结点应预先生成：结点应预先生成：s=(LinkList)malloc(sizeof(LNode)s=(LinkList)malloc(sizeof(LNode); ;s-data=x;s-data=x;s-next=p-next;s-next=p-next;p-
42、next=s;p-next=s;第第7章章图图StatusListInsert_L(LinkList&L,inti,ElmeTypee)p=L;j=0;while(p&jnext;+j;if(!p|ji-1)returnERROR;s=(LinkList)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;returnOK;循循环环执执行行的的结结束束条条件件分分别别是是什什么么？如如果果在在p不不为为空空的的情情况况下下结结束束循循环环，j的的值值为为多多少少？循循环环执执行行了了多多少少次次？P指针指向那个元素？指针指向那个元素？循循环
43、环执执行行的的结结束束条条件件分分别别是是什什么么？P为为空空或或者者j=i-1.如如果果在在p不不为为空空的的情情况况下下结结束束循循环环，j的的值值为为多多少少？为为i-1.循循环环执执行行了了多多少少次次？i-1次次。P指指针针指指向向那那个个元元素素？第第i-1个个元素。元素。第第7章章图图7.2.3十字链表法十字链表法十十字字链链表表(OrthogonalList)(List)是是有有向向图图的的另另一一种种链链式式存存储储结结构构，是是将将有有向向图图的的正正邻邻接接表表和和逆逆邻邻接接表表结合起来得到的一种链表。结合起来得到的一种链表。在在这这种种结结构构中中，每每条条弧弧的的弧
44、弧头头结结点点和和弧弧尾尾结结点点都都存存放放在在链链表表中中，并并将将弧弧结结点点分分别别组组织织到到以以弧弧尾尾结结点点为为头头(顶顶点点)结结点点和和以以弧弧头头结结点点为为头头(顶顶点点)结结点点的的链链表中。表中。第第7章章图图图图7.11图的十字链表弧结点、图的十字链表弧结点、顶点结点结构图顶点结点结构图第第7章章图图图图7.12图图7.1中有向图中有向图G1的十字链表的十字链表 1 1 2 23 3 4 4第第7章章图图可可以以看看到到，弧弧头头相相同同的的弧弧在在同同一一链链表表上上，弧弧尾尾相相同同的的弧弧也也在在同同一一链链表表上上。在在十十字字链链表表中中既既容容易易找找
45、到到以以顶顶点点i i为为尾尾的的弧弧，也也容容易易找找到到以以顶顶点点i i为为头头的的弧弧，易易求求入入度度和和出出度度。建建立立十十字字链表的复杂度同邻接表。链表的复杂度同邻接表。第第7章章图图图的十字链表结构形式化定义如下：图的十字链表结构形式化定义如下：defineMAX_VERTEX_NUM10/*最多顶点个数最多顶点个数*/typedefenumDG,DN,UDG,UDNGraphKind;/*图的种类图的种类*/typedefstructArcBoxinttailvex,headvex;structArcBox*hlink,*tlink;InfoType*info;ArcBox
46、;typedefstructVexNodeVertexTypedata;/*顶点信息顶点信息*/ArcBox*firstin,*firstout;VexNode;typedefstructVexNodexlistMAX_VERTEX_NUM;intvexnum,arcnum;/*图的顶点数和弧数图的顶点数和弧数*/OLGraph;/*图的十字链表表示法图的十字链表表示法(OrthogonalList)*/第第7章章图图7.2.4邻接多重表邻接多重表图图7.13邻接多重表的结点结构邻接多重表的结点结构第第7章章图图邻接多重表的结构类型说明如下：typedefemnuunvisited,visit
47、edVisitIf;typedefstructEBoxVisitIfmark;intivex,jvex;structEbox*ilink,*jlink;InfoType*Info;EBox;typedefstructVerBoxVertexTypedata;Ebox*firstedge;VexBox;typedefstructVexBoxadjmulistMAX_VERTEX_NUM;intvexnum,arcnum;/*图的顶点数和弧数*/AMLGraph;/*基于图的邻接多重表表示法(AdjacencyMulti-list)*/第第7章章图图图图7.14无向图的邻接多重表表示无向图的邻接多
48、重表表示第第7章章图图总结总结图的几种存储结构：邻接矩阵、邻接表、十图的几种存储结构：邻接矩阵、邻接表、十字链表和邻接多重表。每种存储结构都有各自的字链表和邻接多重表。每种存储结构都有各自的优缺点，而其本质区别就是节点里面包含的指针优缺点，而其本质区别就是节点里面包含的指针不同，注意区分。不同，注意区分。第第7章章图图7.3图图的的遍遍历历 从从图图中中某某一一顶顶点点出出发发访访问问图图中中每每一一个个结结点点，且且每每个个顶顶点点仅仅被被访访问问一一次次。图图的的遍遍历历是是图图的的连连通通性性问问题题、拓拓扑扑排排序序、求求关关键键路径等的基础。路径等的基础。图图的的遍遍历历比比起起树树
49、的的遍遍历历要要复复杂杂得得多多。因因为为图图中中顶顶点点关关系系是是任任意意的的，即即图图中中顶顶点点之之间间是是多多对对多多的的关关系系，图图可可能能是是非非连连通通图图，图图中中还还可可能能有有回回路路存存在在，因因此此在在访访问问了了某某个个顶顶点点后后，可可能能沿沿着着某某条条路路径径搜搜索索后后又又回回到到该该顶顶点点上上。为为了了保保证证图图中中的的各各顶顶点点在在遍遍历历过过程程中中访访问问且且仅仅访访问问一一次次，需需要要为为每每个个顶顶点点设设一一个个访访问问标标志志，因因此此我我们们为为图图设设置置一一个个访访问问标标志志数数组组visitedn，用用于于标标示示图图中中
50、每每个个顶顶点点是是否否被被访访问问过过，它它的的初初始始值值为为0(“假假”)，表表示示顶顶点点均均未未被被访访问问；一一旦旦访访问问过过顶顶点点vi，则则置置访访问问标标志志数数组组中中的的visitedi为为1(“真真”)，以表示该顶点已访问。，以表示该顶点已访问。第第7章章图图7.3.1深度优先搜索深度优先搜索深深度度优优先先搜搜索索（Depth-FirstSearch）是是指指按按照照深深度度方方向向搜搜索索，它类似于树的先根遍历，是树的先根遍历的推广。它类似于树的先根遍历，是树的先根遍历的推广。深度优先搜索连通子图的基本思想是：深度优先搜索连通子图的基本思想是：（1）从图中某个顶点
51、从图中某个顶点v0出发，首先访问出发，首先访问v0。（2）找找出出刚刚访访问问过过的的顶顶点点vi的的第第一一个个未未被被访访问问的的邻邻接接点点，然然后后访访问问该该顶顶点点。以以该该顶顶点点为为新新顶顶点点，重重复复本本步步骤骤，直直到到当当前前的的顶顶点没有未被访问的邻接点为止。点没有未被访问的邻接点为止。（3）返返回回前前一一个个访访问问过过的的且且仍仍有有未未被被访访问问的的邻邻接接点点的的顶顶点点，找出并访问该顶点的下一个未被访问的邻接点，然后执行步骤找出并访问该顶点的下一个未被访问的邻接点，然后执行步骤(2)。第第7章章图图采采用用递递归归的的形形式式说说明明，则则深深度度优优先
52、先搜搜索索连连通通子子图图的的基基本本思思想可表示为：想可表示为：（1）访问出发点访问出发点v0。（2）依依次次以以v0的的未未被被访访问问的的邻邻接接点点为为出出发发点点，深深度度优优先先搜搜索图，直至图中所有与索图，直至图中所有与v0有路径相通的顶点都被访问。有路径相通的顶点都被访问。若若此此时时图图中中还还有有顶顶点点未未被被访访问问，则则另另选选图图中中一一个个未未被被访访问问的的顶顶点点作作为为起起始始点点，重重复复上上述述深深度度优优先先搜搜索索过过程程，直直至至图图中中所所有顶点均被访问过为止。有顶点均被访问过为止。图图7.15给给出出了了一一个个深深度度优优先先搜搜索索的的过过
53、程程图图示示，其其中中实实箭箭头头代代表表访访问问方方向向，虚虚箭箭头头代代表表回回溯溯方方向向，箭箭头头旁旁边边的的数数字字代代表表搜搜索顺序，索顺序，A为起始顶点。为起始顶点。第第7章章图图图7.15图的深度优先搜索过程图示第第7章章图图首首先先访访问问A，然然后后按按图图中中序序号号对对应应的的顺顺序序进进行行深深度度优优先先搜搜索索。图中序号对应步骤的解释如下：图中序号对应步骤的解释如下：（1）顶顶点点A的的未未访访邻邻接接点点有有B、E、D，首首先先访访问问A的的第第一一个个未访邻接点未访邻接点B；（2）顶顶点点B的的未未访访邻邻接接点点有有C、E，首首先先访访问问B的的第第一一个个
54、未未访邻接点访邻接点C；（3）顶点顶点C的未访邻接点只有的未访邻接点只有F，访问，访问F；（4）顶点顶点F没有未访邻接点，回溯到没有未访邻接点，回溯到C；（5）顶点顶点C已没有未访邻接点，回溯到已没有未访邻接点，回溯到B；第第7章章图图（6）顶点顶点B的未访邻接点只剩下的未访邻接点只剩下E，访问，访问E；（7）顶点顶点E的未访邻接点只剩下的未访邻接点只剩下G，访问，访问G；（8）顶点顶点G的未访邻接点有的未访邻接点有D、H，首先访问，首先访问G的第一个未访的第一个未访邻接点邻接点D；（9）顶点顶点D没有未访邻接点，回溯到没有未访邻接点，回溯到G；（10）顶点顶点G的未访邻接点只剩下的未访邻接点
55、只剩下H，访问，访问H；（11）顶点顶点H的未访邻接点只有的未访邻接点只有I，访问，访问I；（12）顶点顶点I没有未访邻接点，回溯到没有未访邻接点，回溯到H；（13）顶点顶点H已没有未访邻接点，回溯到已没有未访邻接点，回溯到G；（14）顶点顶点G已没有未访邻接点，回溯到已没有未访邻接点，回溯到E；（15）顶点顶点E已没有未访邻接点，回溯到已没有未访邻接点，回溯到B；（16）顶点顶点B已没有未访邻接点，回溯到已没有未访邻接点，回溯到A。第第7章章图图BooleanvisitedMAX;Status(*visitFunc)(intv);/是对节点元素执行相应的操作是对节点元素执行相应的操作void
56、DFSTraverse(GraphG,Status(*visit)(intv)/*对图对图G进行深度优先搜索，进行深度优先搜索，Graph表示图的一种存储结构表示图的一种存储结构*/VisitFunc=Visit;for(v=0;vG.vexnum;v+)visitedv=False;/*访问标志数组初始化访问标志数组初始化*/for(v=0;v=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/*递归调用递归调用DFS*/*DFS*/第第7章章图图7.3.2广度优先搜索广度优先搜索广广度度优优先先搜搜索索（Breadth-FirstSearch）是是指指
57、照照广广度度方方向向搜搜索索，它它类类似似于于树树的的层层次次遍遍历历，是是树树的的按按层层次次遍遍历历的的推推广广。广广度度优优先先搜索的基本思想是：搜索的基本思想是：（1）从图中某个顶点从图中某个顶点v0出发，首先访问出发，首先访问v0。（2）依次访问依次访问v0的各个未被访问的邻接点。的各个未被访问的邻接点。（3）分分别别从从这这些些邻邻接接点点（端端结结点点）出出发发，依依次次访访问问它它们们的的各各个个未未被被访访问问的的邻邻接接点点（新新的的端端结结点点）。访访问问时时应应保保证证：如如果果vi和和vk为为当当前前端端结结点点，vi在在vk之之前前被被访访问问，则则vi的的所所有有
58、未未被被访访问问的的邻邻接接点点应应在在vk的的所所有有未未被被访访问问的的邻邻接接点点之之前前访访问问。重重复复（3），直直到所有端结点均没有未被访问的邻接点为止。到所有端结点均没有未被访问的邻接点为止。第第7章章图图图7.16图的广度优先搜索过程图示第第7章章图图广度优先搜索连通子图的算法如下：广度优先搜索连通子图的算法如下：voidBFSTraverse(GraphG,Status(*Visit)(intv)/*广度优先搜索图广度优先搜索图G*/for(v=0;vG.vexnum;+v)visitedv=FALSE;InitQueue(Q);/*初始化空队初始化空队*/for(v=0;v
59、=0;w=NextAdjVex(G,u,w)if(!visitedw)Visit(w);visitedw=True;EnQueue(Q,w);/if/while/if/BFSTraverse第第7章章图图分分析析上上述述算算法法，图图中中每每个个顶顶点点至至多多入入队队一一次次，因因此此外外循循环环次次数数为为n。当当图图g采采用用邻邻接接表表方方式式存存储储，则则当当结结点点v出出队队后后，内内循循环环次次数数等等于于结结点点v的的度度。由由于于访访问问所所有有顶顶点点的的邻邻接接点点的的总总的的时时间间复复杂杂度度为为O(d0+d1+d2+dn-1)=O(e)，因因此此图图采采用用邻邻接接
60、表表方方式式存存储储，广广度度优优先先搜搜索索算算法法的的时时间间复复杂杂度度为为O(n+e)；当当图图g采采用用邻邻接接矩矩阵阵方方式式存存储储，由由于于找找每每个个顶顶点点的的邻邻接接点点时时，内内循循环环次数等于次数等于n，因此广度优先搜索算法的时间复杂度为，因此广度优先搜索算法的时间复杂度为O(n2)。第第7章章图图课堂练习课堂练习1无向图无向图G=(V,E),其中：其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行，对该图进行深度优先遍历，得到的顶点序列正确的是（深度优先遍历，得到的顶点序列正确的是（）
61、。）。Aa,b,e,c,d,fBa,c,f,e,b,dCa,e,b,c,f,dDa,e,d,f,c,b第第7章章图图2、设下图如右所示，在下面的、设下图如右所示，在下面的5个序列中，符合个序列中，符合深度优先遍历的序列有多少？（深度优先遍历的序列有多少？（）aebdfcacfdebaedfcbaefdcbaefdbcA5个个B4个个C3个个D2个个第第7章章图图3下面的邻接表表示一个给定的无向图下面的邻接表表示一个给定的无向图（1）给出从顶点）给出从顶点v1开始开始,对图对图G用深度优先搜索法进行遍历用深度优先搜索法进行遍历时的顶点序列；时的顶点序列；（2）给出从顶点）给出从顶点v1开始开始,
62、对图对图G用广度优先搜索法进行遍历用广度优先搜索法进行遍历时的顶点序列。时的顶点序列。第第7章章图图7.4图的连通性问题图的连通性问题7.4.1无向图的连通分量无向图的连通分量图图遍遍历历时时，对对于于连连通通图图，无无论论是是广广度度优优先先搜搜索索还还是是深深度度优优先先搜搜索索，仅仅需需要要调调用用一一次次搜搜索索过过程程，即即从从任任一一个个顶顶点点出出发发，便便可可以以遍遍历历图图中中的的各各个个顶顶点点。对对于于非非连连通通图图，则则需需要要多多次次调调用用搜搜索索过过程程，而而每每次次调调用用得得到到的的顶顶点点访访问问序序列列恰恰为为各各连连通通分分量量中中的的顶顶点点集集。例
63、例如如，图图7.17(a)是是一一个个非非连连通通图图，按按照照它它的的邻邻接接表表进进行行深深度度优优先先搜搜索索遍遍历历，三三次次调调用用DFSTraverse过过程程得得到到的的访访问问顶点序列为：顶点序列为：1，2，4，3，95，6，78，10第第7章章图图图图7.17图及其连通分量图及其连通分量1，2，4，3，95，6，78，10第第7章章图图 设设E(G)E(G)为为连连通通图图G G中中所所有有边边的的集集合合，则则从从图图中中任任一一顶顶点点出出发发遍遍历历图图时时，将将E(G)E(G)分分成成两两个个集集合合T(G)T(G)和和B(G)B(G)。T(G)T(G)为为遍遍历历时
64、时的的边边的的集集合合，B(G)B(G)是是剩剩余余边边的的集集合合。显显然然，T(G)T(G)和和G G中中所所有有顶顶点点一一起起构构成成连连通通图图G G的的极极小小连连通通子子图图，且且为为一一棵棵生生成成树树，按按图图的的遍遍历历方方法法不不同同，分别称为深度优先生成树和广度优先生成树。分别称为深度优先生成树和广度优先生成树。生成树的概念：生成树的概念：若若T是是G的生成树当且仅当的生成树当且仅当T满足如下条件：满足如下条件：T是是G的的连通子图连通子图T包含包含G的的所有顶点所有顶点T中中无回路无回路 对于对于非连通图非连通图，每个，每个连通分量连通分量的顶点集和走过的边集一起构的
65、顶点集和走过的边集一起构成成若干生成树若干生成树，称为，称为生成森林生成森林。 第第7章章图图7.4.2最小生成树最小生成树 假假设设要要在在n n个个城城市市之之间间建建立立通通信信联联络络网网，则则联联通通n n个个城城市市只只需需要要n-1n-1条条线线路路，这这时时自自然然会会考考虑虑这这样样一一个个问问题题，如如何何在在最节省经费的前提下建立这个通信网。最节省经费的前提下建立这个通信网。在在一一个个连连通通网网的的所所有有生生成成树树中中，各各边边的的代代价价之之和和最最小小的的那那棵棵生生成成树树称称为为该该连连通通网网的的最最小小代代价价生生成成树树（MinimumCostSpa
66、nningTree），简简称称为为最最小小生生成成树树(MST)。最最小小生生成树有如下重要性质：成树有如下重要性质：设设N=(V,E)是是一一连连通通网网，U是是顶顶点点集集V的的一一个个非非空空子子集集。若若（u,v）是是一一条条具具有有最最小小权权值值的的边边，其其中中uU，vV-U，则存在一棵包含边（，则存在一棵包含边（u,v）的最小生成树。）的最小生成树。第第7章章图图我们用反证法来证明这个我们用反证法来证明这个MST性质：性质：假假设设不不存存在在这这样样一一棵棵包包含含边边（u,v）的的最最小小生生成成树树。任任取取一一棵棵最最小小生生成成树树T，将将（u,v）加加入入T中中。根
67、根据据树树的的性性质质，此此时时T中中必必形形成成一一个个包包含含（u,v）的的回回路路，且且回回路路中中必必有有一一条条边边（u,v）的的权权值值大大于于或或等等于于（u,v）的的权权值值。删删除除（u,v），则则得得到到一一棵棵代代价价小小于于等等于于T的的生生成成树树T，且且T为为一一棵棵包包含含边边（u,v）的的最最小小生成树。这与假设矛盾，故该性质得证。生成树。这与假设矛盾，故该性质得证。我我们们可可以以利利用用MST性性质质来来生生成成一一个个连连通通网网的的最最小小生生成成树树。普普里里姆姆（Prim）算算法法和和克克鲁鲁斯斯卡卡尔尔（Kruskal）算算法法便便是是利利用用了这
68、个性质。了这个性质。第第7章章图图1.普里姆算法普里姆算法假设假设N=(V,E)是连通网，是连通网，TE为最小生成树中边的集合。为最小生成树中边的集合。（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的的最最小生成树。小生成树。可以看出，可以看出，普利姆算法逐步增加普利姆算法逐步增加U中的顶点，中的顶点，可称为可称为
69、“加点法加点法”。第第7章章图图为为了了实实现现这这个个算算法法需需要要设设置置一一个个辅辅助助数数组组closedge，以以记记录录从从U到到V-U具具有有最最小小代代价价的的边边。对对每每个个顶顶点点vV-U，在在辅辅助助数数组组中中存存在在一一个个分分量量closedgev，它它包包括括两两个个域域vex和和lowcost，其中，其中lowcost存储该边上的权，存储该边上的权，显然有显然有closedgev.lowcost=Min(cost(u,v)|uU)普里姆算法可描述如下：普里姆算法可描述如下：structVertexTypeadjvex;VRTypelowcost;closed
70、geMAX_VERTEX_NUM;/*求最小生成树时的辅助数组求最小生成树时的辅助数组*/第第7章章图图图7.18普里姆算法构造最小生成树的过程第第7章章图图表表7-1普里姆算法各参量的变化普里姆算法各参量的变化第第7章章图图voidMiniSpanTree_Prim(MGraphG,VertexTypeu)/*从从顶顶点点u出出发发，按按普普里里姆姆算算法法构构造造连连通通网网G的的最最小小生生成成树树，并并输输出出生生成成树树的的每条边，这里假设用邻接矩阵存储图每条边，这里假设用邻接矩阵存储图*/k=LocateVertex(G,u);/取得取得u存储的下标存储的下标for(j=0;jG.
71、vexnum;j+)/初始化除定点初始化除定点k之外的其他点的最小代价边之外的其他点的最小代价边if(j!=k)closedgej=u,G.arcskj.adj;closedgek.lowcost=0;for(i=1;iG.vexnum;i+)k=Minium(closedge);/去去V-U集合中定点到集合中定点到U顶点集合中边权值最小的边顶点集合中边权值最小的边printf(closedgek.adjvex,G.vexsk);/*输出生成树的当前最小边输出生成树的当前最小边*/closedgek.lowcost=0;/*将顶点将顶点k纳入纳入U集合集合*/for(j=0;jG.vexnum
72、;j+)/*在顶点在顶点v0并入并入U之后，之后，更新更新closedgej*/if(G.arcskj.adj5,(2,4)-6,(3,4)-6,(2,6)-11,(4,6)-14,(1,2)-16,(4,5)-18,(1,5)-19,(1,6)-21,(5,6)-33。顶点集合状态：顶点集合状态：1，2，3，4，5，6。最小生成树的边的集合：最小生成树的边的集合：。第第7章章图图（2)从待选边中选一条权值最小的边为从待选边中选一条权值最小的边为:(2,3)-5。待待选选的的边边变变为为：(2,4)-6,(3,4)-6,(2,6)-11,(4,6)-14,(1,2)-16,(4,5)-18,(
73、1,5)-19,(1,6)-21,(5,6)-33。顶点集合状态变为：顶点集合状态变为：1，2，3，4，5，6。最小生成树的边的集合：最小生成树的边的集合：(2,3)。第第7章章图图（3）从从待待选选边边中中选选一一条条权权值值最最小小的的边边为为:(2,4)-6。待待选选的的边边变变为为：(3,4)-6,(2,6)-11,(4,6)-14,(1,2)-16,(4,5)-18,(1,5)-19,(1,6)-21,(5,6)-33。顶点集合状态变为：顶点集合状态变为：1，2，3，4，5，6。最小生成树的边的集合：最小生成树的边的集合：(2,3),(2,4)。第第7章章图图（4）从从待待选选边边中
74、中选选一一条条权权值值最最小小的的边边为为:(3,4)-6，由由于于3、4在在同同一一个个顶顶点点集集合合2，3，4内内，故故放放弃弃。重重新新从从待待选选边边中选一条权值最小的边为中选一条权值最小的边为:(2,6)-11。待待选选的的边边变变为为：(4,6)-14,(1,2)-16,(4,5)-18,(1,5)-19,(1,6)-21,(5,6)-33。顶点集合状态变为：顶点集合状态变为：1，2，3，4，6，5。最小生成树的边的集合：最小生成树的边的集合：(2,3)，(2,4),(2,6)。第第7章章图图（5）从从待待选选边边中中选选一一条条权权值值最最小小的的边边为为:(4,6)-14，由
75、由于于4、6在在同同一一个个顶顶点点集集合合2，3，4，6内内，故故放放弃弃。重重新新从从待待选选边边中中选一条权值最小的边为选一条权值最小的边为:(1,2)-16。待待选选的的边边变变为为：(4,5)-18,(1,5)-19,(1,6)-21,(5,6)-33。顶点集合状态变为：顶点集合状态变为：1，2，3，4，6，5。最小生成树的边的集合：最小生成树的边的集合：(2,3)，(2,4),(2,6)，(1,2)。第第7章章图图（6）从待选边中选一条权值最小的边为从待选边中选一条权值最小的边为:(4,5)-18。待选的边变为：待选的边变为：(1,5)-19,(1,6)-21,(5,6)-33。顶
76、点集合状态变为：顶点集合状态变为：1，2，3，4，6，5。最最小小生生成成树树的的边边的的集集合合：(2,3),(2,4),(2,6),(1,2),(4,5)。至至此此，所所有有的的顶顶点点都都在在同同一一个个顶顶点点集集合合1，2，3，4，6，5里里，算算法法结结束束。所所得得最最小小生生成成树树如如图图7.20所所示示，其其代代价价为为：5+6+11+16+18=56。第第7章章图图图图7.20最小生成树最小生成树第第7章章图图7.5有向无环图的应用有向无环图的应用一个无环的有向图称为有向无环图，简称一个无环的有向图称为有向无环图，简称DAG图。图。检查一个有向无环图是否存在环比无向图复杂
77、，如在无向图中检查一个有向无环图是否存在环比无向图复杂，如在无向图中若发现回边（指向已访问过的顶点的边）必存在环，而对有向图若发现回边（指向已访问过的顶点的边）必存在环，而对有向图有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。因有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。因此判断时，从图上某个顶点此判断时，从图上某个顶点v出发，在出发，在dfs(v)结束之前，若出现一结束之前，若出现一条从顶点条从顶点u到顶点到顶点v的回边，说明的回边，说明u是是v的子孙，这时必有环。的子孙，这时必有环。 有向无环图也是描述一项工程或系统的进行过程的有效工具。有向无环图也是描述一项工程或系统的
78、进行过程的有效工具。一个大型工程可分为若干活动（子工程），而这些子工程之间受一个大型工程可分为若干活动（子工程），而这些子工程之间受一定条件的约束，关心的问题是：该工程能否顺序进行，估算整一定条件的约束，关心的问题是：该工程能否顺序进行，估算整个工程完成所必须的最短时间个工程完成所必须的最短时间拓扑排序、关键路径。拓扑排序、关键路径。第第7章章图图7.5.1拓扑排序（拓扑排序（TopologicalSort）用用顶顶点点表表示示活活动动，用用弧弧表表示示活活动动间间的的优优先先关关系系的的有有向向无无环环图图，称称为为顶顶点点表表示示活活动动的的网网（ActivityOnVertexNetwo
79、rk），简称为简称为AOV-网。网。表表72课程关系课程关系第第7章章图图图图7.21表示课程之间优先关系的有向无环图表示课程之间优先关系的有向无环图第第7章章图图在在有有向向图图G=（V，E）中中，V中中顶顶点点的的线线性性序序列列（vi1,vi2,vi3，vin）称称为为拓拓扑扑序序列列，序序列列必必须须满满足足如如下下条条件件：对对序序列列中中任任意意两两个个顶顶点点vi、vj，如如果果在在G中中有有一一条条从从vi到到vj的的路路径径，则在序列中则在序列中vi必排在必排在vj之前。之前。例例如如，图图7.21的的一一个个拓拓扑扑序序列列为为：C1,C2,C3,C4,C5,C8,C9,C
80、7,C6。第第7章章图图AOV-网的特性如下：网的特性如下：若若vi为为vj的的先先行行活活动动，vj为为vk的的先先行行活活动动，则则vi必必为为vk的的先先行行活活动动，即即先先行行关关系系具具有有可可传传递递性性。从从离离散散数数学学的的观观点点来来看看，若有若有、，则必存在，则必存在。显显然然，在在AOV-网网中中不不能能存存在在回回路路，否否则则回回路路中中的的活活动动就就会互为前驱，从而无法执行。会互为前驱，从而无法执行。AOV-网的拓扑序列不是唯一的。网的拓扑序列不是唯一的。例例如如，图图7.21的的另另一一个个拓拓扑扑序序列列为为：C1,C2,C3,C8,C4,C5,C9,C7
81、,C6。第第7章章图图拓扑排序的基本思想为：拓扑排序的基本思想为：（1）从有向图中选一个无前驱的顶点输出；从有向图中选一个无前驱的顶点输出；（2）将此顶点和以它为起点的弧删除；将此顶点和以它为起点的弧删除；（3）重复（重复（1）、（）、（2），直到不存在无前驱的顶点；），直到不存在无前驱的顶点；（4）若若此此时时输输出出的的顶顶点点数数小小于于有有向向图图中中的的顶顶点点数数，则则说说明明有有向向图图中中存存在在回回路路，否否则则输输出出的的顶顶点点的的顺顺序序即即为为一一个个拓拓扑扑序列。序列。第第7章章图图图图7.22AOV-网网例例如如，对对于于图图7.22所所示示的的AOV-网网，执执
82、行行上上述述过过程程可可以以得到如下拓扑序列：得到如下拓扑序列：v1，v6，v4，v3，v2，v5或或v1，v3，v2，v6，v4，v5第第7章章图图基于邻接表的存储结构基于邻接表的存储结构入入度度为为零零的的顶顶点点即即为为没没有有前前驱驱的的顶顶点点，我我们们可可以以附附设设一一个存放各个存放各顶点入度的数组顶点入度的数组indegree，于是有，于是有（1）找找G中中无无前前驱驱的的顶顶点点查查找找indegreei为为零零的的顶顶点点vi；（2）删删除除以以i为为起起点点的的所所有有弧弧对对链链在在顶顶点点i后后面面的的所所有有邻接顶点邻接顶点k，将，将对应的对应的indegreek减
83、减1。为为了了避避免免重重复复检检测测入入度度为为零零的的顶顶点点，可可以以再再设设置置一一个个辅辅助助栈栈，若若某某一一顶顶点点的的入入度度减减为为0，则则将将它它入入栈栈。每每当当输输出出某某一入度为一入度为0的顶点时，便将它从栈中删除。的顶点时，便将它从栈中删除。第第7章章图图StatusTopologicalSort(ALGraphG)FindInDegree(G,indegree);/求得每个顶点的入度求得每个顶点的入度InitStack(S);/初始化一个栈初始化一个栈for(i=0;inextarc)k=p-adjvex;/对对i号顶点的每个邻接点入度减号顶点的每个邻接点入度减1
84、if(!(-indegreek)Push(S,k);/若入度减为若入度减为0，则入栈，则入栈if(countG.vexnum)returnERROR;elsereturnOK;第第7章章图图7.5.2关键路径关键路径有有向向图图在在工工程程计计划划和和经经营营管管理理中中有有着着广广泛泛的的应应用用。通通常常用用有向图来表示工程计划时有两种方法：有向图来表示工程计划时有两种方法：用用顶顶点点表表示示活活动动，用用有有向向弧弧表表示示活活动动间间的的优优先先关关系系，即即上节所讨论的上节所讨论的AOV-网。网。用用顶顶点点表表示示事事件件，用用弧弧表表示示活活动动，弧弧的的权权值值表表示示活活动
85、动所所需要的时间。需要的时间。我我们们把把用用第第二二种种方方法法构构造造的的有有向向无无环环图图叫叫做做边边表表示示活活动动的的网（网（ActivityOnEdgeNetwork）,简称简称AOE-网。网。第第7章章图图AOE-网网在在工工程程计计划划和和管管理理中中很很有有用用。在在研研究究实实际际问问题题时时，人们通常关心的是：人们通常关心的是：哪些活动是影响工程进度的关键活动？哪些活动是影响工程进度的关键活动？至少需要多长时间能完成整个工程？至少需要多长时间能完成整个工程？在在AOE网网中中存存在在唯唯一一的的、入入度度为为零零的的顶顶点点，叫叫做做源源点点；存存在在唯唯一一的的、出出
86、度度为为零零的的顶顶点点，叫叫做做汇汇点点。从从源源点点到到汇汇点点的的最最长长路路径径的的长长度度即即为为完完成成整整个个工工程程任任务务所所需需的的时时间间，该该路路径径叫叫做做关关键键路路径径。关关键键路路径径上上的的活活动动叫叫做做关关键键活活动动。这这些些活活动动中中的的任任意意一一项项活活动动未未能能按按期期完完成成，则则整整个个工工程程的的完完成成时时间间就就要要推推迟迟。相相反，如果能够加快关键活动的进度，则整个工程可以提前完成。反，如果能够加快关键活动的进度，则整个工程可以提前完成。第第7章章图图图图7.24AOE-网网第第7章章图图事事件件vi的的最最早早发发生生时时间间v
87、e(i)：从从源源点点到到顶顶点点vi的的最最长长路路径径的的长长度度，叫叫做做事事件件vi的的最最早早发发生生时时间间。这这个个时时间间决决定定了了所所有有以以vi为为尾尾的的弧弧所所表表示示的的活活动动的的最最早早开开始始时时间间。求求ve(i)时时可可从从源点开始，按拓扑顺序向汇点递推：源点开始，按拓扑顺序向汇点递推：ve(0)=0；ve(i)=Maxve(k)dut()T,1in-1;其其中中，T为为所所有有以以i为为头头的的弧弧的的集集合合，dut()表表示与弧示与弧对应的活动的持续时间。对应的活动的持续时间。第第7章章图图事事件件vi的的最最晚晚发发生生时时间间vl(i)：在在保保
88、证证汇汇点点按按其其最最早早发发生生时间发生这一前提下，求事件时间发生这一前提下，求事件vi的最晚发生时间。的最晚发生时间。在在求求出出ve(i)的的基基础础上上，可可从从汇汇点点开开始始，按按逆逆拓拓扑扑顺顺序序向向源源点递推，求出点递推，求出vl(i)：vl(n-1)=ve(n-1)；vl(i)=Minvl(k)dut()S,0in-2;其其中中，S为为所所有有以以i为为尾尾的的弧弧的的集集合合，dut()表表示与弧示与弧对应的活动的持续时间。对应的活动的持续时间。第第7章章图图活活动动ai的的最最早早开开始始时时间间e(i)：如如果果活活动动ai对对应应的的弧弧为为， 则则 e(i)等等
89、 于于 从从 源源 点点 到到 顶顶 点点 j的的 最最 长长 路路 径径 的的 长长 度度 ， 即即 ：e(i)=ve(j)活活动动ai的的最最晚晚开开始始时时间间l(i)：如如果果活活动动ai对对应应的的弧弧为为，其其持持续续时时间间为为dut(),则则有有：l(i)=vl(k)-dut()，即即在在保保证证事事件件vk的的最最晚晚发发生生时时间间为为vl(k)的的前前提提下下，活活动动ai的的最最晚开始时间为晚开始时间为l(i)。活活动动ai的的松松弛弛时时间间（时时间间余余量量）：ai的的最最晚晚开开始始时时间间与与ai的的最早开始时间之差：最早开始时间之差：l(i)-e(i)。显然，
90、松弛时间（时间余量）为显然，松弛时间（时间余量）为0的活动为关键活动。的活动为关键活动。第第7章章图图图图7.24AOE-网网第第7章章图图求关键路径的基本步骤如下：求关键路径的基本步骤如下：（1）对对图图中中顶顶点点进进行行拓拓扑扑排排序序，在在排排序序过过程程中中按按拓拓扑扑序序列求出每个事件的最早发生时间列求出每个事件的最早发生时间ve(i)；（2）按逆拓扑序列求每个事件的最晚发生时间按逆拓扑序列求每个事件的最晚发生时间vl(i)；（3）求求出出每每个个活活动动ai的的最最早早开开始始时时间间e(i)和和最最晚晚发发生生时时间间l(i)；（4）找出找出e(i)=l(i)的活动的活动ai，
91、即为关键活动。，即为关键活动。第第7章章图图图图7.25关键路径关键路径第第7章章图图例如，对图例如，对图7.24所示的所示的AOE-网计算关键路径的过程如下网计算关键路径的过程如下:(1)计算各顶点的最早开始时间：计算各顶点的最早开始时间：(2)ve(0)=0(3)ve(1)=maxve(0)+dut()=6(4)ve(2)=maxve(0)+dut()=4(5)ve(3)=maxve(0)+dut()=5(6)ve(4)=maxve(1)+dut(),ve(2)+dut()=7(7)ve(5)=maxve(3)+dut()=7(8)ve(6)=maxve(4)=dut()=16(9)ve(
92、7)=maxve(4)+dut()=14(10)ve(8)=maxve(6)+dut(),ve(7)+dut()=18第第7章章图图(2)计算各顶点的最迟开始时间：计算各顶点的最迟开始时间：vl(8)=ve(8)=18vl(7)=minvl(8)-dut()=14vl(6)=minvl(8)-dut()=16vl(5)=minvl(7)-dut()=10vl(4)=minvl(6)-dut(),vl(7)-dut()=7vl(3)=minvl(5)-dut()=8vl(2)=minvl(4)-dut()=6vl(1)=minvl(4)-dut()=6vl(0)=minvl(1)-dut(),v
93、l(2)-dut(),vl(3)-dut()=0第第7章章图图(3)计算各活动的最早开始时间：计算各活动的最早开始时间：e(a1)=ve(0)=0e(a2)=ve(0)=0e(a3)=ve(0)=0e(a4)=ve(1)=6e(a5)=ve(2)=4e(a6)=ve(3)=5e(a7)=ve(4)=7e(a8)=ve(4)=7e(a9)=ve(5)=7e(a10)=ve(6)=16e(a11)=ve(7)=14第第7章章图图(4)计算各活动的最迟开始时间：计算各活动的最迟开始时间：l(a11)=vl(8)-dut()=14l(a10)=vl(8)-dut()=16l(a9)=vl(7)-dut
94、()=10l(a8)=vl(7)-dut()=7l(a7)=vl(6)-dut()=7l(a6)=vl(5)-dut()=8l(a5)=vl(4)-dut()=6l(a4)=vl(4)-dut()=6l(a3)=vl(3)-dut()=3l(a2)=vl(2)-dut()=2l(a1)=vl(1)-dut()=0第第7章章图图对图对图7.24所示网的计算结果如下所示。所示网的计算结果如下所示。第第7章章图图7.6最最短短路路径径7.6.1求某一顶点到其它各顶点的最短路径求某一顶点到其它各顶点的最短路径图图7.26一个带权有向图及其邻接矩阵一个带权有向图及其邻接矩阵012345012345050
95、104501510200152003530030第第7章章图图表表73v0到其它顶点的最短路径到其它顶点的最短路径第第7章章图图 对对于于给给定定的的有有向向图图G=(VG=(V，E)E)及及单单个个源源点点VsVs，求求VsVs到到G G的其余各顶点的最短路径。的其余各顶点的最短路径。 DijkstraDijkstra提提出出了了一一种种按按路路径径长长度度递递增增次次序序产产生生最短路径的算法，即最短路径的算法，即迪杰斯特拉迪杰斯特拉Dijkstra Dijkstra 算法算法。 基本思想基本思想 从从图图的的给给定定源源点点到到其其它它各各个个顶顶点点之之间间客客观观上上应应存存在在一一
96、条条最最短短路路径径，在在这这组组最最短短路路径径中中，按按其其长长度度的的递递增增次次序序，依依次次求求出出到到不不同同顶顶点点的的最最短短路路径径和和路路径长度。径长度。第第7章章图图即按长度递增的次序生成各顶点的最短路径，即先即按长度递增的次序生成各顶点的最短路径，即先求出长求出长度最小的一条最短路径，然后求出长度第二小的度最小的一条最短路径，然后求出长度第二小的最短路径，依最短路径，依此类推，直到求出长度最长的最短路径。此类推，直到求出长度最长的最短路径。算法思想说明算法思想说明设设给给定定源源点点为为Vs，S为为已已求求得得最最短短路路径径的的终终点点集集，开开始始时时令令S=Vs。
97、当当求求得得第第一一条条最最短短路路径径(Vs，Vi)后后，S为为Vs，Vi。根据以下结论可求下一条最短路径。根据以下结论可求下一条最短路径。设下一条最短路径终点为设下一条最短路径终点为j，则，则Vj只有：只有：源点到终点有直接的弧源点到终点有直接的弧；Vs出出发发到到Vj的的这这条条最最短短路路径径所所经经过过的的所所有有中中间间顶顶点点必必定定在在S中中。即即只只有有这这条条最最短短路路径径的的最最后后一一条条弧弧才才是是从从S内内某某个个顶顶点点连接到连接到S外的顶点外的顶点Vj。第第7章章图图引引进进一一个个辅辅助助向向量量D，它它的的每每一一个个分分量量Di表表示示当当前前所所找找到
98、到的的从从始始点点V0到到每每个个终终点点Vi的的最最短短路路径径长长度度。S表表示示已已求求得最短路径的终点集合。迪杰斯特拉算法的得最短路径的终点集合。迪杰斯特拉算法的主要步骤如下：主要步骤如下：(1)G为为用用邻邻接接矩矩阵阵表表示示的的带带权权图图。arcsij表表示示弧弧上上的的权权值值。令令S=V0，也也就就是是将将起起始始点点加加入入集集合合S当当中中，那那么么从从V0出发到图上其余各个顶点出发到图上其余各个顶点Vi的最短路径长度的初值为：的最短路径长度的初值为：第第7章章图图(2)选择选择Vj，使得，使得Vj为目前求得的下一条从为目前求得的下一条从V0出发的最短路径的终点。出发的
99、最短路径的终点。(3)修修改改从从V0出出发发到到集集合合V-S上上任任一一顶顶点点Vk的的最最短短路路径径的的长长度。如果度。如果Dj+g.arcsjkDk则将则将distk修改为修改为Dk+g.arcskjDj=min(Di|viV-S)第第7章章图图(2)选择选择Vj，使得，使得Vj为目前求得的下一条从为目前求得的下一条从V0出发的最短路径的终点。出发的最短路径的终点。(3)修修改改从从V0出出发发到到集集合合V-S上上任任一一顶顶点点Vk的的最最短短路路径径的的长长度。如果度。如果Dj+g.arcsjkDk则将则将distk修改为修改为Dk+g.arcskj(4)重复重复(2)、(3)
100、n-1次，即可按最短路径长度的递增顺序，次，即可按最短路径长度的递增顺序，逐个求出逐个求出v0到图中其它每个顶点的最短路径。到图中其它每个顶点的最短路径。Dj=min(Di|viV-S)第第7章章图图第第7章章图图第第7章章图图迪杰斯克拉算法求最短路径的算法描述如下：迪杰斯克拉算法求最短路径的算法描述如下：void ShortteatPath_DIJ(Mgraph G, int v0, PathMatrix &P,ShortPathTable&D)for(v=0;vG.vexnum;+v)finalv=FALSE;Dv=G.arcsv0v;for(w=0;wG.vexnum;+w)Pvw=FA
101、LSE;if(DvINFINITY)Pvv0=TRUE;Pvv=TRUE;/forDv0=0;finalv0=TRUE;第第7章章图图/开始循环，每次求得开始循环，每次求得V0到某个到某个V顶点的最短路径，并加顶点的最短路径，并加V到到S集集for(i=1;iG.vexnum;+i)min=INFINITY;for(w=0;wG.vexnum;+w)if(!finalw)if(Dwmin)v=w;min=Dw;/求当前最短路经求当前最短路经finalv=TRUE;/该顶点并入该顶点并入S集合集合for(w=0;wG.vexnum;+w)/更新当前最短路径及距离更新当前最短路径及距离if(!finalw&(min+G.arcsvwDw)Dw=min+G.arcsvw;Pw=Pv;Pww=TRUE;/if/for
