《第7章图结构》习题解答要点

1、第7章图结构第7章图结构本章学习要点 熟悉图的定义、相关术语以及基本概念 熟练掌握图的4种存储结构，能根据实际问题选择合适的存储结构 熟练掌握图的两种遍历方法 理解并掌握最小生成树意义和两种算法 理解并掌握查找最短路径的有关算法 理解并掌握拓扑排序的有关算法 理解并掌握查找关键路径的有关算法在计算机科学、工程以及其它许多学科中，常常需要研究数据对象之间的各种关系。比 如，可以用线性表来表示数据对象之间的线性关系，用树结构来表示数据对象之间的某种层 次关系。但是，还有许多问题(比如信息通信网络)中的数据对象是不能用以上两种关系来 明确表示的，这就需要一种更为复杂的数据结构一图结构。图结构可以用来

2、表示数据对象之间的任意关系，图中的每个结点都可以和其它任一结点相连接，即图中数据对象之间的对应 关系是多个对多个”的关系。本章将详细介绍图的基本概念、各种存储结构、遍历方法，求图的连通分量、生成树、 最短路径，最后介绍一些有关图的应用问题。7.1 图的定义和基本术语7.1.1 图的定义图g(graph)是由两个集合v和vr组成，记为g=(v,vr)。v是顶点的有穷非空集合；vr是定义在v上的所有关系(两个不同顶点之间的弧或边)的集合。vr可以是空集合，当 vr为空集时g表示集合类结构类型。如图7.1(a)、(b)所示的是一个有向图和一个无向图。g)有向图s)无向图图了 1图的雪例7.1.2 图

3、结构的基本术语(1)顶点(vertex)图中的数据元素。比如，图 7.1中的顶点有：v1,v2,v3,v4,v5,v6。(2)弧(arc)设vr是图中所有顶点之间的关系集，若 6vr,则表示从顶点 v到顶点w的一条弧。例如，在图 7.1(a)所示的图 g 中的弧有：, 和 , 共 8 条弧。(3)弧尾(tail)弧的起始点。(4)弧头(head)弧的终端点。一条弧用有序对符号“瓠尾，弧头 ”来表示。(5)有向图(digraph)由顶点和弧组成的图称为有向图。比如，图7.1(a)表示一个有向图。(6)边(edge)设vr是图中所有顶点之间的关系集，若 6 vr必有 6 vr,则以无 序对符号(v

4、,w)或(w,v)来代替和,表示顶点v与顶点w之间的一条边。例如，在图 7.1(b)所示的图 g 中的边有：(v1,v2),(v1,v4),(v2,v3),(v2,v6),(v3,v5),(v4,v5)和 (v5,v6)共7条边。(7)无向图(undigraph)由顶点和边组成的图称为无向图。比如，图7.1(b)表示一个无向图。(8)完全图(completed graph)用n表示图中的顶点数，则具有 n(n-1)/2条边的无向图称为 无向完全图；具有n(n-1)条弧的有向图称为 有向完全图。当图g中边(或弧)的总数e满足：e n log n时称其为 稠密图(densegraph)o显然，完全

5、图是稠密图，反之不然。图 而图7.2(b)则是由3个顶点组成的有向完全图。7.2(a)所示为由4个顶点组成的无向完全图,口)无向完全图 也有向完全图 图7 2完全图示例-.169.-(9)权(weight)与图的边或弧相关的数(比如长度)称为权。(10)网(network)具有权值的图称为网，带权的有向图称为 有向网，带权的无向图称为 无向网。比如，图7.3(a)表示的是一个有向网，而图7.3(b)表示的是一个无向网。la)有向网cb)无向网图丁3网示例(11)子图(subgraph)假设有两个图g=(v,e)和g =(v ,e),若v七v并且e,=e,则称g 是g的子图。例如，图7.4(a)

6、为有向图及其部分子图，图7.4(b)为无向图及其部分子图。“1|上)无向图子图2子图1e7.4(12)邻接点(adjacent)对于无向图有向图和无向图的子图示例g=(v,vr),若边(v,w) vr,则称v和w互为邻接点,边(v,w)依附(incident)于顶点v和w,或者说边(v,w)与顶点v、w相关联。对于有向图g=(v,v r),若弧 vr,则称顶点v邻接到顶点w ,顶点w邻接自顶点v。(13)度(degree)在无向图中，顶点 v的度是指和v相关联的边的数目，记为(14)出度(out degree)和入度(in degree)在有向图中，顶点 v的出度是指以的数目，记为 od(v)

