问答题
阅读下列函数说明和c代码，将应填入(n)处的字句写在对应栏内。<br>【说明】<br>所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。<br>应用贪婪法求解该问题。程序先计算由各点构成的所有边的长度(作为边的权值)，按长度大小对各边进行排序后，按贪婪准则从排序后的各边中选择边组成回路的边，贪婪准则使得边的选择按各边长度从小到大选择。<br>函数中使用的预定义符号如下：<br>define M 100<br>typedef struct{/*x为两端点p1、p2之间的距离，p1、p2所组成边的长度*/<br>float x;<br>int p1, p2;<br>}tdr;<br>typedef struct{/*p1、p2为和端点相联系的两个端点，n为端点的度*/<br>int n, P1, p2;<br>}tr;<br>typedef struct{/*给出两点坐标*/<br>float x,y;<br>}tpd;<br>typedef int tl[M];<br>int n=10;<br>【函数】<br>float distance(tpd a,tpd b);/*计算端点a、b之间的距离*/<br>void sortArr(tdr a[M], int m);<br>/*将已经计算好的距离关系表按距离大小从小到大排序形成排序表，m为边的条数*/<br>int isCircuit(tr[M], int i, int j);<br>/*判断边(i, j)选入端点关系表r[M]后，是否形成回路，若形成回路返回0*/<br>void selected(tr r[M], int i, int j);/*边(i,j)选入端点关系表r*/<br>void course(tr r[M], tl 1[M]);/*从端点关系表r中得出回路轨迹表*/<br>void exchange(tdr a[M], int m, int b);<br>/*调整表排序表，b表示是否可调，即是否有边长度相同的边存在*/<br>void travling(tpd pd[M], int n, float dist, t1 locus[M])<br>/*dist记录总路程*/<br>{<br>tdr dr[M];/*距离关系表*/<br>tr r[M];;/*端点关系表*/<br>int i, j, k, h, m;/*h表示选入端点关系表中的边数*/<br>int b;/*标识是否有长度相等的边*/<br>k=0;<br>/*计算距离关系表中各边的长度*/<br>for(i=1;i＜n;i++){<br>for(j=i+1;j＜=n;j++){<br>k++;<br>dr[k].x=(1);<br>dr[k].p1=i;<br>dr[k].p2=j;<br>}<br>}<br>m=k;<br>sortArr(dr,m);/*按距离大小从小到大排序形成排序表*/<br>do{<br>b=1;<br>dist=0;<br>k=h=0;<br>do{<br>k++;<br>i=dr[k].p1;<br>j=dr[k].p2;<br>if((r[i].n＜=1)&&(r[j].n＜=1)){/*度数不能大于2*/<br>if((2)){<br>/*若边(i，j)加入r后形成回路，则不能加入*/<br>(3);<br>h++;<br>dist+=dr[k].x;<br>}else if((4)){<br>/*最后一边选入r成回路，则该边必须加入且得到解*/<br>selected(r,i,j);<br>h++;<br>&n
问答题
阅读下列算法说明和算法，将应填入(n)的字句写在对应的栏内。<br>[说明]<br>下列最短路径算法的具体流程如下：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。该算法的基本思想是：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1条互不构成回路的权值最小边为止。<br>[算法]<br>/*对图定义一种新的表示方法，以一维数组存放图中所有边，并在构建图的存储结构时将它构造为一个“有序表”。以顺序表MSTree返回生成树上各条边。*/<br>typedef struct{<br>VertexType vex1;<br>VertexType vex2;<br>VRType weight;<br>} EdgeType;<br>typedef ElemType EdgeType;<br>typedef struct { //有向网的定义<br>VertexType vexs [MAX_VERTEX_N U M ]; //顶点信息<br>EdgeType edge[ MAX_EDGE_NUM]; //边的信息<br>int vexnum, arcnum; //图中顶点的数目和边的数目<br>I ELGraph;<br>void MiniSpanTree_Kruskal(ELGraph G,SqList& MSTree) {<br>//G, edge 中依权值从小到大存放有向网中各边<br>//生成树的边存放在顺序表MSTree中<br>MFSetF;<br>InitSet(F, G. vexnum ); //将森林F初始化为N棵树的集合<br>InitList (MSTree, G. vexnum); //初始化生成树为空树<br>i=0;k=1;<br>while(k＜(1)){<br>e = G. edge[i]; //取第i条权值最小的边<br>/*函数fix_mfset返回边的顶点所在树的树的根代号，如果边的两个顶点所在树的树根相同，则说明它们已落在同一棵树上。 */<br>ri = fix_mfset(F, LocateVex(e. vex1) );<br>r2=(2); //返回两个顶点所在树的树根<br>if(r1 (3) r2) { //选定生成树上第k条边<br>if(Listlnsert(MSTree,k,e){(4); //插入生成树<br>mix_mfset(E, r1,r2); //将两棵树归并为一棵树<br>}<br>(5); //继续考察下一条权值最小边<br>}<br>DestroySet (F); }<br>}
套餐购买该问题答案仅对会员开放，欢迎开通会员 ¥ 19.9
0.64/天
1个月(不限次)
¥ 19.9
1000次
(不限时)
¥ 29.9
0.32/天
3个月(不限次)
¥ 59.9
0.16/天
1年(不限次)
立即支付
微信支付 
支付宝支付