1、第六章 图6.1 图的定义和基本术语6.2 图的存储方式6.3 图的遍历6.4 图与最小生成树6.5 AOV网与拓扑排序6.6 AOE网与关键路径6.7 最短路径6.8 本章实战练习6.9 小结6.1 图的定义和基本术语6.2 图的存储方式6.3 图的遍历6.4 图与最小生成树6.5 AOV网与拓扑排序6.6 AOE网与关键路径6.7 最短路径6.8 本章实战练习6.9 小结6.1 图的定义和基本术语图形结构是一种比线性表和树形结构更复杂的非线性数据结构。线性结构中，数据元素之间具有单一的线性关系；树形结构中，节点间具有一对多的分支层次关系。在图形结构中，任意两个结点间可能有关系也可能根本不存
2、在任何关联，结点间是多对多的复杂关系。可以说，树是图的特例，线性表是树的特例。在现实中有很多问题可以抽象成为图的形式，因此借助图的结构和技术可以解决很多实际应用问题。图有着雄厚的理论基础，离散数学中，我们已经学过有关图的一些理论，关系代数和图论中也详细介绍了图的基本理论知识。本章重点介绍图在计算机中的存储表示和它的基本操作的实现。6.1.1 图的定义图的定义图（Graph）是由有穷非空定点集合和边（或弧）构成的。采用形式化的定义，图是由两个集合V（Vertex）和E（Edge）组成，记作G=（V,E）。其中V是顶点的有限集合，记为V（G），E是连接V中两个不同定点（即顶点对）的边的有限集合，记
3、为E（G）。图的抽象数据类型定义如下：ADT Graph 数据对象：D=ai|1in,n0,ai 属于ElemType类型/*ElemType是C/C+中自定义的类型标识符*/6.1.1 图的定义图的定义6.1.1 图的定义图的定义（2）对顶点的操作LocateVex(G,x);/*查找顶点即在图G中查找顶点x并返回该顶点在图中的位置*/GetVex(G,x);/*在图G中查找到顶点x并返回x的值*/PutVex(&G,v,value);/*为顶点v赋值*/InsertVex(&G,x);/*在图G中增加顶点v*/DeleteVex(&G,v);/*在图G中删除顶点v*/6.1.1 图的定义图
4、的定义（3）对边的操作InsertArc(&G,v,w);/*若G是有向图，则增加弧；若G是无向图，则增加弧和*/DeleteArc(&G,v,w);/*若G是有向图，则删除弧；若G是无向图，则删除弧和*/（4）对邻接点的操作FirstAdjVex(G,v);/*返回v的第一个邻接顶点，若v没有邻接顶点则返回“空”*/NextAdjVex(G,x,w);/*返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接顶点，则返回“空”*/6.1.1 图的定义图的定义（5）图的遍历DFSTra(g);/*深度优先遍历图*/BFSTra(g);/*广度优先遍历图*/ADT GraphV（G）是顶点
5、的有限集合，通常用字母或者自然数（顶点编号）来标识图中顶点。规定第i个顶点，即编号为i的顶点用vi 表示；E（G）是图中边的集合，它确定了图G的数据元素的关系，E（G）可以为空集，此时表示图G只有顶点没有边，也就是说，顶点和顶点之间没有任何关系。6.1.2 图的基本术语图的基本术语图6.1 无向图G1 图6.2 有向图G26.1.2 图的基本术语图的基本术语6.1.2 图的基本术语图的基本术语完全图（完全图（Completed graph）：）：如果无向图中任意两个顶点间都存在边，则称之为无向完全图。在一个含有n个顶点的无向完全图中，边数为n(n-1)/2条。如果有向图中任意两个顶点间都存在方
6、向互为相反的两条弧，则称之为有向完全图。在一个含有n个顶点的有向完全图中，边数为n(n-1)条。稠密图、稀疏图：稠密图、稀疏图：有很少条便或者弧的图成为稀疏图（Sparse graph），反之称为稠密图（Dense graph）。度：度：顶点v的度是和v相关联的边的数目，记为TD(v)。有向图中，以顶点v为头的弧的数目称为v的入度（InDegree），记为ID(v)。以顶点v为尾的弧的数目称为v的出度（OutDegree），记为OD(v)。TD(v)=ID(v)+OD(v)。无向图不区分入度和出度。6.1.2 图的基本术语图的基本术语权、网：权、网：在 边 或 者 弧 上 的 数 据 信 息
7、称 为 权（Weight）。权值可以表示从一个顶点到另一个顶点的距离或者耗费。带权的图称为网（Network）。路径、路径长度：路径、路径长度：顶点vi到顶点vj的路径（Path）是指从顶点vi到顶点vj之间所经历的顶点序列vi，vi，1vi,m，vj，其中（vi，vi,1）（vi，m，vj）和（vi，j，vi,j+1）E，1jm-1都是图中的边。路径的长度是路径上的边或弧的数目。回路、简单路径、简单回路：回路、简单路径、简单回路：第一个顶点和最后一个顶点相同的路径称为回路或环（Cycle）。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称为
8、简单回路或者简单环。6.1.2 图的基本术语图的基本术语连通图、连通分量、强连通图、强连通分量：连通图、连通分量、强连通图、强连通分量：无向图G中，如果从顶点vi到顶点vj有路径，则称vi和vj是连通的。如果对于图中任意两个顶点vi、vjV，vi和vj都是连通的，则称图G的连通图（Connected Graph）。无向图中的极大连通子图称为连通分量（Connected Component）。例如：图6.3中的G3就是一个连通图。而G4就是非连通图，但有2个连通分量，如图6.4所示。非连通图G4 G4的两个连通分量 图6.46.1.2 图的基本术语图的基本术语有向图G中，如果从vi到vj并且从v
9、j到vi都有路径，则称图G是强连通图。有向图中的极大连通子图称作有向图的强连通分量。例如：图6.5中的G5就是一个强连通图。而G6就是非强连通图，但有2个强连通分量，如图6.6所示。图6.5 强连通图G5 非强连通图G6 G6的两个强连通分量 图6.66.1.2 图的基本术语图的基本术语生成树：生成树：连通图G的生成树，是包含G的全部n个顶点的一个极小连通子图，该极小连通子图有（n-1）条边。如图6.7所示，是连通图G3的生成树。如果在一棵生成树上添加一条边，必定构成一个环，因为这条边的出现使得它依附的那两个顶点之间有了第二条路径。一棵有n个顶点的生成树有且仅有（n-1）条边。如果一个图有n个
10、顶点和小于（n-1）条边，则是非连通图。如果它多于（n-1）条边，则一定有环。但需要大家注意的是，有（n-1）条边的图不一定是生成树。右图6.76.1.2 图的基本术语图的基本术语生成森林：生成森林：如果一个有向图有且仅有一个顶点的入度为0，其他顶点的入度均为1，则这个图是一棵有向树。当一个有向图有多个顶点的入度为0时，它的生成森林是由多棵有向树构成。其中，这个生成森林含有图中全部顶点和相应的弧。如图6.8所示是有向图G7及其生成森林。有向图G7 G7的生成森林图6.86.1 图的定义和基本术语6.2 图的存储方式6.3 图的遍历6.4 图与最小生成树6.5 AOV网与拓扑排序6.6 AOE网
11、与关键路径6.7 最短路径6.8 本章实战练习6.9 小结6.2 图的存储方式图的存储方式图是一种结构复杂的数据结构，图的信息包括顶点和边两部分。由于任意的两个顶点之间可能存在联系，因此不能用数据元素在存储区中的物理位置来表示元素之间的关系，即图不能用顺序映像的存储结构。但是可以借助数组的数据类型表示元素之间的关系。多重链表是一种最简单的链式映像结构，以一个由数据域和指针域组成的结点表示图的一个顶点。其中，数据域存储顶点信息，指针域可以有多个用来存储指向其邻接点的指针。如图6.9所示为图6.1无向图G1、图6.2有向图G2的多重链表。无向图G1多重链表 有向图G2的多重链表图6.96.2 图的
12、存储方式图的存储方式由于每个顶点的度不一定相同，因此在设计结点结构时应该根据实际需要进行操作，设计恰当的结点结构和表结构以获得相对较好的存储单元的利用率。常用的有数组表示法、邻接表表示法、邻接多重表表示法和十字链表表示法。6.2.1 邻接矩阵邻接矩阵图的邻接矩阵（Adiacency Matrix）存储结构又称为数组表示法。其用两个数组分别存储顶点的信息和顶点之间的关系（边或弧）的信息。例如图6.3无向图G3和图6.8有向图 G7的邻接矩阵如图6.10所示。用二维数组表示有n个顶点的图时，需要存储n个顶点的信息以及n2个边的信息。无向图G3的邻接矩阵 有向图G7的邻接矩阵图6.106.2.1 邻
13、接矩阵邻接矩阵网的邻接矩阵定义如下：图的数组表示法具有以下特点：1.因为无向图的邻接矩阵具有对称性，所以可以采取我们之前讲过的压缩存储的方式只存储矩阵的上三角（或下三角）元素。2.无向图（网）的邻接矩阵的第i行（或第i列）非零元素（或非元素）的个数是第i个顶点的度TD(vi)。3.有向图（网）的邻接矩阵的第i行非零元素（或非元素）的个数是第i个顶点的出度OD(vi)。6.2.1 邻接矩阵邻接矩阵4.有向图（网）的邻接矩阵的第i列非零元素（或非元素）的个数是第i个顶点的出入ID(vi).5.显然我们可以通过邻接矩阵很快的看出任意两个顶点之间是否有关系；但是，如果我们想确定这个图（或网）中有多少条
14、边（或弧），就必须遍历整个二维数组，对非零元素（或非无穷元素）计数。时间复杂度是O(n2)并不是理想的时间开销，这是邻接矩阵存储方式的局限。6.2.1 邻接矩阵邻接矩阵/图的邻接矩阵存储表示#define MaxVerNum 10 /最大顶点数typedef enumDG,DN,UDG,UDN GraphType;/枚举有向图，有向网，无向图，无向网typedef structVerType vexsMaxVerNum;/顶点表ArcType arcsMaxVerNumMaxVerNum;/邻接矩阵int vexnum,arcnum;/顶点数和边数GraphType type;/图的类型标识M
15、Graph;void CreateDN(MGraph&G)/算法6.1用数组表示法构造有向网Gscanf(&G.vexnum,&G.arcnum);for(i=0;i G.vexnum;i+)scanf(&G.vexsi);/构造顶点表for(i=0;i G.vexnum;i+)for(j=0;j G.vexnum;j+)G.arcsij=-1;/初始化邻接矩阵权值均为-1，用-1表示邻接矩阵中的元素 for(k=0;k G.vexnum;k+)Scanf&v1,&v2,&w;/接受用户输入与边相连的两个顶点及边的权值n=LocateVex(G,v1);/确定v1在图中的位置m=LocateV
16、ex(G,v2);G.arcsnm=w;/end of CreateDN6.2.1 邻接矩阵邻接矩阵显然，算法6.1的时间复杂度只与途中顶点数有关，与边数无关。因此邻接矩阵存储方式比较适合存储稠密图。数组表示法的空间复杂度是O(n+n2)，其中n表示顶点所占的空间，n2表示邻接矩阵所占的空间。6.2.2 邻接邻接表表邻接表（Adiacency List）也是图的存储方式，它是将顺序存储和链式存储相结合而形成的一种存储方法。邻接表为图的每一个顶点建立一个单链表，将图中的每个顶点vi的所有临结点都放在以vi为表头的链表里，再将所有定点的邻接表表头放到一个一维数组里，显然一维数组是顺序存储结构，由一
17、维数组和多个单链表构成图的邻接表结构。邻接表包括顶点表和边表，对应的结点结构如下图6.11所示。头结点 表结点图6.116.2.2 邻接邻接表表/图的邻接表存储表示#define MaxVerNum 10 /最大顶点数typedef enumDG,DN,UDG,UDN GraphType;/枚举有向图，有向网，无向图，无向网typedef struct ArcNodeint adjvex;/邻接顶点的位置ArcNode *nextarc;/标记下一个vi的邻接结点的指针char data;/标记和边（或弧）的相关信息 ArcNode;typedef struct VexNodeVexInfo
18、vex;/顶点的信息ArcNode *firstarc;/标记第一个vi的邻接结点的指针 VexNode VexListMaxVerNum;typedef struct ALGraphVexList vexs;int vexnum,arcnum;/顶点数和边数GraphType type;/图的类型标识 ALGraph;6.2.2 邻接邻接表表图的邻接表表示法具有以下特点：1.在无向图的邻接表中，第i个链表的结点数目等于顶点vi的度。2.在有向图的邻接表中，第i个链表的结点数目是顶点vi的出度。3.在邻接表中可以快速找到某一顶点的邻接点，但是要确定任意两个顶点（vi 和 vj）之间是否有边（或
19、弧），就必须搜索第i个或者第j个链表，在这个方面远不及邻接矩阵方便快捷。有向图的邻接表不方便查找以vi为弧头的结点数，为此我们可以建立一个逆邻接表，为每一个顶点建立一个以vi为弧头的表。例如图6.12c所示如果在建立邻接表时，仅以顶点编号作为顶点信息输入，则其时间复杂度为O(n+e)。(a)无向图G1的邻接表(b)有向图G2的邻接表(c)有向图G2的逆邻接表图6.12 邻接表和逆邻接表6.2.2 邻接邻接表表6.2.3 十字十字链表链表十字链表（Orthogonal List）是针对有向图的另一种链式存储方式。它综合了邻接表和逆邻接表。在十字链表中，有向图的每一个顶点有一个结点，每一条弧也有一
20、个结点。结点结构如图6.13所示。顶点结点 弧结点图6.13 十字链表顶点结点和弧结点 顶点域 指针域 指针域 弧尾结点 弧头结点 弧信息 指针域 指针域6.2.3 十字十字链表链表顶点结点中，vex是顶点vi的数据域，用来存储顶点的信息；firstin指向第一个以vi为弧头的弧结点，firstout指向第一个以vi为弧尾的弧结点。弧结点中，tailvex表示弧尾结点在图中的存储位置；headvex表示弧头结点在图中的存储位置；hlink指向弧头相同的下一个弧结点；tlink指向弧尾相同的下一个弧结点。data记录这条弧的信息，例如权值等。/图的十字链表存储表示#define MaxVerNu
21、m 10 /最大顶点数typedef struct ArcNodeint tailvex,headvex;ArcNode *hlink,*tlink;char data;/标记和边（或弧）的相关信息 ArcNode;typedef struct VexNodeVexInfo vex;/顶点的信息ArcNode *firstin,*firstout;/标记第一个vi的邻接结点的指针 VexNode VexListMaxVerNum;typedef struct OLGraphVexList vexs;int vexnum,arcnum;/顶点数和边数 OLGraph;/下面算法6.2是建立有向图
22、的十字链表。void CreateOLGraph(OLGraph&G)scanf(&G.vexnum,&G.arcnum);/接受用户输入顶点数和弧数 for(i=0;i G.vexnum;i+)scanf(&G.vexsi.vex);/接受用户输入顶点信息G.vexsi.firstin=NULL;/初始化指针G.vexsi.firstout=NULL;for(j=0;j G.arcnum;j+)scanf(&v1,&v2);/接受用户输入弧头和弧尾n=LocateVex(G,v1);/确定v1在图中的位置m=LocateVex(G,v2);p=(ArcNode*)malloc(sizeof(
23、ArcNode);/为弧结点分配空间*p=n,m,G.vexsm.firstin,G.vexsn.firstout;/初始化弧结点G.vexsm.firstin=p;/将p连入十字链表中G.vexsn.firstout=p;/end of CreateOLGraph6.2.3 十字十字链表链表通过算法6.2可以看出，我们只需要输入n个顶点和e条弧的信息就可以建立十字链表。十字链表中，我们可以轻易找到以vi为弧头或弧尾的弧，因此很容易算出顶点vi的出度和入度。建立十字链表的时间复杂度是O(n+e)，和建立邻接表的时间复杂度相同。6.1 图的定义和基本术语6.2 图的存储方式6.3 图的遍历6.4
24、 图与最小生成树6.5 AOV网与拓扑排序6.6 AOE网与关键路径6.7 最短路径6.8 本章实战练习6.9 小结6.3 图的遍历图的遍历与树的遍历类似，从图中的任意顶点出发，访问其余定点，并且保证所有顶点只被访问一次，这一过程被称为图的遍历（Traversing Graph）。判断图的连通性、拓扑排序和求关键路径都以图的遍历为基础。图的遍历操作复杂，在遍历过程中应该注意以下问题。1.如何选取起始结点。在无向图中，我们可以任意选取起始结点。在有向图中,我们应当尽量选取入度为0的结点为起始结点，这可以使我们的遍历更加清晰。6.3 图的遍历2.当遍历的图是非连通图时，那么从一个结点出发只能访问它
25、所在的连通分量上的所有结点，并不能访问图的所有结点。因此，遍历还需要考虑不同连通分量的起始结点的选取问题。3.图中一个结点可能和多个结点相邻接，我们如何选取下一个邻接点。4.无向图和有向图中都有可能存在回路，那么在一个结点被访问之后有可能因为回路的存在而再次被访问，我们如何避免一个结点被多次访问。一般我们采用深度优先搜索遍历（Depth First Search，DFS）和广度优先遍历（Breadth First Search，BFS）两种方式进行图的遍历。6.3.1 深度优先遍历深度优先遍历算法算法深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的拓展。假设初始状态是图中所有定点都未被访问
26、过，那么深度优先搜索可以从图中某个结点v出发，首先访问此结点，然后从v的未曾访问的邻接点中选择一个v/进行访问，然后再从v/的邻接点中选择一个进行访问，依此类推，直到图中所有和v有路径相通的结点都被访问过为止；如果此时图中还有结点没有被访问，那么选择一个未被访问的结点作为新起始结点，重复上述操作，直到图中所有结点都被访问完。深度优先遍历是通过探索图的最大深度的方式来访问所有结点。下面以图6.14的无向图G8为例，进行图的深度优先遍历。图6.14 无向图G86.3.1 深度优先遍历深度优先遍历算法算法6.3.1 深度优先遍历深度优先遍历算法算法假设从顶点v1为起始结点，在访问v1之后，选择邻接结
27、点v2。因为v2未被访问过，所以可以从v2出发进行搜索。在访问v2之后，选择邻接结点v5。因为v5未被访问过，所以可以从v5出发进行搜索。依次类推，从v4和v8出发进行搜索。在访问了v8之后，由于v8的邻接点都被访问过，因此搜索退回到v4，因为相同的原因，搜索退回到v5、v2，直到v1。此时由于v1的另一个邻接点v3尚未被访问，则搜索继续从v3开始，重复上述遍历过程。由此，得到的结点访问序列如下：V1，V2，V5，V4，V8，V3，V7，V66.3.1 深度优先遍历深度优先遍历算法算法显然，图的深度优先遍历是一个递归的过程。在递归过程中，我们就遇到了本节开头提出的问题（4），我们可以通过辐射一
28、个访问标记数组visited0n-1，初始值均为false，一旦某个结点被访问，立即对其相应分量置true，由此可以区别图中结点是否被访问过，并最终遍历所有结点也避免了结点重复访问。下面算法6.3是从图的某一结点出发，递归地进行深度优先搜索。void DFS(Graph G,int v)for(int i=0;iG.vexnum;i+)/初始化标记数组visitedi=false;visitedv=true;visit(v);/访问结点v并置标记数组中v的对应位置为truex=FirstAdjvex(G,v);while(x!=NULL)if(visitedx=false)DFS(G,x);/
29、对结点x递归调用DFSx=NextAdjvex(G,v,x);/end of DFS/下面算法6.4是深度优先搜索以邻接表存储的非连通图G。void DFSTraversALGraph(ALGraph&G)for(int i=0;iG.vexnum;i+)visitedi=false;/初始化标识数组for(int k=0;kG.vexnum;k+)if(visitedk=false)DFSALGraph(G,k);/end of DFSTraversALGraph/下面算法6.5是如何遍历以邻接表存储的连通图G。void DFSALGraph(MGraph&G,int k)ArcNode*p
30、=NULL;visitedk=true;p=G.vexsk.firstarc;/取头结点是k的边表的头指针while(p)int q=p.adjvex;if(visitedq=false)DFSALGraph(G,q);/若结点q未被访问，则以q为新的起始结点继续深度优先遍历p=p.nextarc;/顶点k的下一个邻接点/end of DFSALGraph/下面算法6.6是深度优先搜索以邻接矩阵存储的连通图G。void DFSMGraph(MGraph G,int v)/从顶点V出发遍历 for(int i=0;iG.vexnum;i+)/初始化标记数组visitedi=false;visit
31、(v);visitedv=true;for(int w=0;wG.vexnum;w+)if(G.arcsvw=1)&(visitedw=false)DFSMGraph(w);/end of DFSMGraph6.3.1 深度优先遍历深度优先遍历算法算法在深度优先遍历时，对图中的每个顶点有且只有一次调用DFS函数，因为visitedn-1数组在不断的被更新，某个顶点visitedi一旦被标记成true，则其将不再被访问。因此深度优先遍历的过程可以看作是对图中结点查找其邻接点的过程。不同的存储方式似的查找邻接点的时间复杂度不尽相同。当图采用邻接矩阵的存储方式时，查找每个结点的邻接点的时间复杂度为O
32、(n2)。当采用邻接表的存储方式时，先要找到每个顶点，其时间复杂度为O(n)，再找到每个顶点的邻接点，其时间复杂度为O(e)。因此总的时间复杂度为O(n+e)。6.3.2 广度优先遍历广度优先遍历算法算法广度优先搜索（Breadth First Search）遍历类似于树的层次遍历过程。设图G的初态是所有顶点均未访问，在G 中任选一顶点i作为初始点，则广度优先搜索的基本思想是：1.首先访问顶点vi，并将其访问标志置为已被访问，即visitedi=true；2.接着依次访问与顶点vi有边相连的所有顶点W1，W2，Wt；3.然后再按顺序访问与W1，W2，Wt有边相连又未曾访问过的顶点；依此类推，直
33、到图中所有顶点都被访问完为止。需要注意的是先被访问的顶点的邻接点会排在后被访问的顶点的邻接点。6.3.2 广度优先遍历算法广度优先遍历算法无向图G9的中，从顶点v1出发的广度优先搜索遍历序列举三种为：v1,v2,v3,v4,v5,v6,v7,v8v1,v3,v2,v7,v6,v5,v4,v8v1,v2,v3,v5,v4,v7,v6,v8图6.15 无向图G96.3.2 广度优先遍历广度优先遍历算法算法和深度优先搜索类似，在遍历的过程中也需要一个访问标记数组。并且，为了顺次访问路径长度为2、3、的顶点，需附设队列以存储已被访问的路径长度为1，2，的顶点。算法6.7是从图的某一结点出发，非递归地进
34、行广度优先遍历。void BFS(Graph G,int v）visit(v);visitedv=true;InitQueue(Q);/初始化队列 EnQueue(Q,v);/起始顶点v入队 while(!Empty(Q)DelQueue(Q,u);/队头元素出队并用v保存 w=FirstAdjvex(G,u);/求v的邻接点 while(w!=0)if(!visitedw)visit(w);visitedw=true;EnQueue(Q,w);w=NextAdjvex(G,u,w);/求下一邻接点 /end of BFS算法6.8是广度优先遍历用邻接矩阵存储的图G。void BFSMGrap
35、h(MGraph G,int v)/从顶点v出发遍历 InitQueue(Q);/Q为队列 visit(v);/输出访问顶点 visitedv=true;/全局数组标记置v已访问 EnQueue(v);/入队列 while(!Empty(Q)DelQueue(Q,u);/队头元素出队并用u保存 for(w=0;wG.vexnum;w+)if(Auw=1)&(visitedw=false)visit(w);visitedw=true;EnQueue(w);/end of BFSMGraph算法6.9是广度优先遍历用邻接表存储的图G。void BFSALGraph(ALGraph G,int v)
36、InitQueue(Q);/Q为队列 visit(v);/输出访问顶点 visitedv=true;/全局数组标记置v已访问 EnQueue(v);/入队列 while(!Empty(Q)DelQueue(Q,u);p=G.vexsu.firstarc;/取头结点是u的边表的头指针 while(p)int q=p.adjvex;if(visitedq=false)visit(q);EnQueue(q);/入队列 p=p.nextarc;/顶点k的下一个邻接点,结点继续深度优先遍历 /end of BFSALGraph6.3.2 广度优先遍历算法广度优先遍历算法通过对算法6.36.9的比较和分析
37、可以看出,图中每个顶点最多进队一次。图的遍历的过程实际上是通过边或弧找邻接顶点的过程。因此图的深度优先遍历和广度优先遍历的时间复杂度相同，唯一的不同点是对顶点的访问顺序有差别。6.1 图的定义和基本术语6.2 图的存储方式6.3 图的遍历6.4 图与最小生成树6.5 AOV网与拓扑排序6.6 AOE网与关键路径6.7 最短路径6.8 本章实战练习6.9 小结6.4 图与最小生成树若图是连通的或强连通的，则从图中某一个顶点出发可以访问到图中所有顶点；若图是非连通的或非强连通图，则需从图中多个顶点出发搜索访问，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为每个连通分量中的顶点集。
38、6.4.1 生成树和森林的生成树和森林的算法算法深度优先搜索遍历算法及广度优先搜索遍历算法中遍历图过程中历经边的集合和顶点集合一起构成连通图的极小连通子图。它是连通图的一颗生成树。它含有图中全部顶点，但只有n-1条边。由深度优先搜索遍历得到的生成树，称为深度优先生成树，由广度优先搜索遍历得到的生成树，称为广度优先生成树。如图6.16 是无向图G9的两种生成树示意图。无向图G9 深度优先生成树 广度优先生成树图6.16 无向图及其生成树6.4.1 生成树和森林的算法生成树和森林的算法下面算法6.10是通过深度优先遍历图G，建立以T为根的生成树。void DFSCreateTree(Graph G
39、,int v,Tree&T)visitedv=true;int firstchild=0;for(int w=FirstAdjvex(G,v);wnextBrother=p;q=p;DFSCreateTree(G,w,q);/end of DFSCreateTree若一个图是非连通图或非强连通图，但有若干个连通分量或若干个强连通分量，则通过深度优先搜索遍历或广度优先搜索遍历，不能得到生成树，但可以得到生成森林，且若非连通图有 n 个顶点，m 个连通分量或强连通分量，则可以遍历得到m棵生成树，合起来为生成森林，森林中包含n-m条树边。生成森林可以利用非连通图的深度优先搜索遍历或非连通图的广度优先
40、搜索遍历算法得到。非连通图G10 G10的生成森林6.4.1 生成树和森林的算法生成树和森林的算法下面算法6.11是通过深度优先遍历非连通图G，建立以T为根的生成森林。void DFSCreateForest(Graph G,Tree&T)T=NULL;/初始化T为空树for(int i=0;iG.vexnum;i+)/初始化标记数组visitedi=false;for(int i=0;inextBrother=p;q=p;DFSCreateTree(G,v,p);以上内容介绍的是如何得到无向图的生成树和生成森林及其算法，下面我们以采用十字链表存储方式的图为例，介绍如何求强连通分量的顶点集。具
41、体步骤如下：1.在有向图G中，首先从顶点v出发沿以v为弧尾的弧进行深度优先遍历，并按访问顺序将顶点依次编号排列起来。2.从序列的编号最大的顶点w出发，沿以w为弧头的弧进行逆向深度优先遍历，如果一次遍历到图中所有顶点，则图G是强连通图；如果不能访问到所有顶点，则从剩余定点中编号最大的定点出发，继续做逆向深度优先遍历，直至图中所有顶点均被访问。此时得到图G的所有强连通分量。每次逆向深度优先遍历得到的顶点集是图G的一个强连通分量的顶点集。6.4.1 生成树和森林的算法生成树和森林的算法6.4.2 最小生成树最小生成树当我们对图G用不同的遍历方法时，可以得到不同的生成树，并且用相同的遍历方法但从不同的
42、顶点出发，也可能得到不同的生成树。按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。若无向连通图是一个带权图，则它必有一棵生成树的所有边的权值之和最小，这样的生成树称为该图的最小生成树(MST Minimum cost Spanning Tree)。构造最小生成树的准则：1.必须只使用该网络中的边来构造最小生成树；2.必须使用且仅使用n-1条边来连接网络中的n个顶点；3.不能使用产生回路的边。6.4.2 最小生成树最小生成树当带权图中有边具有相同的权值时，由于选择的随意性，产生的最小生成树可能不唯一。但是当各边的权值不相同时，产生的最小生成树必然唯一。现实生活中，我们
43、经常遇到需要用最小生成树来解决的问题。比如，我们在若干城市之间铺设公路，铺设道路有对应的经济成本，我们如何保证城市连通的同时把总成本降到最低。铺设公路的造价一般依据城市间的距离设定，我们在考察了实际地形之后进行距离的测量，至此可以用一个带权无向图G来表示城市和公路直接的关系。顶点表示城市，边表示城市间的公路。我们想使总成本降到最低等价于寻找图G的最小生成树。6.4.2 最小生成树最小生成树如何构造最小生成树，典型代表算法是普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法，下面分别予以介绍。1.普里姆（Prim）算法生成最小生成树普里姆算法的基本思想:设G=（V，E）是带权图，V是图G的
44、顶点集，E是边集。（1）在图中任取一个顶点K作为开始点，令U=k，W=V-U，其中W为图中剩余顶点集。（2）找一个顶点在U中，另一个顶点在W中的边中最短的一条。找到后，将该边作为最小生成树的树边保存起来，并将该边顶点加入U集合中，并从W中删去这些顶点。（3）重复（2），直到W为空集止。6.4.2 最小生成树最小生成树普里姆算法是从最小生成树中顶点的角度出发来考虑的，因为图中有n个顶点，按照生成树的定义，所有的顶点都必须加入到最小生成树中，所以除去最初选定的顶点剩余的n-1个顶点在加入到最小生成树的过程中可以选择n-1条边加入到最小生成树的边集中，至此，我们就得到了图G的最小生成树。图6.18展
45、示了运用普里姆算法构造最小生成树的过程。(a)(b)(c)(d)(e)(f)(g)6.4.2 最小生成树最小生成树6.4.2 最小生成树最小生成树记录从顶点集U到V-U的代价最小的边需要设置一个辅助数组MinEdge，定义如下：struct VerType vex;/U中的顶点 ArcType lowcost;/边的权值MinEdgeMaxVerNum;下面算法6.12是用Prim算法从顶点V出发构造图G的最小生成树。（注：图G采用邻接矩阵的存储方式。）void PrimCreateMinTree(Graph G,int v)for(k=0;kG.vexnum;k+)if(k!=v)MinEd
46、gek=v,G.arcskv;MinEdgev.lowcost=0;for(i=0;iG.vexnum;i+)m=minCost(MinEdgei);/cost赋值被加入到生成树中的下一个顶点其中，minCost方法是选取边集中权值最小的并且确定其顶点 printf(MinEdgem.adjvex,G.vexsm);/输出打印生成树的一条边 MinEdgem.lowcost=0;/将顶点m加入到U中 for(j=0;jG.vexnum;j+)if(G.arcsmjj MinEdgej.lowcost)/新顶点并入U中重新选择权值最小边MinEdgej=G.vexsm,G.arcsmj/end
47、of PrimCreateMinTree6.4.2 最小生成树最小生成树普里姆算法中，我们用到了嵌套for循环，其中外层for循环用于寻找当前权值最小的边的顶点，内层for循环是修改顶点的最小边。我们可以看出普里姆算法的时间复杂度为O(n2)。显然其时间复杂度只与图的顶点数目有关，与边数无关。因此，普里姆算法适用于求边比较多的稠密图的最小生成树。表6.1给出了在用算法6.12构造图6.18的图G11的最小生成树的过程中，数组MinEdge的vex和lowcost、集合U和W的变化情况。vi MinEdge v2v3v4v5v6v7UV-Uminlengthvexlowcostv118000v1
48、2v14 v1 v2，v3，v4，v5，v6，v72vexlowcostv11800v690v14 v1，v6 v2，v3，v4，v5，v74vexlowcostv71300v6900 v1，v6，v7 v2，v3，v4，v5 9vexlowcostv7130v51000 v1，v5，v6，v7 v2，v3，v4 1vexlowcostv713v450000 v1,v4，v5，v6，v7 v2，v35vexlowcostv71300000v1，v3，v4，v5，v6，v7 v213vexlowcost000000v1，v2，v3，v4，v5，v6，v7 6.4.2 最小生成树最小生成树2.克鲁
49、斯卡尔（Kruskal）算法生成最小生成树普里姆算法的时间复杂度是O（n2），只与网的顶点数有关。而克鲁斯卡尔算法的时间复杂度是O（eloge），其中e为网的边数。因此，相比较而言，普里姆算法适用于稠密图，克鲁斯卡尔算法适用于稀疏图。从时间复杂度可以看出，克鲁斯卡尔算法是从边的角度求网的最小生成树。克鲁斯卡尔算法的基本思想:(1)将图中所有边按权值递增顺序排列；(2)依次选取权值较小的边，但要求后面选取的边不能与前面选取的边构成回路，若构成回路，则放弃该条边，再去选后面权值较大的边；n个顶点的图中，选够n-1条边即可。6.4.2 最小生成树最小生成树下图6.19 是图6.18(a)带权无向图的
50、克鲁斯卡尔算法构造最小生成树的过程。(a)(b)(c)(d)(e)(f)6.4.2 最小生成树最小生成树为了实现克鲁斯卡尔算法，我们设置一个结构数组来存储图中所有的边，具体定义如下：#define MaxArcNum 20 /定义图的最大边数#define MaxVerNum 10 /定义图的最大顶点数typedef structVerType vexhead;/定义一条边的一个顶点VerType vexTail;/定义一条边的另一个顶点int weight;/该边的权值ArcType,totalArcMaxArcNum;6.1 图的定义和基本术语6.2 图的存储方式6.3 图的遍历6.4 图