7、;顶点v的入度是指以v为弧头的弧的数目，记为id(v);td(v)。v为弧尾的弧顶点v的度是指v的出度、入度的和，记为td(v)。一般地，如果顶点vi的度记为td(v i), 足关系如下：那么一个有n个顶点e条边(或弧)的图，必定满17 td v)2 i0(15)路彳5 (path)在图中，从顶点 v到顶点w的顶点序列称为路径。显然，有向图的路径是有向的。路径长度 是指路径上的边或弧的数目。序列中顶点不重复出现的路径称为径。(16)回路或环(cycle)在路径的顶点序列中，第一个顶点和最后一个顶点相同的路径称为简单路回路。除了第一个顶点和最后一个顶点外，其余顶点均不重复出现的回路称为 单环。例

8、如，在图7.4(a)所示的有向图中，顶点序列 m,mw)表示一简单回路或简条有向路径，由于其中存在重复点vi所以不是简单路径，该路径的长度为4；顶点序列(vi,v3,v4)表示一条有向路径，并且是长度为2的简单路径；顶点序列(vi,v3,v4,v1)表示一条有向路径并且是长度为3的简单回路(或环)。在图7.4(b)所示的无向图中，顶点序列(vi,v3,v5,v4,v3,v5,v2)表示一条路径，由于其 中存在重复点v3、v5所以不是简单路径；顶点序列(vi,v3,v4,v5,v2,v1)是长度为5的简单回路。(17)连通图(connected graph)在无向图g=(v,vr)中，如果从顶点

9、 v到顶点w有路径，则 称v与w是连通的。如果对于任意两个顶点v,w c v都是连通的则称 g是连通图。(18)连通分量(connected component)无向图g中的极大连通子图称为 g的连通分量。图7.5给出一个无向图和它的3个连通分量的示例。()的3个连通分量无向非连通图g无向非连通图和它的3个连逋分量(19)强连通图 在有向图g=(v,vr)中，如果对于任意两个顶点v,wcv,都存在一条v到w第7章图结构的路径，则称 g是强连通图；如果对于任意两个顶点 v,wcv,都存在一个顶点序列：v=v0,vl,v2,，v=w 满足 或 e vr,则称 g是弱连通图。例如，图7.1(a)为弱

10、连通图,图7.2(b)为强连通图。(20)强连通分量 有向图g中的极大强连通子图称为g的强连通分量。图7.6给出一个有向图和它的2个强连通分量的示例。3)有向非连通图g也)g的2个强连通分星e7.6有向非连逋图和它的2个覆连逋分量-.173 .-说明：在连通分量和强连通分量定义中的极大”应理解为包含依附于该连通子图或强连通子图中顶点的所有边或弧。(21)生成树一个无向连通图的生成树是一个 极小连通子图，即它包含图中的所有(假设 n个)顶点，但是只有足以构成一棵树的n-1条边。说明：1 ) 一个无向连通图的生成树不是唯一的，所有生成树的顶点相同但是所包含的边可以不 同。2) 一棵有n个顶点的连通

