图练习与答案.doc

一、应用题1 首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。367589421 1题图 答深度优先遍历序列：125967384宽度优先遍历序列：123456789注：（1）邻接表不唯一，这里顶点的邻接点按升序排列 （2）在邻接表确定后，深度优先和宽度优先遍历序列唯一 （3）这里的遍历，均从顶点1开始2给出图G：（1）画出G的邻接表表示图；（2）根据你画出的邻接表，以顶点为根，画出G的深度优先生成树和广度优先生成树。3105784216912534768910（2）深度优先生成树 （3）宽度优先生成树123465897103.在什么情况下，Prim算法与Kruskual算法生成不同的MST？答在有相同权值边时生成不同的MST，在这种情况下，用Prim或Kruskal也会生成不同的MST4已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以为起点，试画出构造过程）。1265432010116618101459答Prim算法构造最小生成树的步骤如24题所示，为节省篇幅，这里仅用Kruskal算法，构造最小生成树过程如下：（下图也可选(2,4)代替(3,4),(5,6)代替(1,5)）523916116210156435G=(V,E)是一个带有权的连通图,则：（1）请回答什么是G的最小生成树； （2）G为下图所示,请找出G的所有最小生成树。1435292875644 28题图答（1）最小生成树的定义见上面26题（2）最小生成树有两棵。（限于篇幅，下面的生成树只给出顶点集合和边集合，边以三元组（Vi,Vj,W）形式），其中W代表权值。V（G）=1，2，3，4，5 E1(G)=(4，5，2)，（2，5，4），（2，3，5），（1，2，7）；E2(G)=(4，5，2），（2，4，4），（2，3，5），（1，2，7）6请看下边的无向加权图。 （1）写出它的邻接矩阵。（2）按Prim算法求其最小生成树，并给出构造最小生成树过程中辅助数组的各分量值。辅助数组内各分量值： YClosedge2345678 U V.-UVexLowcostVexLowcostVexLowcostVexLowcostVexLowcostVexLowcostVexLowcostVexLowcost7已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、 伦敦(L) 、 东京(T) 、 墨西哥(M),下表给定了这六大城市之间的交通里程: 世界六大城市交通里程表(单位:百公里)PENPALTMPE109828121124N109585510832PA825839792L815539589T211089795113M124329289113 （1）画出这六大城市的交通网络图;（2）画出该图的邻接表表示法;（3）画出该图按权值递增的顺序来构造的最小(代价)生成树.8已知顶点1-6和输入边与权值的序列（如右图所示）：每行三个数表示一条边的两个端点和其权值，共11行。请你：（1）采用邻接多重表表示该无向网，用类PASCAL语言描述该数据结构，画出存储结构示意图，要求符合在边结点链表头部插入的算法和输入序列的次序。 （2）分别写出从顶点1出发的深度优先和广度优先遍历顶点序列，以及相应的生成树。（3）按prim算法列表计算，从顶点1始求最小生成树，并图示该树。1 2 51 3 8 1 4 32 4 62 3 2 3 4 43 5 13 6 104 5 74 6 115 6 159用最短路径算法，求如下图中a到z的最短通路。【（4）由顶点V1到顶点V3的最短路径。【中山大学 1994 四 （12分）】9用最短路径算法，求如下图中a到z的最短通路。65ced4bfghijza2249614223123459829题10已知图的邻接矩阵为：V1V2V3V4V5V6V7V8V9V10V10111000000V20001100000V30001010000V40000011010V50000001000V60000000110V70000000010V80000000001V90000000001V100000000000当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出：（1）以顶点V1为出发点的唯一的深度优先遍历；（2）以顶点V1为出发点的唯一的广度优先遍历；（3）该图唯一的拓扑有序序列。11已知一图如下图所示：（1）写出该图的邻接矩阵；（2）写出全部拓扑排序；（3）以v1为源点,以v8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径；（4）求V1结点到各点的最短距离。12（1）对于有向无环图，叙述求拓扑有序序列的步骤； （2）对于以下的图，写出它的四个不同的拓扑有序序列。二.算法设计题1设无向图G有n个顶点，m条边。试编写用邻接表存储该图的算法。（设顶点值用1n或0n-1编号）答: void CreatGraph (AdjList g)/建立有n个顶点和m 条边的无向图的邻接表存储结构int n,m; scanf(%d%d,&n,&m);for (i =1,i=n;i+)/输入顶点信息,建立顶点向量scanf(&gi.vertex); gi.firstarc=null;for (k=1;kadjvex=j; p-next=gi.firstarc; gi.firstarc=p;/将边结点链入 p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=i;p-next=gj.firstarc;gj.frstarc=p;/算法CreatGraph结束2请用流程图或类高级语言(c)表示算法。已知有向图有n个顶点,请写算法,根据用户输入的偶对建立该有向图的邻接表。即接受用户输入的(以其中之一为0标志结束),对于每条这样的边,申请一个结点,并插入到的单链表中,如此反复,直到将图中所有边处理完毕。提示：先产生邻接表的n个头结点（其结点数值域从1到n）。答 void CreatAdjList(AdjList g)/建立有向图的邻接表存储结构int n;scanf(%d,&n);for (i=1;iadjvex=j;p-next=gi.firstarc;gi.firstarc=p;scanf(&v1,&v2); 3设有向G图有n个点(用1,2,n表示),e条边,写一算法根据其邻接表生成其反向邻接表,要求算法复杂性为O(n+e)。答void InvertAdjList(AdjList gin,gout）/将有向图的出度邻接表改为按入度建立的逆邻接表 for (i=1;i=n;i+)/设有向图有n个顶点，建逆邻接表的顶点向量。 gini.vertex=gouti.vertex; gin.firstarc=null; for (i=1;iadjvex; s=(ArcNode *)malloc(sizeof(ArcNode);/申请结点空间。 s-adjvex=i; s-next=ginj.firstarc; ginj.firstarc=s; p=p-next;/下一个邻接点。 /while /for 4试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径（ij）。注意：算法中涉及的图的基本操作必须在存储结构上实现。答题目分析 在有向图中，判断顶点Vi和顶点Vj间是否有路径，可采用遍历的方法，从顶点Vi出发，不论是深度优先遍历（dfs）还是宽度优先遍历（bfs），在未退出dfs或bfs前,若访问到Vj，则说明有通路，否则无通路。设一全程变量flag。初始化为0，若有通路，则flag=1。int visited=0; /全局变量，访问数组初始化int dfs(AdjList g , vi) /以邻接表为存储结构的有向图g，判断顶点Vi到Vj是否有通路,返回1或0表示有或无 visitedvi=1; /visited是访问数组，设顶点的信息就是顶点编号。 p=gvi.firstarc; /第一个邻接点。 while ( p!=null) j=p-adjvex; if (vj=j) flag=1; return（1）; /vi 和 vj 有通路。 if (visitedj=0) dfs(g,j); p=p-next； /while if (!flag) return(0); /结束5设有向图用邻接表表示,图有n个顶点,表示为1至n,试写一个算法求顶点k的入度(1kn)。答 题目分析在有向图的邻接表中，求顶点的出度容易，只要简单在该顶点的邻接点链表中查结点个数即可。而求顶点的入度，则要遍历整个邻接表。 int count (AdjList g , int k )/在n个顶点以邻接表表示的有向图g中，求指定顶点k(1=k=n)的入度。 int count =0; for (i=1;iadjvex=k) count+; p=p-next;/while/if return(count); /顶点k的入度.6试编写求无向图G的连通分量的算法。要求输出每一连通分量的顶点值。(设图G已用邻接表存储)答题目分析 使用图的遍历可以求出图的连通分量。进入dfs或bfs一次，就可以访问到图的一个连通分量的所有顶点。void dfs ()visitedv=1; printf ( “%3d”,v); /输出连通分量的顶点。p=gv.firstarc;while (p!=null) if（visitedp-adjvex=0） dfs(p-adjvex); p=p-next;/while/ dfs void Count() /求图中连通分量的个数 int k=0 ; static AdjList g ; /设无向图g有n个结点 for (i=1;i0 | p!=null) while (p) if (p & visitedp-adjvex) p=p-next; else printf(p-adjvex); visitedp-adjvex=1; stack+top=p; p=gp-adjvex.firstarc; /else if (top0) p=stacktop-; p=p-next; /while /算法结束。算法讨论 以上算法适合连通图，若是非连通图，则再增加一个主调算法,其核心语句是for (vi=1;vi=n;vi+) if (!visitedvi) Traver(g,vi);8已知个 n顶点的有向图，用邻接矩阵表示，编写函数计算每对顶点的最短路径。答 本题用FLOYD算法直接求解如下： void ShortPath_FLOYD(AdjMatrix g) /求具有n个顶点的有向图每对顶点间的最短路径 AdjMatrix length; /lengthij存放顶点vi到vj的最短路径长度。 for (i=1;i=n;i+) for (j=1;j=n;j+) lengthij=gij; /初始化。 for (k=1;k=n;k+) for (i=1;i=n;i+) for (j=1;j=n;j+) if (lengthik+lengthkjlengthij) lengthij=lengthik+lengthkj; /算法结束9欲用四种颜色对地图上的国家涂色，有相邻边界的国家不能用同一种颜色（点相交不算相邻）。（1）试用一种数据结构表示地图上各国相邻的关系，（分）。（2）描述涂色过程的算法。（不要求证明）（分）。【浙江大学 2002 八 （18分）】答 题目分析 地图涂色问题可以用“四染色“定理。将地图上的国家编号（1到n），从编号1开始逐一涂色，对每个区域用1色，2色，3色，4色（下称“色数”）依次试探，若当前所取颜色与周围已涂色区域不重色，则将该区域颜色进栈；否则，用下一颜色。若1至4色均与相邻某区域重色，则需退栈回溯,修改栈顶区域的颜色。用邻接矩阵数据结构Cnn描叙地图上国家间的关系。n个国家用n阶方阵表示，若第i个国家与第j个国家相邻，则Cij=1，否则Cij=0。用栈s记录染色结果，栈的下标值为区域号，元素值是色数。void MapColor(AdjMatrix C) /以邻接矩阵C表示的n个国家的地区涂色 int s; /栈的下