最小生成树问题课件

榆林学院 12 届课程设计 最小生成树问题 课程设计说明书 学生姓名 赵佳 学 号 院 系 信息工程学院 专 业 计算机科学与技术 班 级 计 14 本 1 指导教师 答辩时间 年 月 日 最小生成树问题 一 一 问题陈述问题陈述 最小生成树问题 设计要求 在 n 个城市之间建设网络 只需保证连通即可 求最经济的 架设方法 存储结构采用多种 求解算法多种 二 二 需求分析需求分析 1 在 n 个城市之间建设网络 只需保证连通即可 2 求城市之间最经济的架设方法 3 采用多种存储结构 求解算法也采用多种 三 三 概要设计概要设计 1 功能模块图 开始 创建一个图 功能选择 1 建立 邻接矩 阵 2 建立 邻接表 3 krus kal 算 法 4 PRIM 算 法 结束 2 功能描述 1 CreateUDG 创建一个图 通过给用户信息提示 让用户将城市信息及城市之间的联系 关系和连接权值写入程序 并根据写入的数据创建成一个图 2 Switch 功能选择 给用户提示信息 让用户选择相应功能 3 Adjacency Matrix 建立邻接矩阵 将用户输入的数据整理成邻接矩阵并显现在屏幕上 4 Adjacency List 建立邻接表 将用户输入的数据整理成临接表并显现在屏幕上 5 MiniSpanTree KRSL kruskal 算法 利用 kruskal 算法求出图的最小生成树 即 城市之间最 经济的连接方案 6 MiniSpanTree PRIM PRIM 算法 利用 PRIM 算法求出图的最小生成树 即 城市之间最经济的 连接方案 四 四 详细设计详细设计 本次课程设计采用两种存储结构以及两种求解算法 1 两种存储结构的存储定义如下 typedef struct Arcell double adj Arcell AdjMatrix MAX VERTEX NUM MAX VERTEX NUM typedef struct char vexs MAX VERTEX NUM 节点数组 AdjMatrix arcs 邻接矩阵 int vexnum arcnum 图的当前节点数和弧数 MGraph typedef struct Pnode 用于普利姆算法 char adjvex 节点 double lowcost 权值 Pnode Closedge MAX VERTEX NUM 记录顶点集 U 到 V U 的代价最小 的边的辅助数组定义 typedef struct Knode 用于克鲁斯卡尔算法中存储一条边及其对应的 2 个节点 char ch1 节点 1 char ch2 节点 2 double value 权值 Knode Dgevalue MAX VERTEX NUM 2 求解算法采用 Prim 算法和 Kruskal 算法 1 普里姆算法 Prim 算法 普里姆算法 Prim 算法是一种构造性算法 生成最小生成树的步骤如下 初始化 U v 以 v 到其他顶点的所有边为候选边 重复一下步骤 n 1 次 使得其他 n 1 个顶点被加入到 U 中 从候选边中挑选权值最小的边加入 TE 设该边在 V U 中的顶点是 1 vk 将顶点 vk 加入到 U 中 考察当前 V U 中的所有顶点 vj 修改候选边 若 vk vj 的权值小于 2 原来和 vj 关联的候选边 则用 vk vj 取代后者作为候选边 开始 标志顶点 1 加入 U 集合 寻找满足边的一个顶点在 U 另一个顶点在 V 的最小边 形成 n 1 条边的生成树 顶点 k 加入 U 修改由顶点 k 到其他 顶点边的权值 结束 得到最小生成树 2 克鲁斯卡尔 Kruskal 算法 克鲁斯卡尔 Kruskal 算法是一种按权值的递增次序选择合适的边来构造 最小生成树的方法 假设 G V E 是一个具有 n 个顶点的带权连通无向图 T U TE 是 G 的最小生成树 则构造最小生成树的步骤如下 置 U 的初值等于 V 即包含有 G 中的全部顶点 TE 的初值为空集 即图 T 中每一个顶点都构成一个分量 将图 G 中的边按权值从小到大的顺序依次选取 若选取的边未使生成树 T 形成回路 则加入 TE 否则舍弃 直到 TE 中包含 n 1 条边为止 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 从 3 使用的函数 int CreateUDG MGraph int LocateVex MGraph G char ch int Minimum MGraph G Closedge closedge void MiniSpanTree PRIM MGraph G char u void Sortdge Dgevalue void Adjacency Matrix MGraph G void Adjacency List MGraph G Dgevalue dgevalue 函数之间的调用关系图 CreateUDG main Adjace ncy Ma trix Adjace ncy Li st MiniSpan Tree KRS L MiniSpan Tree PRI M locateVex locateVex Minimum locateVex Sortdge 五 五 程序代码程序代码 include include include define MAX VERTEX NUM 20 define OK 1 define ERROR 0 define MAX 1000 typedef struct Arcell double adj Arcell AdjMatrix MAX VERTEX NUM MAX VERTEX NUM typedef struct char vexs MAX VERTEX NUM 节点数组 AdjMatrix arcs 邻接矩阵 int vexnum arcnum 图的当前节点数和弧数 MGraph typedef struct Pnode 用于普利姆算法 char adjvex 节点 double lowcost 权值 Pnode Closedge MAX VERTEX NUM 记录顶点集 U 到 V U 的代价最小的边 的辅助数组定义 typedef struct Knode 用于克鲁斯卡尔算法中存储一条边及其对应的 2 个 节点 char ch1 节点 1 char ch2 节点 2 double value 权值 Knode Dgevalue MAX VERTEX NUM int CreateUDG MGraph int LocateVex MGraph G char ch int Minimum MGraph G Closedge closedge void MiniSpanTree PRIM MGraph G char u void Sortdge Dgevalue void Adjacency Matrix MGraph G void Adjacency List MGraph G Dgevalue dgevalue int CreateUDG MGraph cout G vexnum G arcnum cout 请输入各个城市名称 分别用一个字符代替 for i 0 i G vexs i for i 0 i G vexnum i 初始化数组 for j 0 j G vexnum j G arcs i j adj MAX cout 请输入两个城市名称及其连接费用 严禁连接重复输入 endl for k 0 k dgevalue k ch1 dgevalue k ch2 dgevalue k value i LocateVex G dgevalue k ch1 j LocateVex G dgevalue k ch2 G arcs i j adj dgevalue k value G arcs j i adj G arcs i j adj return OK int LocateVex MGraph G char ch 确定节点 ch 在图 G vexs 中的位置 int a for int i 0 i G vexnum i if G vexs i ch a i return a void Adjacency Matrix MGraph G 用邻接矩阵存储数据 int i j for i 0 i G vexnum i for j 0 j G vexnum j if G arcs i j adj MAX cout 0 else cout G arcs i j adj cout endl void Adjacency List MGraph G Dgevalue dgevalue 用邻接表储存数据 int i j for i 0 i G vexnum i cout G vexs i for j 0 j G arcnum j if dgevalue j ch1 G vexs i else if dgevalue j ch1 G vexs i cout b b endl void MiniSpanTree KRSL MGraph G Dgevalue int bj MAX VERTEX NUM 标记数组 for i 0 i G vexnum i 标记数组初始化 bj i i Sortdge dgevalue G 将所有权值按从小到大排序 for i 0 i G arcnum i p1 bj LocateVex G dgevalue i ch1 p2 bj LocateVex G dgevalue i ch2 if p1 p2 cout 城市 dgevalue i ch1 与城市 dgevalue i ch2 连接 endl for j 0 j G vexnum j if bj j p2 bj j p1 void Sortdge Dgevalue double temp char ch1 ch2 for i 0 i G arcnum i for j i j dgevalue j value temp dgevalue i value dgevalue i value dgevalue j value dgevalue j value temp ch1 dgevalue i ch1 dgevalue i ch1 dgevalue j ch1 dgevalue j ch1 ch1 ch2 dgevalue i ch2 dgevalue i ch2 dgevalue j ch2 dgevalue j ch2 ch2 void MiniSpanTree PRIM MGraph G char u 普里姆算法求最小生成树 int i j k Closedge closedge k LocateVex G u for j 0 j G vexnum j 辅助数组初始化 if j k closedge j adjvex u closedge j lowcost G arcs k j adj closedge k lowcost 0 for i 1 i G vexnum i k Minimum G closedge cout 城市 closedge k adjvex 与城市 G vexs k 连接 endl closedge k lowcost 0 for j 0 j G vexnum j if G arcs k j adj closedge j lowcost closedge j adjvex G vexs k closedge j lowcost G arcs k j adj int Minimum MGraph G Closedge closedge 求 closedge 中权值最小的 边 并返回其顶点在 vexs 中的位置 int i j double k 1000 for i 0 i G vexnum i if closedge i lowcost 0 j i return j void main MGraph G Dgevalue dgevalue CreateUDG G dgevalue char u cout 图创建成功 cout 请根据如下菜单选择操作 n cout 1 用邻接矩阵存储 endl cout 2 用邻接表存储 endl cout 3 克鲁斯卡尔算法求最经济的连接方案 endl cout 4 普里姆算法求最经济的连接方案 endl int s char y y while y y cout 请选择菜单 s switch s case 1 cout 用邻接矩阵存储为 endl Adjacency Matrix G break case 2 cout 用邻接表存储为 endl Adjacency List G dgevalue break case 3 cout 克鲁斯卡尔算法最经济的连接方案为 endl MiniSpanTree KRSL G dgevalue break