图练习与答案

、应用题然后写出对其分别进行深1.首先将如下图所示的无向图给出其存储结构的邻接链表表示,度，广度优先遍历的结果。然后写出对其分别进行深答.深度优先遍历序列：宽度优先遍历序列:1259673841234567892.2.给出图G:注：（1）邻接表不唯一，这里顶点的邻接点按升序排列在邻接表确定后，深度优先和宽度优先遍历序列唯一这里的遍历，均从顶点1开始G的邻接表表示图;画出(1).G的深度优先生成树和广度优先生成树。3.在什么情况下，Prim算法与Kruskual算法生成不同的MST?答.在有相同权值边时生成不同的MST在这种情况下，用Prim或Kruskal也会生成不同的MST

4.已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）O答.Prim算法构造最小生成树的步骤如构造最小生成树过程如下：（下图也可选24题所示，为节省篇幅，这里仅用Kruskal算法,4.已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）O答.Prim算法构造最小生成树的步骤如构造最小生成树过程如下：（下图也可选24题所示，为节省篇幅，这里仅用Kruskal算法,(2,4)代替(3,4),(5,6)代替(1,5))1105211G=（V,E）是一个带有权的连通图，则：.请回答什么是G的最小生成树；.G为下图所示，请找出G的所有最小生成树。答.（1）最小生成树的定义见上面26题（2）最小生成树有两棵。答.（1）最小生成树的定义见上面26题（2）最小生成树有两棵。（限于篇幅，下面的生成树只给出顶点集合和边集合，边以三元组（W弋表权值。Vi,Vj,W)形式），其中V(G)={1,2,3,4,5}E1(G)={(4,5,2),(2,5,4),(2,3,5),E2(G尸{(4,5,2),(2,4,4),(2,3,5),(1,2,7)};(1，2,7)}6.请看下边的无向加权图。（1）.写出它的邻接矩阵。（2）.按Prim算法求其最小生成树,并给出构造最小生成树过程中辅助数组的各分量值。辅助数组内各分量值：YClosedge2345678UV.-UVexLowcostVexLowcostVexLowcostVexLowcostVexLowcostVexLowcostVexLowcostVexLowcost7.已知世界六大城市为：北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M),下表给定了这六大城市之间的交通里程：世界六大城市交通里程表(单位：百公里)PENPALTMPE109828121124N109585510832PA825839792L815539589T211089795113M124329289113(1).画出这六大城市的交通网络图；(2).画出该图的邻接表表示法；(3).画出该图按权值递增的顺序来构造的最小(代价)生成树.8.已知顶点1-6和输入边与权值的序列(如右图所示)：每行三个数表示一条边的两个端点和其权值，共11行。请你：.采用邻接多重表表示该无向网，用类PASCA阴言描述该数据结构，画出存储结构示意图，要求符合在边结点链表头部插入的算法和输入序列的次序。.分别写出从顶点1出发的深度优先和广度优先遍历顶点序列，以及相应的生成树。.按prim算法列表计算，从顶点1始求最小生成树，并图示该树。1251381432462323443513610457461156159.用最短路径算法，求如下图中a到z的最短通路。【(4).由顶点V1到顶点V3的最短路径。【中山大学1994四(12分)】.用最短路径算法，求如下图中a到z的最短通路。.已知图的邻接矩阵为:

V1V2V3V4V5V6V7V8V9V10V10111000000V20001100000V30001010000V40000011010V50000001000V60000000110V70000000010V80000000001V90000000001V100000000000当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出(1).以顶点V1为出发点的唯一的深度优先遍历;(2).以顶点V1为出发点的唯一的广度优先遍历;(3).该图唯一的拓扑有序序列。.已知一图如下图所示：.写出该图的邻接矩阵；.写出全部拓扑排序；.以v1为源点，以v8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径；.求V1结点到各点的最短距离。(1).对于有向无环图，叙述求拓扑有序序列的步骤；2).对于以下的图，写出它的四个不同的拓扑有序序歹U。.设无向图G有n个顶点，m条边。试编写用邻接表存储该图的算法。(设顶点值用1〜n或0〜n-1编号)答：voidCreatGraph(AdjListg)//建立有n个顶点和m条边的无向图的邻接表存储结构{intn,m;scanf("%d%d",&n,&m);for(i=1,i<=n;i++)〃输入顶点信息，建立顶点向量{scanf(&g[i].vertex);g[i].firstarc=null;}for(k=1;k<=m;k++)//输入边信息{scanf(&v1,&v2);//输入两个顶点i=GraphLocateVertex(g,v1);j=GraphLocateVertex(g,v2);//顶点定位p=(ArcNode*)malloc(sizeof(ArcNode));//申请边结点p->adjvex=j;p->next=g[i].firstarc;g[i].firstarc=p;//将边结点链入p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=i;p->next=g[j].firstarc;g[j].frstarc=p;}}//算法CreatGraph结束.请用流程图或类高级语言(c)表示算法。已知有向图有n个顶点，请写算法，根据用户输入的偶对建立该有向图的邻接表。即接受用户输入的<vi,vj>(以其中之一为0标志Z束)，对于每条这样的边，申请一个结点，并插入到的单链表中，如此反复，直到将图中所有边处理完毕。提示：先产生邻接表的n个头结点(其结点数值域从1到n)。答.voidCreatAdjList(AdjListg)//建立有向图的邻接表存储结构{intn;scanf("%d",&n);for(i=1;i<=n;j++){scanf(&g[i].vertex);g[i].firstarc=null;}〃输入顶点信息scanf(&v1,.&v2);while(v1&&v2)//题目要求两顶点之一为0表示结束{i=GraphLocateVertex(g2,v1);p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->next=g[i].firstarc;g[i].firstarc=p;scanf(&v1,&v2);}}.设有向G图有n个点(用1,2,…,n表示),e条边，写一算法根据其邻接表生成其反向邻接表，要求算法复杂性为O(n+e)。答.

