作业4图 参考答案

《作业4图 参考答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构作业4图参考答案作业4.图l非编程作业参考答案：41375625abced1．已知带权无向图如图所示：(1).根据普里姆（Prim）算法，求它的从顶点a出发的最小生成树(写出过程，即添加顶点、边次序)；(2).根据克鲁斯卡尔（Kruskal）算法，求该图的最小生成树(写出过程，即添加边次序)。普里姆（Prim）算法：克鲁斯卡尔（Kruskal）算法：2aafbdgcheA697832513024212.已知带权有向图如图所示：(1).画出该图的邻接矩阵存储结构；(2).请写出该图的一个拓扑有序序列；(3).求从顶点a到其余各顶点之间的最短路经及最短路经长度，并给出计算过程。图G的一

2、个拓扑序列：abdfecghafbdecghabdfegchafbdegch数据结构作业4图参考答案从a出发到其它顶点的最短路径及其计算过程：l编程作业：请编写一个完整的程序，建立有向图的邻接表存储结构，并判断两顶点间是否有路径存在，要求：(1)主函数功能：①从键盘读入有向图的顶点数、有向边数，调用函数CreateAdjList()建立邻接表；②在主函数中输出每个顶点的数据域及其所有邻接点；③从键盘读入两个顶点vs、vt（）的数据域，调用函数Path()判断其间是否存在路径；(2)CreateAdjList()：建立有向图邻接表。功能：从键盘接收各顶点数据域及各条有向边所依附的顶点（如：“

3、2,3”代表该边依附的两个顶点在表头数组中的下标为2和3），要求单链表中结点按数据域升序排序；(3)Path():判断两顶点间是否存在路径，如果存在，将打印该路径（若存在多条路径，打印其中一条即可）。例：输入：请输入顶点和边的数目：8，9//(在main（）函数中输入)请输入各顶点数据域：abcdefgh//(在CreateAdjList()中输入)请输入各条边：1,2数据结构作业4图参考答案1,32,43,63,74,85,25,86,7输出：图的邻接表为：a23//（在main（）函数中输出）b4c67d8e28f7gh输入：请输入要查找是否存在路径的顶点：a,h输出：顶点a和d之间存

4、在路径，路经为：abdh输入：请输入要查找是否存在路径的顶点：a,e输出：顶点a和e之间不存在路径参考答案：#include#include#defineMax_Vertex_Num10typedefcharVertexType;intvisited[Max_Vertex_Num];intvisitpath[Max_Vertex_Num];intpathvexnum;intflag;//单链表结点(弧结点)typedefstructArcnode{intadjvex;//该弧所指向顶点（在表头数组中）的位置structArcnode*nextarc;/

5、/指向依附该顶点下一条边或弧}ArcNode;//头结点typedefstructVnode{VertexTypedata;//顶点信息数据结构作业4图参考答案Arcnode*firstarc;//指向第一条依附该顶点的弧}VNode,AdjList[Max_Vertex_Num];//图的定义typedefstruct{AdjListvertices;//表头数组intvexnum,arcnum;//图中顶点及弧的数目}ALGraph;//建立邻接表voidCreateAdjList(ALGraph&G){intk,i,j;ArcNode*p,*q,*s;for(k=1;k<=G.vex

6、num;k++){printf("inputdata:");fflush(stdin);scanf("%c",&G.vertices[k].data);G.vertices[k].firstarc=NULL;}for(k=0;kadjvex=j;s->nextarc=NULL;q=NULL;p=G.vertices[i].firstarc;while((p!=NULL)&&(j>p->adjvex)){

7、q=p;p=p->nextarc;}if(p==NULL&&q==NULL)G.vertices[i].firstarc=s;elseif(p==NULL&&q!=NULL)q->nextarc=s;elseif(p!=NULL&&q==NULL){数据结构作业4图参考答案G.vertices[i].firstarc=s;s->nextarc=p;}else{q->nextarc=s;s->nextarc=p;}}}//