作业4图 参考答案

1、数据结构作业 4图 参考答案图非编程作业参考答案：1已知带权无向图如图所示：a(1). 根据普里姆（Prim）算法，求它的从顶点 a出发的最小生成树(写出过程，即添加顶点、边次序)；(2). Kruskal树(写出过程，即添加边次序)。2614bd753e普里姆（Prim）算法：aaaaea22221 44b c dc ddd3e3e3克鲁斯卡尔（Kruskal）算法：aab c deaaa2221 41b c d1b c d1b c db c d3e3eee已知带权有向图如图所示：bc(1). 画出该图的邻接矩阵存储结构；(2). 请写出该图的一个拓扑有序序列；(3). 求从顶点 a 到其余

2、各顶点之间的最过程。5291862adeh73fga b c d e f g ha 0 2 6 9 图G的一个拓扑序列：b 0 30 1 abdfecghabdfegchafbdecghafbdegchc 0 5 d 0 2 8 0 7 3 0 24 0 21ef g 0h 数据结构作业 4图 参考答案从a出发到其它顶点的最短路径及其计算过程：编程作业：请编写一个完整的程序，建立有向图的邻接表存储结构，并判断两顶点间是否有路径存在，要求：(1) 主函数功能：从键盘读入有向图的顶点数、有向边数，调用函数CreateAdjList()建立邻接表；在主函数中输出每个顶点的数据域及其所有邻接点；从键盘

3、读入两个顶点（）的数据域，调、v v s tst用函数Path()判断其间是否存在路径；(2) CreateAdjList()：建立有向图邻接表。功能：从键盘接收各顶点数2,3”代表该边依附的两个顶点在表头数组中的下标为2和3序；(3) Path(): 例：输入：请输入顶点和边的数目：8，9 /(在 main（）函数中输入)请输入各顶点数据域：a b c d e f g h/(在 CreateAdjList()中输入)请输入各条边：1,2数据结构作业 4图 参考答案1,32,43,63,74,85,25,86,7输出：图的邻接表为：a 2 3 /（在 main（）函数中输出）b 4c 6 7d

4、 8e 2 8f 7gh输入： 请输入要查找是否存在路径的顶点：a,h输出： 顶点 a和 d之间存在路径，路经为：a b d h输入： 请输入要查找是否存在路径的顶点：a,e输出： 顶点 a和 e之间不存在路径参考答案：#include#include#define Max_Vertex_Num 10typedef char VertexType;int visitedMax_Vertex_Num;int visitpathMax_Vertex_Num;int pathvexnum;int flag;/单链表结点(弧结点)typedef struct Arcnodeint adjvex; /该

5、弧所指向顶点（在表头数组中）的位置struct Arcnode *nextarc; /指向依附该顶点下一条边或弧 ArcNode;/头结点typedef struct Vnode VertexType data;/顶点信息数据结构作业 4图 参考答案Arcnode *firstarc; /指向第一条依附该顶点的弧 VNode, AdjListMax_Vertex_Num;/图的定义typedef structAdjListintvertices;/ 表头数组vexnum, arcnum; / 图中顶点及弧的数目 ALGraph;/建立邻接表void CreateAdjList (ALGraph

6、 &G)int k,i,j;ArcNode *p,*q,*s;for(k=1;k=G.vexnum;k+)printf(input data:);fflush(stdin);scanf(%c,&G.verticesk.data);G.verticesk.firstarc=NULL;for(k=0;kadjvex=j;s-nextarc=NULL;q=NULL;p=G.verticesi.firstarc;while(p!=NULL)&(jp-adjvex)q=p; p=p-nextarc;if(p=NULL&q=NULL)G.verticesi.firstarc=s;else if(p=NUL

7、L&q!=NULL)q-nextarc=s;else if(p!=NULL&q=NULL)数据结构作业 4图 参考答案G.verticesi.firstarc=s;s-nextarc=p;elseq-nextarc=s;s-nextarc=p;/按深度优先判断顶点 vx和 vy间是否存在路径void DFSPath(ALGraph G, int v, VertexType vy) ArcNode *w;int i;visitpath+pathvexnum=v;visitedv=1;w=G.verticesv.firstarc;/顶点 v的第一个邻接点while(w!=NULL) /是否存在i=

8、w-adjvex; /邻接点下标if(G.verticesi.data=vy)flag=1;return;else if(flag=0&visitedi=0)DFSPath(G,i,vy);w=w-nextarc; /v的下一个邻接点if(flag=0)pathvexnum-;/从路径上删除 Vvoid Path(ALGraph G, VertexType vx, VertexType vy)int i;数据结构作业 4图 参考答案for(i=1;i=Max_Vertex_Num;i+)visitedi=0;for(i=1;i=G.vexnum;i+)if(G.verticesi.data=v

9、x)break;DFSPath(G,i,vy);if(flag=1)printf(顶点%c到顶点%c之间存在路径，路经为：,vx,vy);for(i=1;i=pathvexnum;i+)printf(%ct,G.verticesvisitpathi.data);printf(%cn,vy);elseprintf(顶点%c到顶点%c之间不存在路径n,vx,vy);void main()ALGraph G;int i;VertexType vx,vy;ArcNode *p;printf(请输入顶点和边的数目：);scanf(%d,%d,&G.vexnum,&G.arcnum);CreateAdjList(G);print