《第7章 图结构》习题解答.doc 66页

'第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-.65.- 第7章图结构，则表示从顶点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）完全图(Completedgraph)用n表示图中的顶点数，则具有n(n-1)/2条边的无向图称为无向完全图；具有n(n-1)条弧的有向图称为有向完全图。当图G中边(或弧)的总数e满足：时，称其为稀疏图(sparsegraph)；当e满足：时称其为稠密图(densegraph)。显然，完全图是稠密图，反之不然。图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’)，若V’V并且E’E，则称G’是G的子图。例如，图7.4(a)为有向图及其部分子图，图7.4(b)为无向图及其部分子图。-.65.- 第7章图结构（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）出度(Outdegree)和入度(Indegree)在有向图中，顶点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）连通图(Connectedgraph)在无向图G=(V,VR)中，如果从顶点v到顶点w有路径，则称v与w是连通的。如果对于任意两个顶点v,w∈V都是连通的则称G是连通图。（18）连通分量(Connectedcomponent)无向图G中的极大连通子图称为G的连通分量。图7.5给出一个无向图和它的3个连通分量的示例。（19）强连通图在有向图G=(V,VR)中，如果对于任意两个顶点v,w∈-.65.- 第7章图结构V，都存在一条v到w的路径，则称G是强连通图；如果对于任意两个顶点v,w∈V，都存在一个顶点序列：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是一棵有向树。一个有向图的生成森林由若干棵有向树组成，森林中含有图中全部顶点，但是只有足以构成若干棵不相交的有向树的弧。显然，一个有向图生成的有向树或生成森林都不是唯一的。关于“顶点位置”的说明：-.65.- 第7章图结构在图的基本操作定义中，其“顶点位置”和“邻接点位置”仅是一个相对的概念。从图的定义可以看出，图中所有顶点的位置都是平等的，可以将任意一个顶点看成是第一个或最后一个顶点，也无法将其排列成一个线性序列或层次关系。在实际操作中，为了方便起见，需要将所有顶点按照某个任意选定的顺序排列起来（排列与图中顶点之间的关系无关）。所以，“顶点在图中的位置”是指该顶点在这个人为的随意排列中的位置（或序号）。同理，可以对某个顶点的所有邻接点按照某个任意选定的顺序进行排列。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．邻接矩阵的定义-.65.- 第7章图结构设G=(V,VR)是一个图，含有n个顶点，那么G的邻接矩阵是表示G中顶点之间相邻关系的n阶方阵An×n，下面分别根据有权图和无权图给出矩阵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)邻接矩阵的类型定义typedefenum{DG,DN,UDG,UDN}GKind;//图的类型GKind{有向图,有向网,无向图,无向网}-.65.- 第7章图结构typedefintVType;//为便于操作，定义顶点类型VType为int型structVNode{intflag;VTypevex;};//顶点与访问情况类型VNode{访问次数,顶点信息}structMGraph{//定义图的邻接矩阵类型MGraphVNode*vexs;//描述顶点的数组指针vexsVType*arcs;//邻接矩阵的数组指针arcsintvexnum,arcnum;//顶点数vexnum和边或弧数arcnumGKindkind;//图的种类标志kind};(2)查找图中顶点位置的操作函数的功能是，返回顶点u在图G中的位置，查找失败返回0值。intLocateVex_MG(MGraphG,VTypeu){inti;for(i=0;i>G.vexnum>>G.arcnum;G.kind=kind;G.vexs=newVNode[G.vexnum];//为G.vexs分配存储空间G.arcs=newVType[G.vexnum*G.vexnum];//为G.arcs分配存储空间cout<<"按某种顺序输入"<>G.vexs[i].vex;//输入所有顶点的信息到G.vexs中}for(i=0;i>u>>v;}//根据顶点信息找到所在位置while(!((i=LocateVex_MG(G,u))&&(j=LocateVex_MG(G,v))));i--,j--;//i,j从位置值转换为下标值G.arcs[i*G.vexnum+j]=1;if(G.kind==DN||G.kind==UDN)cin>>G.arcs[i*G.vexnum+j];//输入相应边或弧的权重wif(G.kind==UDG||G.kind==UDN)//无向图的邻接矩阵是对称的G.arcs[j*G.vexnum+i]=G.arcs[i*G.vexnum+j];}}(4)显示输出邻接矩阵的操作函数功能是，显示输出图G的邻接矩阵G.arcs。voidDisplyMG(MGraphG){inti,j;for(i=0;i>G.vexnum>>G.arcnum;G.vertices=newVexNode[G.vexnum];//为顶点数组分配内存空间cout<<"按某种顺序输入"<>G.vertices[i].data;//输入所有顶点的信息到vex中G.vertices[i].nextarc=NULL;//设定初始的单链表为空}if(G.kind==DG||G.kind==UDG)cout<<"输入图中"<>u>>v;}while(!((i=LocateVex_AL(G,u))&&(j=LocateVex_AL(G,v))));i--,j--;//i,j从位置值转换为下标值pr=newArcNode;//动态分配单链表结点prpr->adjvex=j;pr->weight=0;if(G.kind==DN||G.kind==UDN)cin>>pr->weight;//输入对应边（弧）的权值pr->nextarc=G.vertices[i].nextarc;//将结点pr插入到第i个链表的首部G.vertices[i].nextarc=pr;if(G.kind==UDG||G.kind==UDN)//对于无向图(或网)将结点pr1插入到第j个链表的首部{pr1=newArcNode;//动态分配单链表结点pr1pr1->adjvex=i;pr1->weight=pr->weight;pr1->nextarc=G.vertices[j].nextarc;G.vertices[j].nextarc=pr1;//将结点pr1插入到第j个链表的首部}//endswitch}//endfor}(4)显示输出邻接矩阵的操作函数功能是，显示输出图G的邻接链表中的所有信息。voidDisplyAL(ALGraphG)//显示邻接矩阵G{inti;-.65.- 第7章图结构ArcNode*p;for(i=0;iadjvex<<"]";else//对于网要输出下标与对应的权的值cout<<"["<adjvex<<","<weight<<"]";p=p->nextarc;}cout<>G.vexnum>>G.arcnum;G.xlist=newOLVexNode[G.vexnum];//为顶点数组分配内存空间cout<<"按某种顺序输入"<>G.xlist[i].data;//输入所有顶点的信息到data中G.xlist[i].firstin=G.xlist[i].firstout=NULL;//设定初始的单链表为空}if(G.kind==DG)cout<<"输入图中"<>u>>v;}while(!((i=LocateVex_OLG(G,u))&&(j=LocateVex_OLG(G,v))));pr=newArcBox;//动态分配弧存储空间pr->tailvex=--i;//i从位置值转换为下标值pr->headvex=--j;//j从位置值转换为下标值if(G.kind==DN)cin>>pr->weight;pr->hlink=G.xlist[j].firstin;//将输入的弧插入到相应链表的首部G.xlist[j].firstin=pr;pr->tlink=G.xlist[i].firstout;G.xlist[i].firstout=pr;}//endfor}(4)显示十字链表信息的操作函数voidDisplyOLG(OLGraphG)分别按邻接表和逆邻接表方式显示当前十字链表G的信息。voidDisplyOLG(OLGraphG){inti;ArcBox*p;-.65.- 第7章图结构cout<<"按邻接表显示结果为：n";for(i=0;itailvex<<""<headvex;if(G.kind==DN)cout<<""<weight;cout<<"]";p=p->tlink;}cout<tailvex<<""<headvex;if(G.kind==DN)cout<<""<weight;cout<<"]";p=p->hlink;}cout<>G.vexnum>>G.edgenum;G.xlist=newVexBox[G.vexnum];//为顶点数组分配内存空间cout<<"按某种顺序输入"<>G.xlist[i].data;//输入所有顶点的信息到data中G.xlist[i].firsedge=NULL;//设定初始的单链表为空}if(G.kind==DG)cout<<"输入图中"<>u>>v;}while(!((i=LocateVex_AMLG(G,u))&&(j=LocateVex_AMLG(G,v))));pr=newEBox;//动态分配边的存储空间pr->ivex=--i;//i从位置值转换为下标值pr->jvex=--j;//j从位置值转换为下标值if(G.kind==DN)cin>>pr->info;pr->ilink=G.xlist[i].firsedge;//将输入的边插入到相应链表的首部G.xlist[i].firsedge=pr;pr->jlink=G.xlist[j].firsedge;G.xlist[j].firsedge=pr;}//endfor}(4)按邻接表方式显示当前邻接多重链表的信息-.65.- 第7章图结构函数voidDisplyAMLG(AMLGraphG)按邻接表的方式显示当前邻接多重链表表示的无向图G的相关信息。voidDisplyAMLG(AMLGraphG){inti;EBox*p;cout<<"按邻接表显示结果为：n";for(i=0;iivex==i)cout<<"["<ivex<<""<jvex;elsecout<<"["<jvex<<""<ivex;if(G.kind==DN)cout<<""<info;cout<<"]";if(p->ivex==i)p=p->ilink;//指针指向下一个边结点elsep=p->jlink;}cout<nextarc)//进入下一层{w=p->adjvex;-.65.- 第7章图结构if(!G.vertices[w].flag)DFS_ALG(G,w);//通过递归调用实现深度优先遍历}}(2)对图的深度优先遍历函数voidDFSTraverse_ALG(ALGraphG)的功能是，通过重复调用函数DFS_ALG(G,v)实现对邻接表G的深度优先遍历。voidDFSTraverse_ALG(ALGraphG){intv;for(v=0;vadjvex;if(!G.vertices[u].flag){G.vertices[u].flag=1;//修改标志cout<nextarc;//进入下一个邻接点}//endwhile}//endwhile}//endif}//endforcout<nextarc)-.65.- 第7章图结构{w=p->adjvex;if(!G.vertices[w].flag){q=newCSNode;//动态分配结点qq->data=G.vertices[w].data;//为结点q赋值q->firstchild=q->nextsibling=NULL;if(first){first=0;T->firstchild=q;}//w是第一个v的未被访问的邻接点else{s->nextsibling=q;s=q;}//w是v的其它未被访问的邻接点DFSTree(G,w,q);//从w出发深度优先遍历G，建立子生成树q}//end_if}//end_for}(3)生成森林的算法实现函数voidDFSForest(ALGraphG,CSTree&T)的功能是，从无向图G的第一个结点（按邻接表中的结点顺序）开始，对G进行深度优先遍历得到深度优先生成森林（或树）T。voidDFSForest(ALGraphG,CSTree&T){CSTreep,q;intv;T=NULL;for(v=0;vdata=G.vertices[v].data;//为结点p赋值p->firstchild=p->nextsibling=NULL;if(!T)T=q=p;//v是第一棵生成树的根else{q->nextsibling=p;q=p;}//v是其它生成树的根DFSTree(G,v,p);//建立以p为根的生成树}}显然，该算法的时间复杂度与深度优先遍历算法的时间复杂度相同。7.4.2最小（代价）生成树1．最小生成树的概念对于无向网，因为它的边是带有权值的，而一个图的生成树是不唯一的，那么，就产生了这样一个问题：如何找到一个各边的权值总和最小的生成树，这种生成树称为最小（代价）生成树。-.65.- 第7章图结构最小生成树问题在实际应用中很有意义，比如，要在n个城市之间建立通信联络网，最多有n(n-1)/2条路线，而连通这n个城市仅需要其中的n-1条路线（图的生成树）即可，由于每对城市之间的距离不一样，铺设线路所花费的经济价格也不一同，此时，自然会考虑到如何在最节省经费（最小代价）的前提下建立通信网。例如，图7.21(b)是图7.21(a)的最小生成树。常用的最小代价生成树算法有两种，即普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。这两种算法都用了最小生成树的MST性质，即：设N=(V,VR)是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中u∈U，v∈V-U，则必有一棵包含边(u,v)的最小生成树。2．普里姆(Prim)算法(1)普利姆算法思想设N=(V,VR)是一个连通网，TE是V上最小生成树边的集合。普里姆（Prim）算法从U={u0}(u0∈V)，TE={}开始。重复执行如下操作：在所有u∈U，v∈V-U的边(u,v)∈VR中找一条代价最小的边(u0,v0)并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=(U,TE)为网N=(V,VR)的最小生成树。例如，对于图7.21(a)所示的网，从顶点1开始，按照普里姆算法求最小生成树的过程，可以由图7.22(a)到图7.22(f)表示。为了便于普里姆算法的实现，还需要附设一个数组closedge[]，用以记录从U到V-U具有最小代价的边。对每个顶点vi∈-.65.- 第7章图结构V-U，在数组中存在相应的元素closedge[i-1]，它包含两个域：一个是adjvex域，用于存储该边所依附的在U中的点；另一个是lowcost域，用于存储该边上的权值。lowcost域的具体含义为：图7.23给出利用普里姆算法在图7.22所示的最小生成树的构造过程中，辅助数组closedge[]中各个分量值的具体变化情况。图中第一行内的虚线框表示选中顶点4到U中，边(1,4)的权值为1；图中第二行中closedge为选入顶点1、4以后U到V-U的最短距离，其虚线框表示选中顶点2到U中，边(1,2)的权值为2；第三行中closedge为选入顶点1、2、4以后U到V-U的最短距离，其虚线框表示选中顶点3到U中，边(4,3)的权值为2；以此类推，直到全部顶点均被选入为止。(2)普利姆算法程序实现定义辅助数组类型CloseDgestructCloseDge{VTypeadjvex;intlowcost;};(1)函数voidMiniTree_Prim(MGraphG,VTypeu)的功能是，对于邻接矩阵存储的网G，从顶点u开始，用普里姆算法构造一棵最小代价生成树，并输出该树的结点和边的权值。voidMiniTree_Prim(MGraphG,VTypeu){inti,j,k,min,max;CloseDge*closedge=newCloseDge[G.vexnum];if(!(k=LocateVex_MG(G,u)))return;k--;//将k转换为顶点u的下标-.65.- 第7章图结构for(max=G.arcs[0],i=0;i0&&closedge[j].lowcost=0;m--){if(edge[m].adjvex>w)edge[m+1]=edge[m];elsebreak;}edge[m+1]=arc;k++;}}(2)函数voidFindedge(ALGraph&G,intu,intv,int&flag)的功能是，用深度优先搜索法在以邻接表存储的无向网G中考察顶点u、v是否在同一个连通分量中，如果在同一个连通分量中则flag=1，否则flag=0。voidFindedge(ALGraph&G,intu,intv,int&flag){intw;ArcNode*p;G.vertices[u].flag=1;for(p=G.vertices[u].nextarc;p;p=p->nextarc)-.65.- 第7章图结构{w=p->adjvex;if(w==v){flag=1;return;}if(!G.vertices[w].flag)Findedge(G,w,v,flag);}}(3)函数voidMiniTree_Kruskal(ALGraph&T,MGraphG)的功能是，用克鲁斯卡尔算法求以邻接矩阵存储的无向网G的最小生成树T，T以邻接表存储。voidMiniTree_Kruskal(ALGraph&T,MGraphG){inti,k,j,u,v,flag;ArcNode*pr,*pr1;Edge*edge,arc;/*以下语句的功能是对生成树T进行初始化*/T.vertices=newVexNode[G.vexnum];//为T的头结点数组动态分配内存T.arcnum=G.vexnum-1;//设置T中的边数为n-1条T.kind=G.kind;T.vexnum=G.vexnum;for(i=0;iadjvex=v;pr->weight=arc.adjvex;pr->nextarc=T.vertices[u].nextarc;T.vertices[u].nextarc=pr;pr1=newArcNode;//动态分配单链表结点pr1pr1->adjvex=u;pr1->weight=arc.adjvex;pr1->nextarc=T.vertices[v].nextarc;T.vertices[v].nextarc=pr1;k++;-.65.- 第7章图结构}for(j=0;j2,v30,3,3,v41,v50,3,3,3,v60,9,9,8,8,6,v70,5,5,5,5,vkv4v2v3v5v7v6S={v1}{v1,v4}{v1,v4,v2}{v1,v4,v2,v3}{v1,v4,v2,v3,v5}{v1,v4,v2,v3,v5,v7}{v1,v4,v2,v3,v5,v7,v6}图7.27最短路径及其长度变化表由图7.27的第1列可以看出，一开始顶点集S中只有源点即S={v1}，第2列是源点v1到各个顶点的最短路径长度以及路径上的顶点；在第2列中选中“1,”，即顶点v4加入到S中并同时修改加入v4以后顶点v1到各个顶点的最短路径长度以及路径上的顶点，由此得到第3列；在第3列中选中“2,”，即将顶点v2加入到S中并同时修改v1到各个顶点的最短路径长度以及路径上的顶点，从而得到第4列；在第4列中选中“3,”，即顶点v3加入到S中并同时修改v1到各个顶点的最短路径长度以及路径上的顶点后得到第5列；以此类推，直到所有顶点均被选入为止。2．迪杰斯特拉(Dijkstra)算法(1)定义辅助数组dist[]的结构类型structDist-.65.- 第7章图结构{intfinal;//路径是否结束intmin;//当前路径长度intvex;//网中的结点个数inttop;//存储路径的栈顶指针int*path;//存储路径的栈};(2)初始化辅助数组dist[]函数voidInitDist(Dist*&dist,MGraphG,intv)的功能是，通过有向图G的邻接矩阵以及源点v来初始化辅助数组dist[]。voidInitDist(Dist*&dist,MGraphG,intv){inti;dist=newDist[G.vexnum];for(i=0;i>v;ShortestPath_DIJ(dist,G,v);cout<<"源点为:v="<。下面验证该路径是否为最短路径：首先考虑是否存在（即和是否存在）。如果存在则比较ars[i][1]+ars[1][j]与ars[i][j]，取其中较小者作为从vi到vj的中间点序号不大于1的最短路径长度dist[i][j]并修改相应的路径path[i][j]。然后在路径path[i][j]中再增加一个顶点v2，如果path[i][2]与path[2][j]均存在则比较dist[i][2]+dist[2][j]与dist[i][j]，取其中较小者作为从vi到vj的中间点序号不大于2的最短路径长度dist[i][j]并修改相应的路径path[i][j]。之后在path[i][j]中再增加一个顶点v3重复以上过程。一般地讲，如果path[i][k]与path[k][j]分别是从vi到vk和vk到vj-.65.- 第7章图结构的中间顶点序号不大于k-1的最短路径，则比较dist[i][k]+dist[k][j]与dist[i][j]，取较小者作为从vi到vj的中间点序号不大于k的最短路径长度dist[i][j]并修改相应的路径path[i][j]。弗洛伊德(Floyd)算法递推地产生一个矩阵序列：(dist(0)[i][j],path(0)[i][j])，(dist(1)[i][j],path(1)[i][j])，…，(dist(n)[i][j],path(n)[i][j])。其中，(dist(k)[i][j],path(k)[i][j])分别表示从vi到vj的，中间顶点序号不大于k的，最短路径长度和路径。所以，Floyd算法就是逐步允许越来越多的顶点作为路径的中间顶点，直至所有可能的顶点均作为中间点为止。取矩阵序列dist(k)[i][j]的初值为dist(0)[i][j]=arcs[i][j]，则已知dist(k-1)[i][j]求解dist(k)[i][j]的过程分以下两种情况：(1)如果从vi到vj的路径不经过vk，则dist(k)[i][j]=dist(k-1)[i][j]，path(k)[i][j]=path(k-1)[i][j]。(2)如果从vi到vj的路径经过vk，则比较dist(k-1)[i][k]+dist(k-1)[k][j]与dist(k-1)[i][j]，取较小者作为dist(k)[i][j]，并修改相应的路径path(k)[i][j]为：path(k-1)[i][j]或path(k-1)[i][k]+path(k-1)path[k][j]。例如，对图7.28所示的有向网G，通过弗洛伊德(Floyd)算法，求其每一对顶点之间的最短路径长度dist[i][j]和最短路径path[i][j]。求解过程中dist、path的变化情况如图7.29所示。在图7.29中，Dist0与path0分别表示初始状态的vi、vj的最短距离及路径；Dist1与path1分别表示加入顶点v0(即顶点a)以后顶点vi、vj的最短距离及路径；Dist2与path2分别表示加入顶点v1(即顶点b)以后顶点vi、vj的最短距离及路径；Dist3与path3分别表示加入顶点v2(即顶点c)以后顶点vi、vj的最短距离及路径。2．弗洛伊德(Folyd)算法的实现(1)定义辅助数组dist[]与path[]的结构类型structStack{intt,*s;};//定义存储最短路径的栈类型-.65.- 第7章图结构structMin{intnum;//有向网的结点个数int*dist;//最短路径长度的数组指针Stack*path;//存储路径的数组指针};(2)数组的初始化操作函数voidInitMin(Min&min,MGraphG)的功能是，通过G的邻接矩阵对矩阵来初始化路径数组min。voidInitMin(Min&min,MGraphG){inti,j,w;intnum=G.vexnum;min.num=num;min.dist=newint[num*num];//为最短距离矩阵dist分配空间min.path=newStack[num*num];//为最短路径矩阵path分配空间for(i=0;i{min.path[i*num+j].s[0]=i;min.path[i*num+j].s[1]=j;min.path[i*num+j].t+=2;}}}(3)路径操作与显示输出函数voidAddpath(Stack&path,Stackpath1,Stackpath2)的功能是，实现对路径path[i][j]的连接操作：path[i][j]=path[i][k]+path[k][j]的运算。voidAddpath(Stack&path,Stackpath1,Stackpath2){intt=0,i=0,j=1;while(i="<=";if(t==0)cout<<"nopath!";elsefor(k=0;k=0<0,1>=2<0,2>=3<0,3>=1<0,4>=3<0,5>=6<0,6>=5<1,0>=9<1,1>=0<1,2>=5<1,3>=3<1,4>=5<1,5>=8<1,6>=7<2,0>=4<2,1>=6<2,2>=0<2,3>=5<2,4>=7<2,5>=5<2,6>=9<3,0>=6<3,1>=8<3,2>=2<3,3>=0<3,4>=2<3,5>=5<3,6>=4<4,0>=0<4,1>=0<4,2>=0<4,3>=0<4,4>=0<4,5>=7<4,6>=6<5,0>=0<5,1>=0<5,2>=0<5,3>=0<5,4>=0<5,5>=0<5,6>=0<6,0>=0<6,1>=0<6,2>=0<6,3>=0<6,4>=0<6,5>=1<6,6>=0最短路径上的结点为:-.65.-第7章图结构<0,1>=01<0,2>=032<0,3>=03<0,4>=034<0,5>=0365<0,6>=036<1,0>=1320<1,2>=132<1,3>=13<1,4>=134<1,5>=1365<1,6>=136<2,0>=20<2,1>=201<2,3>=203<2,4>=2034<2,5>=25<2,6>=2036<3,0>=320<3,1>=3201<3,2>=32<3,4>=34<3,5>=365<3,6>=36<4,0>=nopath!<4,1>=nopath!<4,2>=nopath!<4,3>=nopath!<4,5>=465<4,6>=46<5,0>=nopath!<5,1>=nopath!<5,2>=nopath!<5,3>=nopath!<5,4>=nopath!<5,6>=nopath!<6,0>=nopath!<6,1>=nopath!<6,2>=nopath!<6,3>=nopath!<6,4>=nopath!<6,5>=65-.65.-第7章图结构程序运行中所建立的是图7.26(a)所示的有向网G的邻接矩阵，其输出结果是G中任意两点之间的最短路径长度和最短路径上各个顶点的下标序列。该算法的时间复杂度为O(n3)。-.65.- 第7章图结构7.6拓扑排序拓扑排序是有向图的重要应用之一，它在实际中的应用很广。有向无环图是描述工程和系统进程的有效工具。例如，要完成一项大工程(project)可以把它分为若干个称为活动(activity)的子工程，当这些活动都完成时，整个工程即告结束。而这些活动的安排有时要有特殊的要求，比如有些活动必须安排在另外一些活动已完成以后才能开始，而有些活动并不依赖于任何活动的完成等。类似这样的问题，可以用有向无环图来解决。7.6.1AOV网在有向图中，以顶点表示活动，有向边表示活动之间的优先关系，我们把这样的有向图称为顶点表示活动的网络(ActivityOnVertexNetwork)，简称为AOV网。在AOV网中，若从顶点vi到顶点vj有一条有向路径，则称vi是vj的前驱，vj是vi的后继；若是AOV网中的一条弧，则称vi是vj的直接前驱，vj是vi的直接后继。如果vi是vj的前驱或直接前驱，则vi活动必须在vj活动开始前结束；而vj活动必须在vi活动结束后才能开始。在AOV网中不允许出现回路，因为如果有回路存在则表示必有某个活动是以自己为先决条件的，即存在活动vi，vi既是其本身的前驱又是其本身的后继，这显然是矛盾的。例如，图7.30(a)列出了某大学计算机专业学生所学的一些课程，图7.30(b)用有向图表示课程之间的先后关系。课程号课程名称先导课课程号课程名称先导课C1C语言程序设计无C7编译原理C3,C5C2离散数学C1C8操作系统C3,C6C3数据结构C1,C2C9高等数学无C4汇编语言C1C10线性代数C9C5语言设计与分析C3,C4C11普通物理C9C6计算机组成原理C11C12数值分析C1,C9,C10(a)某大学计算机专业学生所学的一些课程由图可以看出，先学习课程C1、C2以后才可以开始学习课程C3，即C1、C2为C3的直接前导课程；只有学习C3、C4以后才可以开始学习课程C5；只有学习C3、C5-.65.- 第7章图结构以后才可以学习课程C7。所以C7的直接前导课程为C3、C5，而C7的所有前导课程为C1、C2、C3、C4、C5。检测AOV网中是否存在环路的办法是对有向图构造其顶点的拓扑有序序列，若网中所有顶点均在该序列中，则该AOV网中必定不存在环路，否则必有环路存在。7.6.2拓扑排序如何安排AOV网中各个活动的先后次序就是拓扑排序问题。所谓拓扑排序，即是把AOV网中各个顶点按照它们之间的优先关系排列成一个线性序列，这个序列称为拓扑有序序列。在AOV网中，如果从顶点vi到顶点vj有有向路径存在，则在拓扑有序序列中，vi必定排在vj的前面。如果在AOV网中存在环路，则不存在该网的拓扑有序序列；否则，任何有向无环网其所有顶点都可以排列在一个拓扑有序序列中。显然，一个AOV网的拓扑有序序列不是唯一的。对图7.30(b)所示的有向图进行拓扑排序，可以得到多种不同的拓扑有序序列，下面给出其中的三种拓扑有序序列：对AOV网进行拓扑排序的步骤是：首先任意选取一个入度为零的顶点输出，再从图中删除该顶点和所有以它为尾的弧。重复以上步骤，直至有向图中全部顶点都被输出，或者还没有输出全部顶点，但已找不到入度为零的顶点为止。第一种情况表明该有向图中不存在有向环路，拓扑排序已完成；对于第二种情况则说明该有向图中存在有向环路。1．拓扑排序的算法思想为了实现拓扑排序的方法，可以采用邻接表作为有向图的存储结构，并且在头结点中增加一个存放顶点入度的域(indegree)。每个顶点入度域的值随邻接表动态生成过程中累计得到。也可以另设一个数组(indegree)用于存放所有顶点的入度。在入度数组(indegree)中，入度为0的顶点即为可以删除的没有前驱的顶点。删除顶点以及以该顶点为尾的所有弧的操作，可以通过对弧头顶点入度域的值减1来实现。为了避免重复检测入度为0的顶点，可以另设一个栈(Stack)来存储所有入度为0的顶点下标。下面列出拓扑排序算法的具体步骤：(1)如果入度数组(indegree)是另设的，则初始化该数组；(2)将邻接表中所有入度为0的顶点下标进栈S，初始化输出顶点计数器count；(3)在栈S不为空时：a)出栈并输出顶点i，count++；b)将顶点i的所有直接后继顶点k的入度减1。如果减1后，顶点k的入度为0，则顶点k进栈S。(4)如果S为空时countadjvex]++;p=p->nextarc;}}S.s=newint[num];S.t=0;for(i=0;iadjvex]--;if(!indegree[p->adjvex])S.s[S.t++]=p->adjvex;p=p->nextarc;}}cout<表示，其持续时间为dut()，事件的最早开始时间为ve(j)，最迟开始时间为vl(j)，则有关系：e(i)=ve(j)，l(i)=vl(k)-dut()。其中ve(j)与vl(j)的计算均采用以下递推的方法：由公式(1)、(2)可以看出：计算ve(j)时，从事件a0开始向前推进；计算vl(i)时，从事件an-1开始向后推进。这两个递推公式的计算必须分别在拓扑有序和逆拓扑有序的前提下进行。也就是说，在事件vj的所有前驱事件的最早开始时间确定之后，才能计算出vj的最早开始时间ve(j)；在事件vi的所有后继事件的最迟开始时间确定之后，才能计算出vi的最迟开始时间vl(i)-.65.- 第7章图结构。求拓扑逆序的过程与求拓扑正序的过程类似：检查所有出度为0的顶点，并删除这些顶点及以这些点为头的弧，继续这个过程，直到结束。如果已经得到了拓扑序列，那么求拓扑逆序只需将该序列倒排一下即可。例如，图7.34所示的AOE网中，各事件的最早开始时间、最迟开始时间如图7.35所列，各活动的持续时间、最早开始时间、最迟开始时间、时间余量如图7.36所列。vi012345678ve(i)057131717192224vl(i)0107131720192224图7.35AOE网中各事件的最早、最迟时间aia0a1a2a3a4a5a6a7a8a9a10a11a12j0012233344657k1233445667888dut()5736344425542e(i)005771313131717191722l(i)50107141316151717192022l(i)-e(i)5050703200030图7.36网中各活动的持续时间、最早开始时间、最迟开始时间、时间余量由图7.36得到的关键活动为：a1、a3、a5、a8、a9、a10、a12。关键路径如图7.37所示。求关键路径的步骤为：(1)从源点v0开始，计算各事件的最早开始时间。令ve(0)=0，按拓扑有序求其余各顶点的最早开始时间ve(i)(0adjvex;indegree[p->adjvex]--;if(!indegree[p->adjvex])S.s[S.t++]=k;if(Ve[j]+p->weight>Ve[k])Ve[k]=Ve[j]+p->weight;p=p->nextarc;}}delete[]indegree;delete[]S.s;return((count，以及该活动的持续时间dut、最早开始时间ee、最迟开始时间el和是否是关键活动的信息(Y/N)。voidCriticalPath(ALGraphG){inti,j,k,ee,el,*Ve,*Vl;chartag;ArcNode*p;StackS;if(!TopSort1(G,Ve,S))-.65.- 第7章图结构{cout<<"AOE网中存在环路，操作失败！n";return;}Vl=newint[G.vexnum];for(i=0;i0)//按照逆拓扑排序的顺序{j=S.s[--S.t];p=G.vertices[j].nextarc;while(p)//计算每个顶点的最迟开始时间{k=p->adjvex;if(Vl[k]-p->weightweight;p=p->nextarc;}}cout<<"j,k,dut,ee,el,tagn";for(j=0;jadjvex;ee=Ve[j];el=Vl[k]-p->weight;tag=(ee==el)?"Y":"N";cout<weight<<","<nextarc;}}}voidmain(){ALGraphG;GKindgk=DN;cout<<"建立一个AOE网的邻接表G:n";CreateGraph_AL(G,gk);cout<<"AOE网G的邻接表为:n";DisplyAL(G);cout<<"AOE网G的关键活动为:n";CriticalPath(G);}程序运行演示结果为：-.65.-第7章图结构建立一个AOE网的邻接表G:输入顶点数和边(弧)数vexnumarcnum:913↙按某种顺序输入9个顶点的值:123456789↙输入图中13条边(弧)和权的信息uvw:125137243346353454464474694795892572585↙AOE网G的邻接表为:0(1):[2,7][1,5]1(2):[3,3]2(3):[4,3][3,6]3(4):[6,4][5,4][4,4]4(5):[7,5][6,2]5(6):[8,4]6(7):[8,5]7(8):[8,2]-.65.- 第7章图结构8(9):AOE网G的关键活动为:j,k,dut,ee,el,tag0,2,7,0,0,Y0,1,5,0,5,N1,3,3,5,10,N2,4,3,7,14,N2,3,6,7,7,Y3,6,4,13,15,N3,5,4,13,16,N3,4,4,13,13,Y4,7,5,17,17,Y4,6,2,17,17,Y5,8,4,17,20,N6,8,5,19,19,Y7,8,2,22,22,Y-.65.-第7章图结构程序运行中所建立的是图7.34所示的AOE网的邻接表，其输出结果是G中每个活动所依附的顶点下标，以及该活动的持续时间dut、最早开始时间ee、最迟开始时间el和是否是关键活动的信息(Y/N)。求关键路径的时间复杂度为O(n+e)。7.8习题一、问答题1．在一个图中，各个顶点的度数之和与图的边数之和的关系是什么？2．在一个有向图中，所有顶点的入度之和与所有顶点的出度之和的关系是什么？3．对图7.38所示的无向图，试回答：（1）每个顶点的度是多少？（2）给出它们的邻接矩阵、邻接表、邻接多重表表示。（3）从顶点1开始按编号递增的顺序进行深度优先遍历的顶点序列是什么？（4）从顶点1开始按编号递减的顺序进行广度优先遍历的顶点序列是什么？4．对图7.39所示的有向图，试回答：（1）每个顶点的出度、入度各是多少？（2）给出它们的邻接矩阵、邻接表、逆邻接表、十字链表表示。（3）从顶点1开始按编号递减的顺序进行深度优先遍历的顶点序列是什么？（4）从顶点1开始按编号递增的顺序进行广度优先遍历的顶点序列是什么？5．对于图7.40(a)、(b)所示的两个无向图，从顶点v1开始按编号递增的顺序分别进行深度优先遍历和广度优先遍历。分别画出以上遍历的深度优先生成树和广度优先生成树。-.65.- 第7章图结构6．画出图7.41所示的无向网：(1)按照普里姆算法，从顶点v1出发生成最小生成树，按生成次序写出各条边。(2)按照克鲁斯卡尔算法，生成最小生成树，按生成次序写出各条边。(3)画出最小生成树，并求出该树的权值。7．试利用迪杰斯特拉(Dijkstra)算法，求图7.42所示的有向网中从顶点a到其它各顶点的最短路径，写出矩阵path、dist在执行该算法过程中各步的状态。8．利用弗洛伊德(Floyd)算法求图7.43所示的有向网中各对顶点之间的最短路径，并写出计算过程。9．已知有m个顶点的无向图，采用邻接矩阵结构存储在矩阵A中。(1)求图中共有多少条边的方法是什么？(2)判断顶点i和j之间是否有边的方法是什么？(3)计算顶点i的度的方法是什么？-.65.- 第7章图结构10．已知一个无向图采用邻接表结构存储。(1)求图中共有多少条边的方法是什么？(2)判断顶点i和j之间是否有边的方法是什么？(3)计算顶点i的度的方法是什么？11．试列出图7.44所示的有向图中所有可能的拓扑有序序列。12．对于图7.45所示的AOE网所代表的一项工程，(1)计算每个事件的最早开始时间和最迟开始时间；(2)计算每个活动的最早开始时间和最迟开始时间；(3)计算完成该工程的最短时间；(4)求出该工程的所有关键活动；(5)求出该工程的关键路径。二、填空题1．具有n个顶点的连通图至少有（）条边。2．当图的顶点序列确定时，该图的（）表示法唯一，而（）表示法不唯一。3．G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。4．具有n个顶点的无向图，边的总数最多有（）条。5．在具有n个顶点的有向图中，顶点的度最大为（）。6．已知图G的邻接表表示如图7.46所示，从顶点v1出发的深度优先遍历序列为（）广度优先遍历序列为（）。7．如果含有n个顶点的图形成一个环，则它有（）棵生成树。8．图G有n个顶点和e条边，采用邻接矩阵存储，则拓扑排序算法的时间复杂度为（）。-.65.- 第7章图结构9．用克鲁斯卡尔算法求最小生成树的时间复杂度为（），该算法对（）图较为适合。10．有向图G如图7.47所示。（1）该图的所有拓扑排序序列有（）；（2）添加弧（）后，则仅有唯一的一个拓扑排序序列。三、编程设计1．编写算法，在有n个顶点的有向图G的邻接表上，统计每个顶点的入度、出度和总度数。2．分别给出建立无向图、有向图和有向网的邻接矩阵的算法。3．分别给出建立无向图、有向图和有向网的邻接表的算法。4．编写算法，在无向图的邻接表结构上，生成无向图的邻接矩阵结构。5．编写算法，在无向图的邻接矩阵结构上，生成无向图的邻接表结构。6．编写算法，已知图有向G的邻接表存储结构：(1)求G中出度最大的顶点，并输出该顶点的编号；(2)求G中所有出度为0的顶点，并输出它们的编号；(3)判断G中是否存在边(i,j)（即存在弧和）。7．编写算法，判断无向图G是否连通：若连通返回1；否则返回0。8．编写程序，实现对图G从顶点v开始进行深度优先遍历的非递归算法。9．编写算法，判断无向图G是否为一棵树：若是一棵树则返回1；否则返回0。10．编写算法，判断有向图G是否为一棵以v0为根的有向树：若是则返回1；否则返回0。11．编写算法，求出无向图G的连通分量的个数。12．编写算法。对于邻接矩阵存储的无向网G，从顶点u开始，用普里姆算法构造一棵最小代价生成树T，并输出T中所有结点、边和权值的信息。13．编写程序。用克鲁斯卡尔算法求以邻接矩阵存储的无向网G的最小生成树T，T以邻接表存储。14．编写程序。通过迪杰斯特拉算法求出邻接矩阵表示的有向网G从源点v出发到各点的最短路径长度dist[]和最短路径path[]。15．编写程序。通过弗洛伊德算法求出邻接矩阵表示的有向网G中每一对顶点之间的最短路径及其长度到min中。16．编程实现。根据有向图G的邻接表输出一个拓扑排序序列。17．编程程序。求出邻接表表示的有向网G中每个活动所依附的顶点下标，以及该活动的持续时间dut、最早开始时间ee、最迟开始时间el和是否是关键活动的信息(Y/N)。7.9上机实验-.65.- 第7章图结构图结构是一种比线性结构和树结构更为复杂的数据结构。在图结构中，任意两个顶点之间都可能相关，结点之间的邻接关系是任意的。图是计算机应用过程中对实际问题进行数学抽象和描述的强有力的工具，是本门课程的重点之一。数据结构中对图的研究侧重于图在计算机中如何存储表示，以及如何实现对图的遍历和求图的连通分量、生成树、最短路径等基本操作。实验题目1图的遍历演示【问题描述】图是非线性结构，图的遍历操作是其它众多基本操作的基础。试编写一个程序，完成对邻接表存储表示的连通图进行深度优先遍历和广度优先遍历的操作。【基本要求】以邻接表为存储结构，实现对连通图（有向图和无向图）的深度优先和广度优先遍历。以用户指定的顶点为起点，分别输出每种遍历下的顶点访问序列和相应生成树（有向树）的边。【测试数据】本章习题中图7.39和图7.40(a)、图7.40(b)所表示的图。【实现提示】（1）在建立图的邻接表表头时，每个顶点用一个编号表示（如果图有n个顶点，则它们的编号分别为0,1,2,3,…,n-1）。其顶点序列的顺序可按用户输入顶点数据时的顺序来确定。（2）在建立邻接表的链表时，通过输入图的全部边（或弧）来输入图，每个边（或弧）为一个数对。注意，生成树的边是有向的，端点顺序不能颠倒。【选作内容】（1）借助栈类型（自己定义和实现），用非递归算法实现图的深度优先遍历。（2）以邻接表为存储结构，建立深度优先生成树和广度优先生成树。实验题目2最小生成树【问题描述】若在n个城市之间建立通信网络，只需要架设n-1条路线即可。如何以最低的经济代价架设这个通信网络，是一个网的最小生成树问题。【基本要求】（1）利用普里姆算法求网的最小生成树。（2）利用克鲁系卡尔算法求网的最小生成树。（3）输出生成树中各条边以及它们的权值。【测试数据】本章习题中图7.41所示的图。-.65.- 第7章图结构【实现提示】通信线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。图的存储结构的选取，应和所做的操作相适应。为了便于选择权值最小的边，此题将每条边及其权值的信息顺序存储到一个数组中。实验题目3校园导游咨询（最短路径问题）【问题描述】设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】（1）设计所在校园的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、介绍等信息；以边表示路径，存放路径长度等相关信息。（2）为来访客人提供图中任意景点相关信息查询。（3）为来访客人提供图中任意景点之间的问路查询，即任意两个景点之间的一条最短的简单路径。【测试数据】有学生根据实际情况指定。【实现提示】一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向图。顶点和边均含有相关信息。【选作内容】（1）求校园图的各个顶点的信息。（2）提供图中任意景点之间的问路查询，即求任意两个景点之间的所有路径。（3）提供校园图中多个景点的最佳访问路线查询，即求途径这多个景点的最短路径。《7.8习题》部分习题参考答案三、编程设计1．编写算法，在有n个顶点的有向图G的邻接表上，统计每个顶点的入度、出度和总度数。voidfunc7_1(ALGraphG,intid[],intod[],int&num){//id[]为每个结点的入度序列，od[]为每个结点的出度序列，num为总度数inti,n=G.vexnum;ArcNode*p;for(i=0;inextarc)-.65.- 第7章图结构{od[i]++;//出度累加id[p->adjvex]++;//入度累加num+=2;//总度数累加}}}voidmain(){ALGraphG1;GKindgk1=DG;cout<<"建立一个有向图的邻接表G1:n";CreateGraph_AL(G1,gk1);cout<<"有向图G1的邻接表为:n";DisplyAL(G1);inti,num,n=G1.vexnum,*OD=newint[n],*ID=newint[n];func7_1(G1,ID,OD,num);cout<<"结点的出度序列为:";for(i=0;i>G.vexnum>>G.arcnum;G.kind=kind;G.vexs=newVNode[G.vexnum];//为G.vexs分配存储空间G.arcs=newVType[G.vexnum*G.vexnum];//为G.arcs分配存储空间cout<<"按某种顺序输入"<>G.vexs[i].vex;//输入所有顶点的信息到G.vexs中}for(i=0;i>u>>v;}//根据顶点信息找到所在位置while(!((i=LocateVex_MG(G,u))&&(j=LocateVex_MG(G,v))));i--,j--;//i,j从位置值转换为下标值G.arcs[i*G.vexnum+j]=1;if(G.kind==DN||G.kind==UDN)cin>>G.arcs[i*G.vexnum+j];//输入相应边或弧的权重wif(G.kind==UDG||G.kind==UDN)//无向图的邻接矩阵是对称的G.arcs[j*G.vexnum+i]=G.arcs[i*G.vexnum+j];}}3．分别给出建立无向图、有向图和有向网的邻接表的算法。voidCreateGraph_AL(ALGraph&G,GKindkind){inti,j,k;VTypeu,v;ArcNode*pr,*pr1;G.kind=kind;cout<<"输入顶点数和边(弧)数vexnumarcnum:";cin>>G.vexnum>>G.arcnum;G.vertices=newVexNode[G.vexnum];//为顶点数组分配内存空间cout<<"按某种顺序输入"<>G.vertices[i].data;//输入所有顶点的信息到vex中G.vertices[i].nextarc=NULL;//设定初始的单链表为空}if(G.kind==DG||G.kind==UDG)cout<<"输入图中"<>u>>v;}while(!((i=LocateVex_AL(G,u))&&(j=LocateVex_AL(G,v))));i--,j--;//i,j从位置值转换为下标值pr=newArcNode;//动态分配单链表结点prpr->adjvex=j;pr->weight=0;if(G.kind==DN||G.kind==UDN)cin>>pr->weight;//输入对应边（弧）的权值pr->nextarc=G.vertices[i].nextarc;//将结点pr插入到第i个链表的首部G.vertices[i].nextarc=pr;if(G.kind==UDG||G.kind==UDN)//对于无向图(或网)将结点pr1插入到第j个链表的首部{pr1=newArcNode;//动态分配单链表结点pr1pr1->adjvex=i;pr1->weight=pr->weight;pr1->nextarc=G.vertices[j].nextarc;G.vertices[j].nextarc=pr1;//将结点pr1插入到第j个链表的首部}//endswitch}//endfor}4．编写算法，在无向图的邻接表结构上，生成无向图的邻接矩阵结构。-.65.-第7章图结构voidfunc74(MGraph&G1,ALGraphG){inti,j,n=G.vexnum;ArcNode*p;G1.arcnum=G.arcnum;G1.vexnum=G.vexnum;G1.kind=G.kind;G1.arcs=newint[n*n];//分配邻接矩阵空间G1.vexs=newVNode[n];//分配顶点信息空间for(i=0;inextarc){j=p->adjvex;G1.arcs[i*n+j]=1;}}}voidmain(){ALGraphG;MGraphG1;GKindgk=UDG;cout<<"建立一个无向图的邻接表G:n";CreateGraph_AL(G,gk);cout<<"无向图G的邻接表为:n";DisplyAL(G);func74(G1,G);cout<<"无向图G的邻接矩阵为:n";DisplyMG(G1);}运行演示结果(以图7.38为例)为：建立一个无向图的邻接表G:输入顶点数和边(弧)数vexnumarcnum:69按某种顺序输入6个顶点的值:123456输入图中9条边(弧)的信息uv:122425263645465616无向图G的邻接表为:0(1):[5][1]1(2):[5][4][3][0]2(3):[5]3(4):[5][4][1]4(5):[5][3][1]5(6):[0][4][3][2][1]无向图G的邻接矩阵为:010001100111000001010011010101111110-.65.-第7章图结构5．编写算法，在无向图的邻接矩阵结构上，生成无向图的邻接表结构。voidfunc75(ALGraph&G1,MGraphG){inti,j,n=G.vexnum;ArcNode*p;G1.arcnum=G.arcnum;G1.vexnum=G.vexnum;G1.kind=G.kind;G1.vertices=newVexNode[n];//为顶点数组分配内存空间for(i=0;iadjvex=j;p->weight=0;p->nextarc=G1.vertices[i].nextarc;//将结点p插入到第i个链表的首部G1.vertices[i].nextarc=p;}}6．编写算法，已知图有向G的邻接表存储结构：(1)求G中出度最大的顶点，并输出该顶点的编号；(2)求G中所有出度为0的顶点，并输出它们的编号；(3)判断G中是否存在边(i,j)（即存在弧和）。voidfunc7_6(ALGraphG,intmi,intmj){//算法思想是：首先统计图中所有顶点的出度到数组od[]中，再查找出度最大的顶点下标同时输出出度为零的下标。然后查找弧，如果查找成功则继续查找弧，如果再次成功则输出边(mi,mj)存在。inti,n=G.vexnum;int*od=newint[n],max=0,flag=0;-.65.- 第7章图结构ArcNode*p;for(i=0;inextarc)od[i]++;for(i=0;iod[max])max=i;if(od[i]==0){if(!flag){flag=1;cout<<"出度为零的顶点下标有:";}cout<nextarc)//查找if(p->adjvex==mj){flag++;break;}if(flag==1)for(p=G.vertices[mj].nextarc;p;p=p->nextarc)//查找if(p->adjvex==mi){flag++;break;}if(flag==2)cout<<"图中存在边（"<Stack){vex=*(pv-1);for(f=0,p=vex.nextarc;p;p=p->nextarc){//查找栈顶结点中未被访问的邻接点t=p->adjvex;if(G.vertices[t].flag==0){f=1;break;}}if(f)//访问栈顶结点的第一个未被访问的结点{-.65.- 第7章图结构cout<nextarc)//进入下一层{w=p->adjvex;if(!G.vertices[w].flag)DFS_ALG1(G,w,num);//通过递归调用实现深度优先遍历}}intfunc7_10(ALGraphG,VTypev0){inti,v=LocateVex_AL(G,v0)-1,num=0,n=G.vexnum;for(i=0;i，以及该活动的持续时间dut、最早开始时间ee、最迟开始时间el和是否是关键活动的信息(Y/N)。-.65.-'