第7章 图结构习题解答.doc

第7章 图结构第7章 图 结 构本章学习要点熟悉图的定义、相关术语以及基本概念熟练掌握图的4种存储结构，能根据实际问题选择合适的存储结构熟练掌握图的两种遍历方法理解并掌握最小生成树意义和两种算法理解并掌握查找最短路径的有关算法理解并掌握拓扑排序的有关算法理解并掌握查找关键路径的有关算法在计算机科学、工程以及其它许多学科中，常常需要研究数据对象之间的各种关系。比如，可以用线性表来表示数据对象之间的线性关系，用树结构来表示数据对象之间的某种层次关系。但是，还有许多问题（比如信息通信网络）中的数据对象是不能用以上两种关系来明确表示的，这就需要一种更为复杂的数据结构图结构。图结构可以用来表示数据对象之间的任意关系，图中的每个结点都可以和其它任一结点相连接，即图中数据对象之间的对应关系是“多个对多个”的关系。本章将详细介绍图的基本概念、各种存储结构、遍历方法，求图的连通分量、生成树、最短路径，最后介绍一些有关图的应用问题。7.1图的定义和基本术语7.1.1图的定义图G(graph) 是由两个集合V和VR组成，记为G=(V,VR)。V是顶点的有穷非空集合；VR是定义在V上的所有关系（两个不同顶点之间的弧或边）的集合。VR可以是空集合，当VR为空集时G表示集合类结构类型。如图7.1(a)、(b)所示的是一个有向图和一个无向图。7.1.2图结构的基本术语（1）顶点(Vertex) 图中的数据元素。比如，图7.1中的顶点有：v1,v2,v3,v4,v5,v6。（2）弧(Arc) 设VR是图中所有顶点之间的关系集，若VR，则表示从顶点v到顶点w的一条弧。例如，在图7.1(a)所示的图G中的弧有：,和,共8条弧。（3）弧尾(Tail) 弧的起始点。（4）弧头(Head) 弧的终端点。一条弧用有序对符号“”来表示。（5）有向图(Digraph) 由顶点和弧组成的图称为有向图。比如，图7.1(a)表示一个有向图。（6）边(Edge) 设VR是图中所有顶点之间的关系集，若VR必有VR，则以无序对符号(v,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满足：时，称其为稀疏图(sparse graph)；当e满足：时称其为稠密图(dense graph)。显然，完全图是稠密图，反之不然。图7.2(a)所示为由4个顶点组成的无向完全图，而图7.2(b)则是由3个顶点组成的有向完全图。（9）权(Weight) 与图的边或弧相关的数（比如长度）称为权。（10）网(Network) 具有权值的图称为网，带权的有向图称为有向网，带权的无向图称为无向网。比如，图7.3(a)表示的是一个有向网，而图7.3(b)表示的是一个无向网。（11）子图(Subgraph) 假设有两个图G=(V,E)和G=(V,E)，若VV并且EE，则称G是G的子图。例如，图7.4(a)为有向图及其部分子图，图7.4(b)为无向图及其部分子图。（12）邻接点(Adjacent) 对于无向图G=(V,VR)，若边(v,w)VR，则称v和w互为邻接点，边(v,w)依附(Incident)于顶点v和w，或者说边(v,w)与顶点v、w相关联。对于有向图G=(V,VR)，若弧VR，则称顶点v邻接到顶点w，顶点w邻接自顶点v。（13）度(Degree) 在无向图中，顶点v的度是指和v相关联的边的数目，记为TD(v)。（14）出度(Out degree)和入度(In degree) 在有向图中，顶点v的出度是指以v为弧尾的弧的数目，记为OD(v)；顶点v的入度是指以v为弧头的弧的数目，记为ID(v)；顶点v的度是指v的出度、入度的和，记为TD(v)。一般地，如果顶点vi的度记为TD(vi)，那么一个有n个顶点e条边（或弧）的图，必定满足关系如下：（15）路径(Path) 在图中，从顶点v到顶点w的顶点序列称为路径。显然，有向图的路径是有向的。路径长度是指路径上的边或弧的数目。序列中顶点不重复出现的路径称为简单路径。（16）回路或环(Cycle) 在路径的顶点序列中，第一个顶点和最后一个顶点相同的路径称为回路。除了第一个顶点和最后一个顶点外，其余顶点均不重复出现的回路称为简单回路或简单环。例如，在图7.4(a)所示的有向图中，顶点序列(v1,v3,v4,v1,v2)表示一条有向路径，由于其中存在重复点v1所以不是简单路径，该路径的长度为4；顶点序列(v1,v3,v4)表示一条有向路径，并且是长度为2的简单路径；顶点序列(v1,v3,v4,v1)表示一条有向路径并且是长度为3的简单回路（或环）。在图7.4(b)所示的无向图中，顶点序列(v1,v3,v5,v4,v3,v5,v2)表示一条路径，由于其中存在重复点v3、v5所以不是简单路径；顶点序列(v1,v3,v4,v5,v2,v1)是长度为5的简单回路。（17）连通图(Connected graph) 在无向图G=(V,VR)中，如果从顶点v到顶点w有路径，则称v与w是连通的。如果对于任意两个顶点v,wV都是连通的则称G是连通图。（18）连通分量(Connected component) 无向图G中的极大连通子图称为G的连通分量。图7.5给出一个无向图和它的3个连通分量的示例。（19）强连通图 在有向图G=(V,VR)中，如果对于任意两个顶点v,wV，都存在一条v到w的路径，则称G是强连通图；如果对于任意两个顶点v,wV，都存在一个顶点序列：v=v0,v1,v2,vk=w满足或VR，则称G是弱连通图。例如，图7.1(a)为弱连通图，图7.2(b)为强连通图。（20）强连通分量 有向图G中的极大强连通子图称为G的强连通分量。图7.6给出一个有向图和它的2个强连通分量的示例。说明：在连通分量和强连通分量定义中的“极大”应理解为包含依附于该连通子图或强连通子图中顶点的所有边或弧。（21）生成树 一个无向连通图的生成树是一个极小连通子图，即它包含图中的所有（假设n个）顶点，但是只有足以构成一棵树的n-1条边。说明：1）一个无向连通图的生成树不是唯一的，所有生成树的顶点相同但是所包含的边可以不同。2）一棵有n个顶点的连通图的生成树有且仅有n-1条边。但是有n个顶点和n-1条边的无向图不一定是生成树。例如，图7.7给出一个连通图(图7.7(a)和它的3棵生成树(图7.7(b)的示例。（22）生成森林 如果一个有向图G恰有一个顶点的入度为0，其余顶点的入度均为1，则G是一棵有向树。一个有向图的生成森林由若干棵有向树组成，森林中含有图中全部顶点，但是只有足以构成若干棵不相交的有向树的弧。显然，一个有向图生成的有向树或生成森林都不是唯一的。关于“顶点位置”的说明：在图的基本操作定义中，其“顶点位置”和“邻接点位置”仅是一个相对的概念。从图的定义可以看出，图中所有顶点的位置都是平等的，可以将任意一个顶点看成是第一个或最后一个顶点，也无法将其排列成一个线性序列或层次关系。在实际操作中，为了方便起见，需要将所有顶点按照某个任意选定的顺序排列起来（排列与图中顶点之间的关系无关）。所以，“顶点在图中的位置”是指该顶点在这个人为的随意排列中的位置（或序号）。同理，可以对某个顶点的所有邻接点按照某个任意选定的顺序进行排列。7.1.3图的基本操作对于图结构，常用的操作有以下几种：（1）创建CreateGraph(&G,V,VR) 根据顶点集V和关系（边或弧）集VR构造图G；（2）查找LocateVex(G,u) 函数功能是，如果图G中存在信息等于u的顶点则返回该顶点在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中插入顶点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.2 图的存储表示与实现图是一种复杂结构其存储方法也比较多，在实际应用中，一般需要根据具体的图形和要进行的操作来选取适当的存储结构。图的常用存储结构有：邻接矩阵表示法、邻接表表示法、十字链表表示法和多重链接表表示法。7.2.1邻接矩阵表示法邻接矩阵表示法是图的一种顺序存储表示法。用两个数组分别存储数据元素（顶点）的信息和元素之间所存在的关系(边或弧)的信息。该表示法既可用于表示无向图也可用于表示有向图。1邻接矩阵的定义设G=(V,VR)是一个图，含有n个顶点，那么G的邻接矩阵是表示G中顶点之间相邻关系的n阶方阵Ann，下面分别根据有权图和无权图给出矩阵A的定义。如果G是无权图，则A的定义为：如果G是有权图，则A的定义为：【例7.1】分别给出图7.1、图7.3中各图的邻接矩阵。在图7.1(a)、图7.1(b)中，图的顶点顺序按排列时的邻接矩阵分别如图7.9(a)、图7.9(b)所示；在图7.3(a)、图7.3(b)中，图的顶点顺序分别按和排列时的邻接矩阵分别如图7.9(c)、图7.9(d)所示。显然，图的邻接矩阵有以下特点：(1) 当图中顶点的排列顺序确定后，该图的邻接矩阵是唯一确定的；(2) 无向图的邻接矩阵是对称的，可以采用压缩存储的方法仅存入其下三角（或上三角）部分的元素即可；(3) 在无向图中，顶点vi的度是其邻接矩阵A的第i行元素的和，即：；(4) 在有向图中，顶点vi的出度是其邻接矩阵A的第i行元素的和，而入度是A的第i列元素的和，所以vi 的度可以表示为：（n为图中顶点的个数）。2邻接矩阵的存储表示与实现(1)邻接矩阵的类型定义typedef enumDG,DN,UDG,UDNGKind; /图的类型GKind有向图,有向网,无向图,无向网typedef int VType; /为便于操作，定义顶点类型VType为int 型struct VNodeint flag;VType vex; /顶点与访问情况类型VNode访问次数,顶点信息struct MGraph /定义图的邻接矩阵类型MGraphVNode* vexs; /描述顶点的数组指针vexsVType* arcs; /邻接矩阵的数组指针arcsint vexnum,arcnum; /顶点数vexnum和边或弧数arcnumGKind kind; /图的种类标志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的种类标志kind建立图G的所有信息。#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.vexs分配存储空间G.arcs=new VTypeG.vexnum*G.vexnum; /为G.arcs分配存储空间cout按某种顺序输入G.vexnum个顶点的值:n;for(i=0;iG.vexsi.vex; /输入所有顶点的信息到G.vexs中for(i=0;iG.vexnum;i+) /将图G的关系集G.arcs初始化为空集for(j=0;jG.vexnum;j+)G.arcsi*G.vexnum+j=0;if(G.kind=DG|G.kind=UDG)cout输入图中G.arcnum条边(弧)的信息u v:n;elsecout输入图中G.arcnum条边(弧)和权的信息u v w:n;for(k=0;kuv; /根据顶点信息找到所在位置while(!(i=LocateVex_MG(G,u)&(j=LocateVex_MG(G,v);i-,j-; /i,j从位置值转换为下标值G.arcsi*G.vexnum+j=1;if(G.kind=DN|G.kind=UDN)cinG.arcsi*G.vexnum+j; /输入相应边或弧的权重wif(G.kind=UDG|G.kind=UDN) /无向图的邻接矩阵是对称的G.arcsj*G.vexnum+i=G.arcsi*G.vexnum+j;(4)显示输出邻接矩阵的操作函数功能是，显示输出图G的邻接矩阵G.arcs。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)演示程序主函数程序中分别建立有向图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;CreateGraph_MG(G3,gk3);cout建立一个无向网的邻接矩阵G4:n;CreateGraph_MG(G4,gk4);cout有向网G3的邻接矩阵为:n;DisplyMG(G3);cout无向网G4的邻接矩阵为:n;DisplyMG(G4);程序运行演示结果为：-.66.- 建立一个有向图的邻接矩阵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个顶点的值: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 01 0 0 0 1 0无向图G2的邻接矩阵为:0 1 0 1 0 01 0 1 0 0 10 1 0 0 1 01 0 0 0 1 00 0 1 1 0 10 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个顶点的值: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 0无向网G4的邻接矩阵为:0 9 0 8 09 0 0 3 00 0 0 0 128 3 0 0 10 0 12 1 0说明：（1）程序演示中建立的是图7.1、图7.3中4个图的邻接矩阵：G1.arcs、G2.arcs、G3.arcs、G4.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)的算法实现代码。（3）用邻接矩阵表示有n个顶点的图G时，查找边（或弧）的时间复杂度为O(n2)。由于邻接矩阵的存储空间仅与顶点数n有关，而与边无关，因此，当图G的顶点较多而边数又很少时，其边的查找效率会很低。为此，下面给出图的另一种存储结构，即图的邻接表表示法。7.2.2邻接表表示法图的邻接表表示是把图的每个顶点的邻接顶点用一个链表来表示。一般地，用顺序存储的方式来表示图中n个顶点的信息，另外，对图中每个顶点v建立一个单链表，用于表示与v相邻接的所有顶点的位置（下标）。链表中每个结点有两个域值：一个是顶点位置（下标）域，用于表示该邻接点的序号；另一个是指针域，用于指向下一个邻接点。1邻接表的定义(1) 表结点 在邻接表中，对图中的每个顶点建立一个单链表，顶点v所对应的单链表中的结点（表示依附于该顶点的边或以v为尾的弧）称为表结点。图的表结点中包含有顶点位置域(adjvex)、指向下一条边（弧）的指针域（nextarc）；而网的表结点中还要有表示相应权值的域（weight）。(2) 头结点 在邻接表中每个单链表上附设一个结点，称为头结点。每个头结点由3个域组成：结点信息域(data)、结点访问次数域(flag)和指向链表中第一个结点的指针域(nextarc)。图中的所有头结点以顺序结构存储。在图7.10中分别给出邻接表表结点的结构示图(a)和头结点的结构示图(b)。例如，图7.11分别给出有向图G1和无向图G2的一种邻接表表示结构。由于图中顶点的排列次序可以不同，每个顶点的邻接点的排列顺序也可以不同，所以，一个图的邻接表表示不唯一。用邻接表表示具有n个顶点和e条边的无向图时，需要一个由n个元素组成的顺序表（表头结点表）和由2e个结点组成的n个单链表。而表示n个顶点和e条弧的有向图时，需要一个由n个元素组成的顺序表和由e个结点组成的n个单链表。当图中边（或弧）的数目远远少于图的顶点数目时，邻接表所需的存储空间要比邻接矩阵所需的少。2逆邻接表在图G的邻接表中，顶点v的相邻元素可以通过遍历该顶点对应的单链表求得，设该链表中结点的个数为k那么，G为无向图时k表示v的度，G为有向图时k表示v的出度。如果求顶点v的入度，则需要遍历邻接表中的所有单链表，统计与v的序号相同的结点个数。这样处理很不方便，为此，仿照邻接表，建立一个逆邻接表，即对每个顶点v建立一个单链表，把所有邻接于v的顶点链接在一起，此时该单链表的长度即为v的入度。例如，图7.11(a)所示的有向图可用逆邻接表表示为图7.12。3邻接表的存储表示与实现(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)查找图中顶点位置的操作函数的功能是，返回顶点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,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;elsecout输入图中G.arcnum条边(弧)和权的信息u v w:n;for(k=0;kuv;while(!(i=LocateVex_AL(G,u)&(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) /对于无向图(或网)将结点pr1插入到第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)/显示邻接矩阵Gint i;ArcNode* p;for(i=0;iG.vexnum;i+)p=G.verticesi.nextarc;couti (G.verticesi.data): ;while(p)if(G.kind=DG|G.kind=UDG) /对于图仅输出顶点的下标值coutadjvex ;else /对于网要输出下标与对应的权的值coutadjvex,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;cout建立一个有向图的邻接表G1:n;CreateGraph_AL(G1,gk1);cout建立一个无向图的邻接表G2:n;CreateGraph_AL(G2,gk2);cout有向图G1的邻接表为:n;DisplyAL(G1);cout无向图G2的邻接表为:n;DisplyAL(G2);cout*n;cout建立一个有向网的邻接表G3:n;CreateGraph_AL(G3,gk3);cout建立一个无向网的邻接表G4:n;CreateGraph_AL(G4,gk4);cout有向网G3的邻接表为:n;DisplyAL(G3);cout无向网G4的邻接表为:n;DisplyAL(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个顶点的值: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): 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 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说明：（1）程序演示中建立的是图7.1、图7.3中4个图的一种邻接表表示：G1.vertices、G2.vertices、G3.vertices和G4.vertices。（2）在程序显示的结果中，第一列为顶点的下标，第二列为图中所有顶点的值。对于图，单链表中的每一项表示该顶点的邻接点的下标；对于网，单链表中的每一项表示该顶点的邻接点的下标值和相应边（弧）的权值。（3）在建立邻接表时，由于输入的是顶点信息，所以要先通过查找求得该顶点在图中的位置，再将相应结点插入到对应单链表的首部，所以，该操作的时间复杂度为O(n*e)。7.2.3有向图的十字链表表示法十字链表是有向图的另一种链式存储结构，该方法是将有向图的邻接表和逆邻接表结合起来得到的一种链表。1十字链表的定义类似邻接表，在十字链表中包含链表的头结点和弧结点两种类型的结点，图7.13给出十字链结点结构的示图。其中，头结点包含顶点信息域(data)、指向以该顶点为弧头的第一个弧结点的指针域(firstin)、指向以该顶点为弧尾的第一个弧结点的指针域(firstout)，表的所有头结点以顺序存储。弧结点包含表示弧尾顶点下标的尾域(tailvex)、表示弧头顶点下标的头域(headvex)、指向弧头相同的下一条弧的指针域(hlink)、指向弧尾相同的下一条弧的指针域(tlink)、弧的信息（如权值）域(info)。例如，图7.14给出有向图的一种十字链表表示。如果将有向图的邻接矩阵看成是稀疏矩阵的话，则十字链表也可以看成是邻接矩阵的十字链表存储结构。在有向图的十字链表表示中，链表的头结点之间是顺序存储结构，弧结点所在的链表是非循环链表，结点之间的相对位置自然形成，不一定按顶点序列号有序。由此可见，有向图的十字链表表示方式是不唯一的。2十字链表的存储表示与实现(1)十字链表存储结构的类型定义下面分别给出十字链弧结点(ArcBox)、顶点结点(OLVexNode)、十字链表(OLGraph)的类型定义。struct ArcBox /弧结点的结构定义int tailvex,headvex; /定义弧尾和弧头顶点的位置ArcBox *hlink,*tlink; /弧头相同、弧尾相同的弧的链域int weight; /定义有向网中弧的权值;struct OLVexNode /顶点结点结构定义VType data; /顶点信息ArcBox *firstin,*firstout; /分别指向顶点的第一条入弧和出弧;struct OLGraph /定义十字链表类型OLVexNode *xlist; /链表头结点数组指针int vexnum,arcnum; /有向图的顶点数和弧数GKind kind;(2)十字链表的查找操作函数int LocateVex_OLG(OLGraph G,VType u) 返回顶点u在图G中的位置，如果查找失败则返回0值。int LocateVex_OLG(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建立一个有向图或有向网的十字链表G。void CreateGraph_OLG(OLGraph& G,GKind kind)int i,j,k;VType u,v;ArcBox* pr;G.kind=kind;coutG.vexnumG.arcnum;G.xlist=new OLVexNodeG.vexnum; /为顶点数组分配内存空间cout按某种顺序输入G.vexnum个顶点的值:n;for(i=0;iG.xlisti.data; /输入所有顶点的信息到data中G.xlisti.firstin=G.xlisti.firstout=NULL; /设定初始的单链表为空if(G.kind=DG)cout输入图中G.arcnum条弧的信息u v:n;elsecout输入图中G.arcnum条弧和权的信息u v w:n;for(k=0;kuv;while(!(i=LocateVex_OLG(G,u)&(j=LocateVex_OLG(G,v);pr=new ArcBox; /动态分配弧存储空间pr-tailvex=-i; /i从位置值转换为下标值pr-headvex=-j; /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)显示十字链表信息的操作函数void DisplyOLG(OLGraph G)分别按邻接表和逆邻接表方式显示当前十字链表G的信息。void DisplyOLG(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建立一个有向图的十字链表G1:n;CreateGraph_OLG(G1,gk1);cout建立一个有向网的十字链表G2:n;CreateGraph_OLG(G2,gk2);cout有向图G1的信息为:n;DisplyOLG(G1);cout有向网G2的信息为:n;DisplyOLG(G2);程序运行演示结构为：建立一个有向图的十字链表G1:输入顶点数和边(弧)数vexnum a