作业4图 参考答案作业4图参考答案 参考答案.doc

作业4. 图 非编程作业参考答案： 已知带权无向图如图所示： (1). 根据普里姆（Prim）算法，求它的从顶点a出发的最小生成树(写出过程，即添加顶点、边次序)； (2). 根据克鲁斯卡尔（Kruskal）算法，求该图的最小生成树(写出过程，即添加边次序)。 普里姆（Prim）算法： 克鲁斯卡尔（Kruskal）算法： 2. 已知带权有向图如图所示： (1). 画出该图的邻接矩阵存储结构； (2). 请写出该图的一个拓扑有序序列； (3). 求从顶点a到其余各顶点之间的最短路经及最短路经长度，并给出计算过程。 图G的一个拓扑序列： abdfecgh afbdecgh abdfegch afbdegch 从a出发到其它顶点的最短路径及其计算过程： 编程作业： 请编写一个完整的程序，建立有向图的邻接表存储结构，并判断两顶点间是否有路径存在，要求： (1) 主函数功能：①从键盘读入有向图的顶点数、有向边数，调用函数CreateAdjList()建立邻接表；②在主函数中输出每个顶点的数据域及其所有邻接点；③从键盘读入两个顶点vs、vt（）的数据域，调用函数Path()判断其间是否存在路径； (2) CreateAdjList()：建立有向图邻接表。功能：从键盘接收各顶点数据域及各条有向边所依附的顶点（如：“2,3”代表该边依附的两个顶点在表头数组中的下标为2和3），要求单链表中结点按数据域升序排序； (3) Path(): 判断两顶点间是否存在路径，如果存在，将打印该路径（若存在多条路径，打印其中一条即可）。 例：输入：请输入顶点和边的数目：8，9 //(在main（）函数中输入) 请输入各顶点数据域：a b c d e f g h //(在CreateAdjList()中输入) 请输入各条边：1,2 1,3 2,4 3,6 3,7 4,8 5,2 5,8 6,7 输出：图的邻接表为：a 2 3 //（在main（）函数中输出） b 4 c 6 7 d 8 e 2 8 f 7 g h 输入： 请输入要查找是否存在路径的顶点：a,h 输出： 顶点a和d之间存在路径，路经为：a b d h 输入： 请输入要查找是否存在路径的顶点：a,e 输出： 顶点a和e之间不存在路径 参考答案： #includestdio.h #includemalloc.h #define Max_Vertex_Num 10 typedef char VertexType; int visited[Max_Vertex_Num]; int visitpath[Max_Vertex_Num]; int pathvexnum; int flag; //单链表结点(弧结点) typedef struct Arcnode { int adjvex; //该弧所指向顶点（在表头数组中）的位置 struct Arcnode *nextarc; //指向依附该顶点下一条边或弧 } ArcNode; //头结点 typedef struct Vnode { VertexType data; //顶点信息 Arcnode *firstarc; //指向第一条依附该顶点的弧 } VNode, AdjList[Max_Vertex_Num]; //图的定义 typedef struct { AdjList vertices; // 表头数组 int vexnum, arcnum; // 图中顶点及弧的数目 } ALGraph; //