voidInvertAdjList(AdjListgin,gout)//将有向图的出度邻接表改为按入度建立的逆邻接表{for(i=1;i<=n;i++)〃设有向图有n个顶点，建逆邻接表的顶点向量。{gin[i].vertex=gout[i].vertex;gin.firstarc=null;}for(i=1;i<=n;i++)//邻接表转为逆邻接表。{p=gout[i].firstarc;//取指向邻接表的指针。while(p!=null){j=p->adjvex;s=(ArcNode*)malloc(sizeof(ArcNode));//申请结点空间。s->adjvex=i;s->next=gin[j].firstarc;gin[j].firstarc=s;p=p->next;//下一个邻接点。}//while}//for}.试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点V到顶点V的路径(i<>j)。注意：算法中涉及的图的基本操作必须在存储结构上实现。答.[题目分析]在有向图中，判断顶点Vi和顶点Vj间是否有路径，可采用遍历的方法，从顶点Vi出发，不论是深度优先遍历(dfs)还是宽度优先遍历(bfs),在未退出dfs或bfs前，若访问到Vj,则说明有通路，否则无通路。设一全程变量flag。初始化为0,若有通路，则flag=1。intvisited[]=0;//全局变量，访问数组初始化intdfs(AdjListg,vi)//以邻接表为存储结构的有向图g,判断顶点Vi到Vj是否有通路，返回1或0表示有或无{visited[vi]=1;//visited是访问数组，设顶点的信息就是顶点编号。p=g[vi].firstarc;//第一个邻接点。while(p!=null){j=p->adjvex;if(vj==j){flag=1;return(1);}//vi和vj有通路。if(visited[j]==0)dfs(g,j);p=p->next;}//whileif(!flag)return(0);}//结束.设有向图用邻接表表示，图有n个顶点，表示为1至n,试写一个算法求顶点k的入度(1<k<n)。答.[题目分析]在有向图的邻接表中，求顶点的出度容易，只要简单在该顶点的邻接点链表中查结点个数即可。而求顶点的入度，则要遍历整个邻接表。intcount(AdjListg,intk){intcount=0;for(i=1;i<=n;i++)//

if(i!=k)//{p=g[i].firstarc;////在{intcount=0;for(i=1;i<=n;i++)//

if(i!=k)//{p=g[i].firstarc;//求顶点k的入度要遍历整个邻接表。顶点k的邻接链表不必计算取顶点i的邻接表。while(p){if(p->adjvex==k)count++;p=p->next;}//while}//ifreturn(count);//顶点k的入度.}.试编写求无向图G的连通分量的算法。要求输出每一连通分量的顶点值。(设图G已用邻接表存储)答.[题目分析]使用图的遍历可以求出图的连通分量。进入dfs或bfs一次，就可以访问到图的一个连通分量的所有顶点。voiddfs(){visited[v]=1;printf("%3d,v);//输出连通分量的顶点。p=g[v].firstarc;while(p!=null){if(visited[p->adjvex==0])dfs(p->adjvex);p=p->next;}//while}//dfsvoidCount()//求图中连通分量的个数{intk=0;staticAdjListg;//设无向图g有n个结点for(i=1;i<=n;i++)if(visited[i]==0){printf("\n第％~个连通分量：\n",++k);dfs(i);}//if}//Count算法中visited口数组是全程变量，每个连通分量的顶点集按遍历顺序输出。这里设顶点信息就是顶点编号，否则应取其g[i].vertex分量输出。.写出图的深度优先搜索DFS算法的非递归算法。答.voidTraver(AdjListg,vertypev)//图g以邻接表为存储结构，算法从顶点v开始实现非递归深度优先遍历。{structarc*stack口；visited[v]=1;printf(v);//输出顶点vtop=0;p=g[v].firstarc;stack[++top]=p;while(top>0||p!=null){while(p)if(p&&visited[p->adjvex])p=p->next;else{printf(p->adjvex);visited[p->adjvex]=1;stack[++top]=p;p=g[p->adjvex].firstarc;}//elseif(top>0){p=stack[top--];p=p->next;}}//while}//算法结束。[算法讨论]以上算法适合连通图，若是非连通图，则再增加一个主调算法，其核心语句

是for(vi=1;vi<=n;vi++)是for(vi=1;vi<=n;vi++)if(!visited[vi])Traver(g,vi);已知个n顶点的有向图，用邻接矩阵表示，编写函数计算每对顶点的最短路径。答.本题用FLOYDT法直接求解如下：voidShortPath_FLOYD(AdjMatrixg)//求具有n个顶点的有向图每对顶点间的最短路径{AdjMatrixlength;//length[i][j]存放顶点vi到vj的最短路径长度。for(i=1;i<=n;i++)for(j=1;j<=n;j++)length[i][j]=g[i][j];//初始化。for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(length[i][k]+length[k][j]<length[i][j])length[i][j]=length[i][k]+length[k][j];}//算法结束欲用四种颜色对地图上的国家涂色，有相邻边界的国家不能用同一种颜色(点相交不算相邻)。.试用一种数据结构表示地图上各国相邻的关系，(6分)。.描述