11、图的生成树有且仅有n-1条边。但是有 n个顶点和n-1条边的无向图不一定是生成树。例如，图7.7给出一个连通图(图7.7(a)和它的3棵生成树(图7.7(b)的示例。(22)生成森林如果一个有向图 g恰有一个顶点的入度为 0,其余顶点的入度均为 1,则g是一棵有向树。一个有向图的生成森林由若干棵有向树组成，森林中含有图中全部顶点、但是只有足以包戈芍于愣丕出交也有回村.町弧.。显然,一个有向图生成的有向树或生成森林都 不是唯一的。e如)有向图gs7.3有向图生成有向树和森林的示图关于顶点位置”的说明：在图的基本操作定义中， 其 顶点位置”和 邻接点位置”仅是一个相对的概念。 从图的定义可以看出，

12、图中所有顶点的位置都是平等的，可以将任意一个顶点看成是第一个或最后一个顶点，也无法将其排列成一个线性序列或层次关系。在实际操作中，为了方便起见，需要将所有顶点按照某个任意选定的顺序排列起来(排列与图中顶点之间的关系无关)。所以，顶点在图中的位置”是指该顶点在这个人为的随意排列中的位置(或序号)。同理，可以对某个顶点的所有邻接点按照某个任意选定的顺序进行排列。2 .1.3图的基本操作对于图结构，常用的操作有以下几种：(1)创建creategraph(&g,v,vr)根据顶点集v和关系(边或弧)集 vr构造图g;(2)查找locatevex(g,u)函数功能是，如果图g中存在信息等于u的顶点则返回

13、该顶点在g中的位置，否则返回0;(3)提取getvex(g,v)函数功能是，返回图 g中顶点v的信息；(4)修改putvex(&g ,v,value)函数功能是，修改图 g中顶点v的信息为value;(5)邻接点firstadjvex(g ,v)函数功能是，返回图 g中顶点v的第一个邻接点在 g中的位 置，操作不成功时返回0;(6)下一个邻接点 nextadjvex(g ,v,w)函数中v,w是图g的顶点，且w是v的一个邻接点。 函数功能是，返回顶点 v相对于w的下一个邻接点所在的位置，如果 w是v的最后一个邻接 点则返回0;(7)插入顶点insertvex(&g ,v)函数功能是，在图 g中

14、插入顶点v;(8)删除顶点deletevex(&g,v)函数功能是，在图g中删除顶点v以及相关的边或弧；(9)插入弧insertarc(&g ,v,w)函数功能是，在图 g中增加边(v,w)或弧;(10)删除弧deletearc(&g ,v,w)函数功能是，在图 g中删除边(v,w)或弧 ;(11)深度优先遍历dsftraverse(g,v,visit()函数功能是，从顶点v开始按深度优先遍历图g,其中visit()是关于顶点的操作函数；(12)广度优先遍历 bsftraverse(g,v,visit()函数功能是，从顶点v开始按广度优先遍历图 g,其中visit()是关于顶点的操作函数。7.

15、2图的存储表示与实现图是一种复杂结构其存储方法也比较多，在实际应用中，一般需要根据具体的图形和要 进行的操作来选取适当的存储结构。图的常用存储结构有：邻接矩阵表示法、邻接表表示法、 十字链表表示法和多重链接表表示法。7.2.1 邻接矩阵表示法邻接矩阵表示法是图的一种顺序存储表示法。用两个数组分别存储数据元素(顶点)的 信息和元素之间所存在的关系(边或弧)的信息。该表示法既可用于表示无向图也可用于表示有 向图。1 .邻接矩阵的定义设g=(v,vr)是一个图，含有n个顶点，那么g的邻接矩阵是表示 g中顶点之间相邻关系 的n阶方阵anw,下面分别根据有权图和无权图给出矩阵a的定义。如果g是无权图，则

16、a的定义为：1(vi，vj) wvr或 wvrai j0其它情况如果g是有权图，则a的定义为：fwij(vi ,vj) wvr 或 wyr(权彳wj #0)ai j、0 其它情况(为操作统一此处用0而非)【例7.1】分别给出图7.1、图7.3中各图的邻接矩阵。7.9(a)、图7.9(b)所示；在图 排列时的邻接矩阵分别如图在图7.1(a)、图7.1(b)中，图的顶点顺序按vi,v2,v3,v4,v5,v6排列时的邻接矩阵分别如图a,b,c, d 和 a,b,c, d,e7.3(a)、图7.3(b)中，图的顶点顺序分别按7.9(c)、图 7.9(d)所示。01010000000010000100

17、10000001001000100101001010010i00i010001000110iaiooio0 70 00 09 0100000500p08dgoo3o00001283001001210无向图r有向网和无向网的邹媵炬阵表示显然，图的邻接矩阵有以下特点：(1)当图中顶点的排列顺序确定后，该图的邻接矩阵是唯一确定的；(2)无向图的邻接矩阵是对称的，可以采用压缩存储的方法仅存入其下三角(或上三角)部分的元素即可；n _1(3)在无向图中，顶点vi的度是其邻接矩阵a的第i行元素的和，即：td (v ) =z ai j；j =0(4)在有向图中，顶点vi的出度是其邻接矩阵 a的第i行元素的和

18、，而入度是a的第i列元n _1n -1素的和，所以vi的度可以表示为：td(vi)= ai j +z a ji (n为图中顶点的个数)j 0：j zq2.邻接矩阵的存储表示与实现(1)邻接矩阵的类型定义图的类型gkind有向图，有向网，无向图，无向网typedef enumdg,dn,udg,udngkind;第7章图结构typedef int vtype;struct vnodeint flag;vtype vex;struct mgraphvnode* vexs;vtype* arcs;int vexnum,arcnum;gkind kind;为便于操作，定义顶点类型 vtype为int型

19、/顶点与访问情况类型 vnode访问次数，顶点信息/定义图的邻接矩阵类型mgraph描述顶点的数组指针邻接矩阵的数组指针vexsarcs/顶点数vexnum和边或弧数 arcnum图的种类标志kind(2)查找图中顶点位置的操作函数的功能是，返回顶点u在图g中的位置，查找失败返回 0值。int locatevex_mg(mgraph g,vtype u) int i;for(i=0;ig .vexnum;i+)if(g.vexsi.vex=u) break;if(ig.vexnum)return(i+1);else return(0);(3)邻接矩阵的建立操作函数的功能是，根据图 g的种类标志

20、kind建立图#includeiostream.hvoid creategraph_mg(mgraph& g ,gkind kind)int i,j,k;vtype u,v;coutg.vexnumg .arcnum;g.kind=kind;g.vexs=new vnodeg .vexnum;g.arcs=new vtypeg.vexnum*g .vexnum;g的所有信息。为gvexs分配存储空间为g.arcs分配存储空间cout按某种顺序输入g .vexnum个顶点的值：n;for(i=0;ig.vexsi.vex;for(i=0;ig .vexnum;i+)for(j=0;jg .vex

21、num;j+)g.arcsi*g.vexnum+j=0;if(g.kind=dg|g .kind=udg)/flag=0表示该顶点未被访问/输入所有顶点的信息到g.vexs中/将图g的关系集garcs初始化为空集cout输入图中g.arcnum条边(弧)的信息u v:n;-.181.-elsecout输入图中g.arcnum条边(弧)和权的信息 u v w:n;for(k=0;kuv; 根据顶点信息找到所在位置while(!(i=locatevex_mg(g )&(j=locatevex_mg(g,v); i-,j-;/i,j从位置值转换为下标值g.arcsi*g.vexnum+j=1; if

22、(g.kind=dn|g .kind=udn) cing.arcsi*g .vexnum+j;/b入相应边或弧的权重 wif(g.kind=udg|g .kind=udn)无向图的邻接矩阵是对称的g.arcsj*g.vexnum+i=g .arcsi*g.vexnum+j; (4)显示输出邻接矩阵的操作函数功能是，显示输出图g的邻接矩阵 garcs。void displymg(mgraph g) int i,j;for(i=0;ig.vexnum;i+) for(j=0;jg .vexnum;j+)coutg.arcsi*g .vexnum+j ;coutendl;(5)演示程序主函数程序中分

23、别建立有向图g1、无向图g2、有向网g3和无向网g4的邻接矩阵，并显示输出每个邻接矩阵的数据信息。void main() mgraph g1,g2,g3,g4;gkind gk1=dg ,gk2=udg ,gk3=dn,gk4=udn;cout建立一个有向图的邻接矩阵g1:n;creategraph_mg(g1,gk1);cout建立一个无向图的邻接矩阵g2:n;creategraph_mg(g2,gk2);cout有向图g1的邻接矩阵为：n;displymg(g1);cout无向图g2的邻接矩阵为：n;displymg(g2);cout*n;cout建立一个有向网的邻接矩阵g3:n;crea

24、tegraph_mg(g3,gk3);cout建立一个无向网的邻接矩阵g4:n;creategraph_mg(g4,gk4);cout有向网g3的邻接矩阵为：n;displymg(g3);cout无向网g4的邻接矩阵为：n;displymg(g4);程序运行演示结果为：建立一个有向图的邻接矩阵g1:输入顶点数vexnum和弧数arcnum:6 8/按某种顺序输入6个顶点的值： 一1 2 3 4 5 6/输入图中8条边(弧)的信息u v:1 2 1 4 3 1 3 6 4 3 5 4 6 1 6 5/建立一个无向图的邻接矩阵g2:输入顶点数vexnum和弧数arcnum:6 7/按某种顺序输入6

25、个顶点的值：一1 2 3 4 5 6/输入图中7条边(弧)的信息u v:1 2 1 4 2 3 2 6 5 3 5 6 5 4/有向图g1的邻接矩阵为：0 1 0 1 0 00 0 0 0 0 01 0 0 0 0 10 0 1 0 0 00 0 0 1 0 00 1 0 0 1 0*建立一个有向网的邻接矩阵g3:输入顶点数vexnum和弧数arcnum:4 4/按某种顺序输入4个顶点的值：一1 2 3 4/输入图中4条边(弧)和权的信息u v w:1 2 7 1 3 1 3 4 5 4 1 9/建立一个无向网的邻接矩阵 g4:输入顶点数vexnum和弧数arcnum:5 5/按某种顺序输入5

26、个顶点的值：一1 2 3 4 5/输入图中5条边(弧)和权的信息u v w:1 2 9 4 1 8 4 2 3 4 5 1 3 5 12/有向网g3的邻接矩阵为：0 7 1 00 0 0 00 0 0 59 0 0 01 0 0 0 1 0无向图g2的邻接矩阵为：无向网g4的邻接矩阵为0 1 0 1 0 00 90 8 01 0 1 0 0 19 00 3 00 1 0 0 1 00 00 0 121 0 0 0 1 08 30 0 10 0 1 1 0 10 012 1 0说明：(1)程序演示中建立的是图7.1、图7.3中4个图的邻接矩阵:gl.arcs、g2.arcs、g3.arcs、g4

27、.arcs。从运行结果可以看出与图7.9的形式一致。(2)在图的邻接矩阵存储结构上也容易实现其它基本操作，比如，对于无向图g中返回顶点v的第一个邻接点位置的基本操作函数：int firstadjvex_mg(mgraph g,vtype v)。算法的实现过程是：1)根据顶点信息 v,通过调用函数int locatevex_mg(mgraph g,vtype v)找到v在g中的 位置i;2)在g的邻接矩阵中寻找第i行中第一个非零元素所在的列号j;3)如果j存在函数返回j+1,否则返回0值。类似地可以给出函数：int nextadjvex_mg(mgraph g ,vtype v,vtype w)

28、的算法实现代码。(3)用邻接矩阵表示有 n个顶点的图g时，查找边(或弧)的时间复杂度为o(n2)。由于邻接矩阵的存储空间仅与顶点数n有关，而与边无关，因此，当图 g的顶点较多而边数又很少时，其边的查找效率会很低。为此，下面给出图的另一种存储结构，即图的邻接表表示法。7.2.2邻接表表示法图的邻接表表示是把图的每个顶点的邻接顶点用一个链表来表示。一般地，用顺序存储的方式来表示图中n个顶点的信息，另外，对图中每个顶点v建立一个单链表，用于表示与 v相邻接的所有顶点的位置（下标）。链表中每个结点有两个域值：一个是顶点位置（下标）域， 用于表示该邻接点的序号；另一个是指针域，用于指向下一个邻接点。1

29、.邻接表的定义（1）表结点 在邻接表中，对图中的每个顶点建立一个单链表，顶点v所对应的单链表中的结点（表示依附于该顶点的边或以v为尾的弧）称为 表结点。图的表结点中包含有顶点位置域（adjvex）、指向下一条边（弧）的指针域（nextarc）；而网的表结点中还要有表示相应权值 的域（weight）。（2）头结点 在邻接表中每个单链表上附设一个结点，称为头结点。每个头结点由 3个域 组成：结点信息域（data）、结点访问次数域（flag）和指向链表中第一个结点的指针域 （nextarc）。 图中的所有头结点以顺序结构存储。在图7.10中分别给出邻接表表结点的结构示图（a）和头结点的结构示图（b）

30、oadjvexwe ii ghtnextarcdataflagnext-arc邻接栽培点结构3）头结点结构图7.1口邻接表的结点结构示图例如，图7.11分别给出有向图 g1和无向图g2的一种邻接表表示结构。口有向图g1吼及g1的一种翎接表表示匡11图的鄂接表表亭本例由于图中顶点的排列次序可以不同，每个顶点的邻接点的排列顺序也可以不同，所以， 一个图的邻接表表示不唯一。用邻接表表示具有 n个顶点和e条边的无向图时，需要一个由n个元素组成的顺序表（表 头结点表）和由2e个结点组成的n个单链表。而表示 n个顶点和e条弧的有向图时，需要一 个由n个元素组成的顺序表和由 e个结点组成的n个单链表。当图中

31、边（或弧）的数目远远少 于图的顶点数目时，邻接表所需的存储空间要比邻接矩阵所需的少。2 .逆邻接表在图g的邻接表中，顶点 v的相邻元素可以通过遍历该顶点对应的单链表求得，设该链表中结点的个数为 k那么，g为无向图时k表示v的度，g为有向图时k表示v的出度。如果 求顶点v的入度，则需要遍历邻接表中的所有单链表，统计与v的序号相同的结点个数。这样处理很不方便，为此，仿照邻接表，建立一个逆邻接表，即对每个顶点 v建立一个单链表，把所有邻接于v的顶点链接在一起，此时该单链表的长度即为v的入度。例如，图7.11(a)所示的有向图可用逆邻接表表示为图7.12。117.12有向图的法郭授表表示3.邻接表的存

32、储表示与实现(1)邻接表存储结构的类型定义定义单链表结点类型arcnode :struct arcnode int adjvex,weight;arcnode* nextarc;定义链表头结点结构类型vexnode:struct vexnodevtype data;int flag;arcnode* nextarc;定义邻接表存储结构的类型algraph :struct algraphvexnode* vertices;/定义头结点数组指针 verticesint vexnum,arcnum;顶点数 vexnum 和边或弧数 arcnumgkind kind;图的种类标志kind;(2)查找图

33、中顶点位置的操作函数的功能是，返回顶点 u在图g中的位置，查找失败返回0值。int locatevex_al(algraph g ,vtype u) int i;for(i=0;ig .vexnum;i+)if(g.verticesi.data=u) break;if(ig.vexnum)return(i+1);else return(0); (3)邻接表的建立操作函数的功能是，根据图 g的种类标志kind建立g的邻接表表示的存储结构。#includeiostream.hvoid creategraph_al(algraph& g ,gkind kind) int i,j,k;vtype u,

34、v;arcnode* pr,*pr1;g.kind=kind;coutg.vexnumg .arcnum; g.vertices=new vexnodeg .vexnum;为顶点数组分配内存空间cout按某种顺序输入g .vexnum个顶点的值：n; for(i=0;ig.verticesi.data;/输入所有顶点的信息到 vex中g.verticesi.nextarc=null;设定初始的单链表为空 if(g.kind=dg|g .kind=udg) cout输入图中g.arcnum条边(弧)的信息u v:n; else cout输入图中g.arcnum条边(弧)和权的信息 u v w:n

35、; for(k=0;kuv; while(!(i=locatevex_al(g )&(j=locatevex_al(g ,v); i-,j-;/i,j从位置值转换为下标值pr=new arcnode;动态分配单链表结点 prpr-adjvex=j; pr-weight=0; if(g.kind=dn|g .kind=udn)cinpr-weight;/输入对应边(弧)的权值pr-nextarc=g.verticesi.nextarc;将结点pr插入到第i个链表的首部g.verticesi.nextarc=pr; if(g.kind=udg|g .kind=udn) /对于无向图(或网)将结点p

36、r1插入到第j个链表的首部 pr1=new arcnode;/动态分配单链表结点 pr1pr1-adjvex=i; pr1-weight=pr-weight; pr1-nextarc=g .verticesj.nextarc; g.verticesj.nextarc=pr1;将结点pr1插入到第j个链表的首部/end switch /end for (4)显示输出邻接矩阵的操作 函数功能是，显示输出图g的邻接链表中的所有信息。void displyal(algraph g)/ 显示邻接矩阵 g int i;arcnode* p;for(i=0;ig .vexnum;i+) p=g.vertic

37、esi.nextarc;couti (g .verticesi.data):; while(p) if(g .kind=dg|g .kind=udg) coutadjvex;else/对于图仅输出顶点的下标值/对于网要输出下标与对应的权的值couttadjvex,weightnextarc;coutendl;/end for(5)演示程序主函数程序中分别建立有向图 g1、无向图g2、有向网g3和无向网g4的邻接表，并显示输出 所建立的每个邻接表的数据信息。void main() algraph g1,g2,g3,g4;gkind gk1=dg ,gk2=udg ,gk3=dn,gk4=udn;

38、cout建立一个有向图的邻接表creategraph_al(g1,gk1);cout建立一个无向图的邻接表creategraph_al(g2,gk2);cout有向图g1的邻接表为:n;displyal(gi);cout”无向图g2的邻接表为：n;displyal(g2);g1:n;g2:n;cout*n;cout建立一个有向网的邻接表creategraph_al(g3,gk3);cout建立一个无向网的邻接表creategraph_al(g4,gk4);cout有向网g3的邻接表为：n;displyal(g3);cout无向网g4的邻接表为：n;displyal(g4);程序运行演示结果为：

39、建立一个有向图的邻接表 g1:g3:n;g4:n;输入顶点数和边(弧)数vexnum arcnum:6 8 /第7章图结构按某种顺序输入6个顶点的值：1 2 3 4 5 6/输入图中8条边(弧)的信息u v:1 2 1 4 3 1 3 6 4 3 5 4 6 1 6 5/建立一个无向图的邻接表g2输入顶点数和边(弧)数vexnum arcnum:6 7 /按某种顺序输入6个顶点的值：1 2 3 4 5 6/输入图中7条边(弧)的信息u v:1 2 1 4 2 3 2 6 5 3 5 6 5 4/有向图g1的邻接表为：0 (1)： 3 11 (2)：2 (3): 5 03 (4): 24 (5)

40、: 35 (6): 4 0无向图g2的邻接表为：0 (1): 3 11 (2): 5 2 02 (3): 4 13 (4): 4 04 (5): 3 5 25 (6): 4 1说明：*建立一个有向网的邻接表g3:输入顶点数和边(弧)数vexnum arcnum:4 4 /按某种顺序输入4个顶点的值：1 2 3 4/输入图中4条边(弧)和权的信息u v w:1 2 7 1 3 1 3 4 5 4 1 9/建立一个无向网的邻接表g4:输入顶点数和边(弧)数vexnum arcnum:5 5 /按某种顺序输入5个顶点的值：1 2 3 4 5/输入图中5条边(弧)和权的信息u v w:1 2 9 4

41、1 8 4 2 3 4 5 1 3 5 12/有向网g3的邻接表为：0 (1)： 2,1 1,71 (2)：2 (3): 3,53 (4): 0,9无向网g4的邻接表为：0 (1)： 3,8 1,91 (2)： 3,3 0,92 (3): 4,123 (4): 4,1 1,3 0,84 (5): 2,12 3,1-.183.-(1)程序演示中建立的是图7.1、图7.3中4个图的一种邻接表表示：g1.vertices、g2.verticesg3.vertices 和 g4.vertices。(2)在程序显示的结果中，第一列为顶点的下标，第二列为图中所有顶点的值。对于图， 单链表中的每一项表示该顶

42、点的邻接点的下标；对于网，单链表中的每一项表示该顶点的邻 接点的下标值和相应边(弧)的权值。(3)在建立邻接表时，由于输入的是顶点信息，所以要先通过查找求得该顶点在图中的位置，再将相应结点插入到对应单链表的首部，所以，该操作的时间复杂度为o(n*e)。7.2.3有向图的十字链表表示法十字链表是有向图的另一种链式存储结构，该方法是将有向图的邻接表和逆邻接表结合 起来得到的一种链表。1.十字链表的定义7.13给出十类似邻接表，在十字链表中包含链表的头结点和弧结点两种类型的结点，图 字链结点结构的示图。tai i vex head vex hi i nk 11i nk i n千口品 忏 i rsti

43、n + i rstout|g)头皓点结构)迎堵点结构图丁 13 十字选会的结点结构其中，头结点包含顶点信息域(data)、指向以该顶点为弧头的第一个弧结点的指针域(firstin)、指向以该顶点为弧尾的第一个弧结点的指针域(firstout),表的所有头结点以顺序存储。弧结点包含表示弧尾顶点下标的尾域(tailvex) 表示弧头顶点下标的头域 (headvex)、指向弧头相同的下一条弧的指针域 (hlink)、指向弧尾相同的下一条弧的指针域(tlink)、弧的信息(如权第7章图结构值)域(info)。例如，图7.14给出有向图的一种十字链表表示。0图7 14有向图的十字能益表示示例-.185.

44、-2.十字链表的存储表示与实现(1)十字链表存储结构的类型定义下面分别给出十字链弧结点 定义。struct arcboxinttailvex,headvex;arcbox *hlink,*tlink;intweight;struct olvexnodevtypedata;arcbox*firstin,*firstout;struct olgrapholvexnode *xlist;int vexnum,arcnum;gkind kind;(2)十字链表的查找操作函数int败则返回int如果将有向图的邻接矩阵看成是稀疏矩阵的话，则十字链表也可以看成是邻接矩阵的十 字链表存储结构。在有向图的十字链

45、表表示中，链表的头结点之间是顺序存储结构，弧结点 所在的链表是非循环链表，结点之间的相对位置自然形成，不一定按顶点序列号有序。由此 可见，有向图的十字链表表示方式是不唯一的。(arcbox)、顶点结点(olvexnode)、十字链表(olgraph)的类型/弧结点的结构定义/定义弧尾和弧头顶点的位置/弧头相同、弧尾相同的弧的链域/定义有向网中弧的权值顶点结点结构定义顶点信息/分别指向顶点的第一条入弧和出弧定义十字链表类型链表头结点数组指针有向图的顶点数和弧数locatevex_olg(olgraph g ,vtype u)返回顶点u在图g中的位置，如果查找失 0值。locatevex_olg(

46、olgraph g ,vtype u) int i;for(i=0;ig .vexnum;i+) if(g .xlisti.data=u)break;if(ig.vexnum)return(i+1);else return(0); (3)建立十字链表的算法实现函数 void creategraph_olg(olgraph& g ,gkind kind)根据图的类型 kind 建立一个有向图 或有向网的十字链表 govoid creategraph_olg(olgraph& g,gkind kind) int i,j,k；vtype u,v;arcbox* pr;g.kind=kind;cout

47、g.vexnumg .arcnum;g.xlist=new olvexnodeg .vexnum;为顶点数组分配内存空间cout按某种顺序输入g .vexnum个顶点的值：n;for(i=0;ig.xlisti.data;g.xlisti.firstin=g .xlisti.firstout=null;if(g.kind=dg)cout输入图中g.arcnum条弧的信息 u v:n;else cout输入图中g.arcnum条弧和权的信息 u v w:n; for(k=0;kuv; while(!(i=locatevex_olg(g ,u)&(j=locatevex_olg(g ,v);动态分

48、配弧存储空间/i从位置值转换为下标值/j从位置值转换为下标值/将输入的弧插入到相应链表的首部pr=new arcbox;pr-tailvex=-i;pr-headvex=-j;if(g.kind=dn)cinpr-weight;pr-hlink=g .xlistj.firstin;g.xlistj.firstin=pr;pr-tlink=g .xlisti.firstout;g.xlisti.firstout=pr;/end for(4)显示十字链表信息的操作g的信函数void displyolg(olgraph g)分别按邻接表和逆邻接表方式显示当前十字链表 息。void displyolg

49、(olgraph g) int i;arcbox* p;cout按邻接表显示结果为：n;for(i=0;ig .vexnum;i+) p=g.xlisti.firstout;couti (g .xlisti.data):;while(p) couttailvex headvex;if(g .kind=dn)cout weight;couttlink;coutendl;/end forcout按逆邻接表显示结果为：n;for(i=0;ig .vexnum;i+) p=g.xlisti.firstin;couti (g .xlisti.data):;while(p) couttailvex headvex;if(g .kind=dn)cout weight;couthlink;coutendl;/end for(5)程序演示主程序代码程序中分别建立一个有向图g1和一个有向网g2的十字链表，并按邻接表和逆邻接表两种形式显示所建立的的十字链表的内容。void main() olgraph g1,g2;gkind gk1=dg ,gk2=dn;cout