实验8 最小生成树

电子信息学院 实验报告书 课 程 名 数据结构 题 目 最小生成树 实验类别 设计 班 级 BX1008 学 号 101003150809 姓 名 胡欢 2011 年 11 月 28 日 最小生成树 实验报告 0 1 实验题目 1 复习图的存储方法和图的遍历方法 2 进一步掌握图的非线性特点 递归特点和动态特点 3 掌握最小生成树的求解算法 2 实验内容 1 用 Prim 算法求最小生成树 2 输入网的二维矩阵 输出最小生成树 3 实验要求 1 利用 C C 语言完成算法设计和程序设计 2 上机调试通过实验程序 并检验程序运行的正确性 3 输入数据 并求最小生成树 4 给出具体算法分析 包括时间复杂度和空间复杂度等 5 撰写实验报告 把输入实验数据及运行结果用抓图的形式粘贴到实验报告上 4 实验步骤与源程序 实验步骤 1 首先 为了使程序更为通俗易懂 我们在程序开头 初始化形成 n 1 条边的生成树 2 初始化矩阵 编写满足条件的无向图的邻接矩阵 要注意的是 在初始化矩阵的时候全 部元素设为无穷大 3 根据题意 编写程序 用 Prim 算法求最小生成树 源代码 include define inf 9999 define max 40 void prim int g max int n prim 的函数 int lowcost max closest max int i j k min for i 2 i n i n 个顶点 n 1 条边 lowcost i g 1 i 初始化 closest i 1 顶点未加入到最小生成树中 lowcost 1 0 标志顶点 1 加入 U 集合 最小生成树 实验报告 1 for i 2 i n i 形成 n 1 条边的生成树 min inf k 0 for j 2 j n j 寻找满足边的一个顶点在 U 另一个顶 点在 V 的最小边 if lowcost j min k j printf d d d t closest k k min lowcost k 0 顶点 k 加入 U for j 2 j n j 修改由顶点 k 到其他顶点边的权值 if g k j lowcost j lowcost j g k j closest j k printf n int adjg int g max 建立无向图 int n e i j k v1 v2 weight printf 输入顶点个数 边的条数 scanf d d for i 1 i n i for j 1 j n j g i j inf 初始化矩阵 全部元素设为无穷大 for k 1 k e k 最小生成树 实验报告 2 printf 输入第 d 条边的起点 终点 权值 k scanf d d d g v1 v2 weight g v2 v1 weight return n void prg int g max int n 输出无向图的邻接矩阵 int i j for i 0 i n i printf d t i for i 1 i n i printf n d t i for j 1 j n j printf g i j inf t d t g i j printf n void main int g max max n n adjg g printf 输入无向图的邻接矩阵 n prg g n printf 最小生成树的构造 n prim g n 最小生成树 实验报告 3 5 测试数据与实验结果 图图 5 5 测试数据及实验结果测试数据及实验结果 6 结果分析与实验体会 由截图可知用 Prim 算法求最小生成树和输入网的二维矩阵 输出最小生成树功能基本 实现 通过该实验 本人对求最小生成树的 prim 算法有了更深刻的理解 对用数组存放边 的权值和基于数组的指针操作有了更深的认识 在刚开始调试的时候总输出乱码 经过上网 查阅才了解到字符数组与 C 风格的 字符串是有区别的 后者是以 NULL 结尾的 前者必须将 最后一