xx 学 院 《数据结构与算法》课程设计 报 告 书 课程设计题目 PRIM算法求最小生成树 院系名称计算机科学与技术系 专 业 （班 级） 姓 名 （学 号） 指 导 教 师 完 成 时 间 1 一 、 问 题 分 析 和 任 务 定 义 在 该 部 分 中 主 要 包 括 两 个 方 面 ： 问 题 分 析 和 任 务 定 义 ； 1 问 题 分 析 本 次 课 程 设 计 是 通 过 PRIM（ 普 里 姆 ） 算 法 ， 实 现 通 过 任 意 给 定 网 和 起 点 ， 将 该 网 所 对应 的 所 有 生 成 树 求 解 出 来 。 在 实 现 该 本 设 计 功 能 之 前 ， 必 须 弄 清 以 下 三 个 问 题 ： 1． 1 关 于 图 、 网 的 一 些 基 本 概 念 1． 1． 1 图 图 G 由 两 个 集 合 V 和 E 组 成 ， 记 为 G=（ V， E）， 其 中 V 是 顶 点 的 有 穷 非 空集 合 ， E 是V 中 顶 点 偶 对 的 有 穷 集 ， 这 些 顶 点 偶 对 称 为 边 。 通 常 ， V（ G） 和E（ G） 分 别表 示 图 G 的 顶 点 集 合 和 边 集 合 。 E（ G） 也 可 以 为 空 集 。 则 图 G 只 有 顶 点 而 没 有 边 。 1． 1． 2 无 向 图 对 于 一 个 图 G， 若 边 集 E（ G） 为 无 向 边 的 集 合 ， 则 称 该 图 为 无 向 图 。 1． 1． 3 子 图 设 有 两 个 图 G=（ V， E） G’=（ V’，） ,若 V’是 V 的 子 集 ， 即 V’V ， 且E’是 E 的 子 集 ， 即 E’E ， 称 G’是 G 的 子 图 。 1． 1． 4 连 通 图 若 图 G 中 任 意 两 个 顶 点 都 连 通 ， 则 称 G 为 连 通 图 。 1． 1． 5 权 和 网 在 一 个 图 中 ， 每 条 边 可 以 标 上 具 有 某 种 含 义 的 数 值 ， 该 数 值 称 为 该 边 的权 。 把 边 上 带 权 的 图 称 为 网 。 如图 1 所 示 。 1． 2 理解 生 成 树 和 最小生 成 树 之 间的 区别 和 联系 1． 2． 1 生 成 树 在 一 个 连 通 图 G 中 ， 如果取它的 全部 顶 点 和 一 部 分 边 构成 一 个 子 图 G’，即 ： V（ G’） = V...
