【vfp精品源码栏目提醒】:网学会员为需要vfp精品源码的朋友们搜集整理了AAA数据结构课程设计报告 - 大学课件相关资料,希望对各位网友有所帮助!
////////大学 数据结构课程设计总结报告设计题目:以邻接链表的方式确定一个无向网学生班 级:学 号:指导教师: 年 月 日一、设计题目 题目 3. 以邻接链表的方式确定一个无向网,完成: ⑴建立并显示出它的邻接矩阵; (并随时显示队列的入、出情况) ⑵对该图进行广度优先遍历,显示遍历的结果, ; ⑶用普里姆算法构造其最小生成树,随时显示其构造的过程; ⑷用克鲁斯卡尔算法构造其最小生成树,随时显示其构造的过程;二、运行环境(软、硬件环境) 硬件环境: CPU:1000MHz 以上 内存:256MB 以上 硬盘:60G 以上 软件环境: 系统平台:Windows 2000 / Windows XP / Windows Vista / Windows 7 运行环境:TC 3.0 / Microsoft Visual C 6.0 三、算法设计的思想 1、存储结构:邻接矩阵 邻接表。
2、遍历方式: 广度优先搜索BFS 3、实现最小生成树的方式:普里姆算法(Prime 算法)和克鲁斯卡尔算法(kruskai 算法),具体实现见代码。
四、算法的流程图五、算法设计分析及截图 (1)邻接表的建立. 邻接链表的头结点所使用的结构体: typedef struct node int adjvex struct node next JD typedef struct tnode int vexdata struct node firstarc TD 建立某无向图的邻接链表,所用函数:int crt_linklistTD gint aM,其中调用函数 int loc_vertexTD gint vexint n:找出边的头尾结点。
主要利用 for 循环实现顶点和边 的输出,在确定边的时候,将该边的权值取地址给 ai-1j-1和 aj-1i-1。
测试结果: 邻接表的建立: 邻接矩阵的建立:(2)广度优先遍历 使用 void traverTD gint n函数实现, 利 调用函数 void bfsTD gint vint visited: 用 队列实现遍历过程,并用 for 循环输出每次入队出队情况。
测试结果:(3)最小生成树的方式:普里姆算法(Prime 算法) . 使用函数: void minispantree_PRIMint aMint n,利用邻接矩阵实现 测试结果: 2---4; 1---2; 3---4;(4) 最小生成树的方式:克鲁斯卡尔算法(kruskai 算法) 算法思想:设 NVE是连通网,TE 是 N 上最小生成树中边的集合 初始令 Uu0u0∈V TEΦ 在所有 u∈Uv∈V-U 的边uv∈E 中,找一条代价最小的边u0v0 将u0v0并入集合 TE,同时 v0 并入 U 重复上述操作直至 UV 为止,则 TVTE为 N 的最小生成树 算法实现:图用邻接矩阵表示 边的表示方式:typedef struct int vexhvext int weight int flag EDGE 测试结果:六、源代码 include include define M 10 define MAX 100 typedef struct node int adjvex struct node next JD typedef struct tnode int vexdata struct node firstarc TD typedef struct int data int jihe VEX typedef struct int vexhvext int weight int flag EDGE void minitree_KRUSKALvoid int nimminkj VEX tM EDGE eM printfInput number of vertex and edge: scanfddnm fori1i