数据结构课程设计报告题目：最小生成树问题
院（系）：计算机工程学院
学生姓名:
班级：学号:
起迄日期:
指导教师:
2011—2012年度第 2 学期
一、需求分析
1.问题描述：
在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。
2.基本功能
在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。
程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。
3.输入输出
以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。
二、概要设计
1.设计思路：
因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所以我选择采用了邻接表和邻接矩阵两种存储结构。
2.数据结构设计：
图状结构：
ADT Graph{
数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R：R={VR}
VR={
谓词P(v,w)定义了弧
基本操作：
CreateGraph( &G, V, VR )
初始条件：V是图的顶点集，VR是图中弧的集合。
操作结果：按V和VR的定义构造图G。
DestroyGraph( &G )
初始条件：图G存在。
操作结果：销毁图G。
LocateVex( G, u )
初始条件：图G存在，u和G中顶点有相同特征。
操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返
回其它信息。
GetVex( G, v )
初始条件：图G存在，v是G中某个顶点。
操作结果：返回v的值。
PutVex( &G, v, value )
初始条件：图G存在，v是G中某个顶点。
操作结果：对v赋值value。
FirstAdjVex( G, v )
初始条件：图G存在，v是G中某个顶点。
操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，
则返回“空”。
NextAdjVex( G, v, w )
初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。
操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的
最后一个邻接点，则返回“空”。
InsertVex( &G, v )
初始条件：图G存在，v和图中顶点有相同特征。
操作结果：在图G中增添新顶点v。
DeleteVex( &G, v )
初始条件：图G存在，v是G中某个顶点。
操作结果：删除G中顶点v及其相关的弧。
InsertArc( &G, v, w )
初始条件：图G存在，v和w是G中两个顶点。
操作结果：在G中增添弧
DeleteArc( &G, v, w )
初始条件：图G存在，v和w是G中两个顶点。
操作结果：在G中删除弧
DFSTraverse( G, Visit() )
初始条件：图G存在，Visit是顶点的应用函数。
操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用
函数Visit一次且仅一次。一旦visit()失败，则操作失败。
BFSTraverse( G, Visit() )
初始条件：图G存在，Visit是顶点的应用函数。
操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用
函数Visit一次且仅一次。一旦visit()失败，则操作失败。
}ADT Graph
存储结构：
邻接矩阵：
#define INFINITY INT_MAX据类型的定义
<1>图类型
#define M 20
#define MAX 20
#define null 0
#define MAX_VERTEX_NUM 20要模块的算法描述
<1>主函数
int main(void) owcost=0; egin；
把j赋给edges[k].end；
把i，j之间的权值赋给edges[k].weight；
K++；}/*对结构体edge进行初始化*/
}
}
对图G边的权值进行排序sort(edges, G)；
当循环变量i小于当前弧度数时
{将0赋给parent[i]，初始化数组；}
当循环变量i小于当前弧度数时(此时第i条弧为最小的) {
找第i条弧的起点和终点；并分别赋给你n，m；
当n，m不相等时
{把m赋给parent[n]；
输出此时第i条弧的起点、终点、权值；
}
}
}
流程图：
四、调试分析
本次课程设计基本达到了设计需求。但是还有很多不足。比如不能随意切换两种算法，也不能由用户选择使用邻接矩阵还是邻接表，以后更加深入的学习计算机知识或许可以在这两个方面进行改进。
五、测试结果
prim算法正确结果：
prim算法错误结果：
克鲁斯卡尔算法正确结果：
克鲁斯卡尔算法错误结果：
六、体会与自我评价
“数据结构”是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已成为其他理工专业的热门选修课。本学期通过学习这门课程，我学会了分析研究计算机加工的数据结构的特性，以及算法的事件分析和空间分析。这些帮助我在设计程序的过程中，更好为数据选择适当的逻辑结构、存储结
构及其相应的算法。
通常情况下，交通、道路问题的数学模型是一种称为“图”的数据结构。在本课题中，每个顶点代表一个城市，每一条边代表一条通信录井，同时给每条路径赋予权值，代表着这条路径的建设代价。通过最小生成树的实现，可以实现以最节省经费的方式来建立这个通信网。对于n个顶点的联通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。但是根据要求，我们需要以最少的经费来完成整个通信网的建设，于是便有了最小生成树问题。
为了完成本次课程设计，因为课本上只有prim算法的代码，所以克鲁斯卡尔算法还需要自己使用百度进行查找。在查找到算法之后，要将其变为程序源代码，将它们的功能实现出来。这就需要用到计算机高级语言编程了。我们所学的是C语言版的数据结构，C语言的课程是在大一下半学期就完成的，所以总体来说难度并不是很大。再加上题目要求也不多，属于很简单的题目，所以基本上没有碰到大的难题。
通过本次设计，我对C语言有了更深一层的认识，同时也更好的掌握了“图”部分的算法及其实现方法。这让我对数据结构这门课程都有了更深层次的体会。进行课程设计的确会对本课程的学习有很大的帮助。
数据结构课程设计报告题目：最小生成树问题 院（系）：计算机工程学院 学生姓名: 班级：学号: 起迄日期: 指导教师: 2011—2012年度第 2 学期 一、需求分析
1.问题描述： 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 2.基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 3.输入输出 以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。 二、概要设计 1.设计思路： 因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所以我选择采用了邻接表和邻接矩阵两种存储结构。 2.数据结构设计： 图状结构： ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R={VR} VR={
榆林学院12届课程设计 《最小生成树问题》 课程设计说明书 学生姓名：赵佳 学号： 1412210112 院系：信息工程学院 专业：计算机科学与技术 班级：计14本1 指导教师： 答辩时间：年月日 最小生成树问题 一、问题陈述 最小生成树问题 设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方
法。存储结构采用多种。求解算法多种。 二、需求分析 1.在n个城市之间建设网络，只需保证连通即可。 2.求城市之间最经济的架设方法。 3.采用多种存储结构，求解算法也采用多种。 三、概要设计 1、功能模块图 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的代价最小的边的
1. 实验报告如有雷同，雷同各方当次实验成绩均以0分计。 2. 当次小组成员成绩只计学号、姓名登录在下表中的。 3. 在规定时间内未上交实验报告的，不得以其他方式补交，当次成绩按0分计。 4. 实验报告文件以PDF 格式提交。 【实验题目】生成树协议 【实验目的】理解快速生成树协议的配置及原理。使网络在有冗余链路的情况下避免环路的产生，避免广播风暴等。 【实验内容】 (1)完成实验教程实例3-8的实验，回答实验提出的问题及实验思考。（P117） (2)抓取生成树协议数据包，分析桥协议数据单元（BPDU ）。 (3)在实验设备上查看VLAN 生成树，并学会查看其它相关重要信息。 【实验要求】 一些重要信息需给出截图。 注意实验步骤的前后对比！ 【实验记录】(如有实验拓扑请自行画出, 要求自行画出拓扑图) (1) 实例3-8 实验拓扑图如下： 院系 班 级 组长 学号 学生 实验分工 陈 刘 3-8 、 宗良 警示
步骤0： 将PC1和PC2配置好IP地址和掩码后按照拓扑图连接实验设备。 在PC1上启动Wireshark 软件观察包的数量变化如下： 此时已经产生了广播风暴。 两台交换机此时的生成树配置信息如下： 无生成树配置信息。 用PC1pingPC2时包增长情况如下：
可见此时包增长的更快，已经产生广播风暴，但是PC并未发生死锁。步骤1： 配置交换机A： 步骤2： 配置交换机B： 步骤3: 配置两交换机的快速生成树协议：
再按照拓扑图连接实验设备，此时包增长情况如下： 此时两PC间可以相互ping通，且无广播风暴。由此可见生成树协议的作用为避免网络中存在交换环路的时候产生广播风暴，确保在网络中有环路时自动切断环路。
数据结构课程设计 目录 一. 设计目的.................................................................................................. 错误！未定义书签。 二. 设计内容 (1) 三．概要设计 (1) 1、功能模块图 (1) 2、各个模块详细的功能描述 (2) 四．详细设计 (3) 1．主函数和其他函数的伪码算法 (3) 2、主要函数的程序流程图 (7) 3、函数之间的调用关系图 (15) 五．测试数据及运行结果 (15) 1．正常测试数据及运行结果 (16) 2、非正常测试数据及运行结果 (17) 六．调试情况，设计技巧及体会 (18) 七．参考文献 (19) 八．附录：源代码 (19)
一. 设计目的 课程设计是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。能够在设计中逐步提高程序设计能力，培养科学的软件工作方法。而且通过数据结构课程设计能够在下述各方面得到锻炼： 1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。 2、提高程序设计和调试能力。通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。 二. 设计内容 最小生成树问题: 设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 三．概要设计 1、功能模块图
黄冈师范学院 提高型实验报告 实验课题最小生成树的Prim算法 （实验类型：□综合性■设计性□应用性） 实验课程算法程序设计 实验时间 2010年12月24日 学生姓名周媛鑫 专业班级计科 0801 学号 200826140110
一．实验目的和要求 （1）根据算法设计需要, 掌握连通网的灵活表示方法; （2）掌握最小生成树的Prim算法; （3）熟练掌握贪心算法的设计方法; 二．实验条件 （1）硬件环境：实验室电脑一台 （2）软件环境：winTC 三．实验原理分析 （1）最小生成树的定义： 假设一个单位要在n个办公地点之间建立通信网，则连通n个地点只需要n-1条线路。可以用连通的无向网来表示n个地点以及它们之间可能设置的通信线路，其中网的顶点表示城市，边表示两地间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以表示一个通信网。其中一棵使总的耗费最少，即边的权值之和最小的生成树，称为最小生成树。 （2）构造最小生成树可以用多种算法。其中多数算法利用了最小生成树的下面一种简称为MST的性质：假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中u∈U，v∈V-U，则必存在一棵包含边 (u.v)的最小生成树。 （3）普里姆（Prim）算法即是利用MST性质构造最小生成树的算法。算法思想如下： 假设N=(V,{E})和是连通网，TE是N上最小生成树中边的集合。算法从U={u0}( u0∈V)，TE={}开始，重复执行下述操作：在所有u∈U，v∈V-U的边(u, v) ∈E 中找一条代价最小的边(u0, v0)并入集合TE，同时v0并入U，直到U=V为止。此时TE中必有n-1条边，则T=(V,{TE})为N的最小生成树。 四．实验步骤 （1）数据结构的设计： 采用邻接矩阵的存储结构来存储无向带权图更利于实现及操作： 邻接矩阵的抽象数据结构定义： #define INFINITY INT_MAX //最大值 #define MAX_ERTEX_NUM 20 //最大顶点数 typedef enum {DG,DN,UDG,UDN}GraphKind;//{有向图,有向网，无向网，无向图} typedef struct Arc Cell{ VRType adj ; // VRType 是顶点关系的类型。对无权图用1和0表示相邻否；InfoType * info; //该弧相关信息的指针 }ArcCell ，AdjMatrix [ MAX_VERTEX_NUM][MAX_VERTEX_NUM]； Typedef struct { VertexType vexs [ MAX_VERTEX_NUM] ; //顶点向量
0分计。 4. 实验报告文件以PDF 格式提交。 【实验题目】生成树协议 【实验目的】理解快速生成树协议的配置及原理。使网络在有冗余链路的情况下避免环路的产生，避免广播风暴等。 【实验内容】 (1)完成实验教程实例3-8的实验，回答实验提出的问题及实验思考。（P117） (2)抓取生成树协议数据包，分析桥协议数据单元（BPDU ）。 (3)在实验设备上查看VLAN 生成树，并学会查看其它相关重要信息。 【实验要求】 一些重要信息需给出截图。 注意实验步骤的前后对比！ 【实验记录】(如有实验拓扑请自行画出, 要求自行画出拓扑图) (1) 实例3-8 实验拓扑图如下：
步骤0： 将PC1和PC2配置好IP地址和掩码后按照拓扑图连接实验设备。 在PC1上启动Wireshark 软件观察包的数量变化如下： 此时已经产生了广播风暴。 两台交换机此时的生成树配置信息如下： 无生成树配置信息。 用PC1pingPC2时包增长情况如下：
可见此时包增长的更快，已经产生广播风暴，但是PC并未发生死锁。步骤1： 配置交换机A： 步骤2： 配置交换机B： 步骤3: 配置两交换机的快速生成树协议：
再按照拓扑图连接实验设备，此时包增长情况如下： 此时两PC间可以相互ping通，且无广播风暴。由此可见生成树协议的作用为避免网络中存在交换环路的时候产生广播风暴，确保在网络中有环路时自动切断环路。
步骤4：验证测试 SwitchA的生成树信息： SwitchB的生成树信息：
步骤5：设置交换机的优先级 将SwitchA的优先级设置为4096 步骤6: 验证SwitchA的优先级 当两个端口都连在一个共享介质上，交换机会选择一个高优先级的端口进入
算法与数据结构 实验报告 系（院）：计算机科学学院 专业班级：软工11102 姓名：潘香杰 学号： 201104449 班级序号： 18 指导教师：詹泽梅老师 实验时间：2013.6.17 - 2013.6.29 实验地点：4号楼5楼机房
目录 1、课程设计目的．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 2、设计任务．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 3、设计方案．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 4、实现过程．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 5、测试．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 6、使用说明．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 7、难点与收获．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 8、实现代码．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 9、可改进的地方．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．
算法与数据结构课程设计是在学完数据结构课程之后的实践教学环节。本实践教学是培养学生数据抽象能力，进行复杂程序设计的训练过程。要求学生能对所涉及问题选择合适的数据结构、存储结构及算法，并编写出结构清楚且正确易读的程序，提高程序设计基本技能和技巧。 一．设计目的 1．提高数据抽象能力。根据实际问题，能利用数据结构理论课中所学到的知识选择合适的逻辑结构以及存储结构，并设计出有效解决问题的算法。 2．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3．初步了解开发过程中问题分析、整体设计、程序编码、测试等基本方法和技能。二．设计任务 设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下： ①创建无向图的邻接表 ②无向图的深度优先遍历 ③无向创建无向图的邻接矩阵 ④无向图的基本操作及应用 ⑤图的广度优先遍历 1．有向图的基本操作及应用 ①创建有向图的邻接矩阵 ②创建有向图的邻接表 ③拓扑排序 2．无向网的基本操作及应用 ①创建无向网的邻接矩阵 ②创建无向网的邻接表 ③求最小生成树 3．有向网的基本操作及应用 ①创建有向网的邻接矩阵 ②创建有向网的邻接表 ③关键路径 ④单源最短路径 三．设计方案 第一步：根据设计任务，设计DOS菜单，菜单运行成果如图所示：
二层交换：生成树STP基本概念与实验 如果你把两台傻瓜式交换机之间连两根网线，那么这俩交换机就会出现环路从而产生广播风暴。 可能你会觉得好笑，但实际工作中，我却碰到了，一些不懂网络的装修包工头，就会这样做。 ==================================================================== 生成树就是为了让交换网络中防环而出现的。 生成树最原始的版本是802.1d，也就是STP（Spanning Tree Protocol）， 但这个版本的标准是所有VLAN共用一个生成树，所以也叫CST（Common Spanning Tree） 思科在此基础上增强了一下，发布了PVST+（Per Vlan Spanning Tree） 802.1d的下一个版本是802.1w，也就是RSTP（Rapid STP），但还是共用生成树，搞不懂IEEE不长点记性。 于是思科又搞了一下，发布了PVRST+ IEEE又基于思科的MISTP的方案，发布了802.1s（MSTP），这个就屌爆了，之后再说为何这么屌，凡是大一点的交换网络都用MSTP。 ===================================================================== STP的基础 要学习更高级的RSTP/MST，还是需要STP的基础，尽管现在已经很少用到STP。 STP的工作流程
1. 在整个交换网段里选择一台做根桥，这根桥就是整棵树的根部，所有其他交换机就选一条到这个根桥的最短路径，其余的路径阻塞掉。所有交换机中桥优先级最低的成为根桥。 2. 选择所有非根桥交换机的根端口，就是那条最短路径的接口。如果有超过1条等价路径，则选择对端指定端口优先级最低的本地端口（有点绕口，通过实验来说明） 3. 选择各网段的指定端口。这个网段其实就是指一根链接，其中一头一定是指定端口，另外一头可能是根端口，也可能是非指定端口。 根端口——只出现在非根桥交换机上，就是到达根桥最短路径的那个接口。如下图，SW1被设置较低的桥优先级成为了根桥，注意，根桥上是没有根端口的。根端口转发数据帧。 指定端口（和非指定端口）——所有交换机上都可能有，根桥上的所有端口都是指定端口（接终端的那些不算啊），非根桥之间的指定端口通过判断优先级，谁低谁是指定端口，对端是非指定端口或根端口，非指定端口禁止转发数据帧，不过仍会监听BPDU。 如下图，SW1上的接口都是指定端口，SW2/3上离根桥最短路径的端口就是根端口。而SW2<->SW3之间的链路，记住，一条链接上一定有一头是指定端口，另外一头如果不是根端口，那就一定是非指定端口。那哪边是指定端口呢？哪边的桥优先级更低，哪边就是指定端口。而SW3上非指定端口被阻塞了，所以SW2<->SW3之间的链路其实是被阻塞了不能用于转发数据。
实验五最小生成树 一、需求分析 1、本程序の目の是要建设一个最经济の网，，输出相应の最小生成树。在这里都用整型数来代替。 2、测试数据 见下程序。 二、概要设计 主程序： int main() { 初始化； while (条件) { 接受命令; 处理命令; } return 0; } 三、详细设计 #include
{ char adjvex; int lowcost; }Close,close[MAX_VERTEX_NUM]; typedef struct ArcNode { int adjvex; ArcNode *nextarc; int info; }ArcNode; typedef struct VNode { char data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList verties; int vexnum,arcnum; }ALGraph; ALGraph G;//对象G int LocateVek(ALGraph ,char );//返回结点位置 int minimum(close);//返回最小数 void MinSpanTree_PRIM(ALGraph,char);//最小生成树 void Create(ALGraph &);//创建邻接表 int main() { char a;int i=1; Create(G); /*for(int i=1;i<=G.vexnum;i++) { for(s=G.verties[i].firstarc;s!=NULL;s=s->nextarc) cout<
最小生成树算法分析 一、生成树的概念 若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次bfs或dfs后便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs亦可系统地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树。 对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次bfs或dfs后一般不能系统地访问所有顶点，而只能得到以出发点为根的连通分支（或强连通分支）的生成树。要访问其它顶点需要从没有访问过的顶点中找一个顶点作为起始点，再次调用bfs 或dfs，这样得到的是生成森林。 由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。 可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。 二、求图的最小生成树算法 严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V， E’），且边集E’能将图中所有顶点连通又不形成回路，则称子图G’是图G的一棵生成树。 对于加权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。 求图的最小生成树具有很高的实际应用价值，比如下面的这个例题。
例1、城市公交网 [问题描述] 有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。 [输入] n（城市数，1<=n<=100） e（边数） 以下e行，每行3个数i,j,w ij，表示在城市i,j之间修建高速公路的造价。 [输出] n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。 [举例] 下面的图（A）表示一个5个城市的地图，图（B）、（C）是对图（A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树，其权和分别为20和33，前者比后者好一些，但并不是最小生成树，最小生成树的权和为19。 [问题分析] 出发点：具有n个顶点的带权连通图，其对应的生成树有n-1条边。那么选哪n-1条边呢？设图G的度为n，G=（V，E），我们介绍两种基于贪心的算法，Prim算法和Kruskal算法。 1、用Prim算法求最小生成树的思想如下： ①设置一个顶点的集合S和一个边的集合TE，S和TE的初始状态均为空集； ②选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S； ③重复下列操作，直到选取了n-1条边： 选取一条权值最小的边（X，Y），其中X∈S，not (Y∈S)； 将顶点Y加入集合S，边（X，Y）加入集合TE； ④得到最小生成树T =（S，TE）
实验二十一、生成树实验 一、实验目的 1、了解生成树协议的作用。 2、熟悉生成树协议的配置。 二、应用环境 交换机之间具有冗余链路本来是一件很好的事情，但是它有可能引起的问题比它能够解决的问题还要多。如果你真的准备两条以上的路，就必然形成了一个环路，交换机并不知道如何处理环路，只是周而复始地转发帧，形成一个“死循环”，这个死循环会造成整个网络处于阻塞状态，导致网络瘫痪。 采用生成树协议可以避免环路。 生成树协议的根本目的是将一个存在物理环路的交换网络变成一个没有环路的逻辑树形网络。IEEE802.1d 协议通过在交换机上运行一套复杂的算法STA（spanning-tree algorithm），使冗余端口置于“阻断状态”，使得接入网络的计算机在与其他计算机通讯时，只有一条链路生效，而当这个链路出现故障无法使用时，IEEE802.1d 协议会重新计算网络链路，将处于“阻断状态”的端口重新打开，从而既保障了网络正常运转，又保证了冗余能力。 三、实验设备 1、DCS-3926S 交换机2 台 2、PC 机2 台 3、Console 线1-2 根 4、直通网线 4-8 根 四、实验拓扑 五、实验要求 IP 地址设置：
如果生成树成功，则PC1 可以ping 通PC2。 六、实验步骤 第一步：正确连接网线，恢复出厂设置之后，做初始配置 交换机A： switch#config switch(Config)#hostname switchA switchA(Config)#interface vlan 1 switchA(Config-If-Vlan1)#ip address 10.1.157.100 255.255.255.0 switchA(Config-If-Vlan1)#no shutdown switchA(Config-If-Vlan1)#exit switchA(Config)# 交换机B： switch#config switch(Config)#hostname switchB switchB(Config)#interface vlan 1 switchB(Config-If-Vlan1)#ip address 10.1.157.101 255.255.255.0 switchB(Config-If-Vlan1)#no shutdown switchB(Config-If-Vlan1)#exit switchB(Config)# 第二步：“PC1 ping PC2 –t ”观察现象 1、ping不通； 2、所有连接网线的端口的绿灯很频繁地闪烁，表明该端口收发数据量很大，已经 在交换机内部形成广播风暴。 第三步：在两台交换机中都使用启用生成树协议 switchA(Config)#spanning-tree mode stp
算法设计与分析课程设计报告 学院计算机科学与技术 专业计算机科学与技术 年级2011 姓名XXX 学号 2013年5 月19 日
题目：最小生成树问题的算法实现及复杂度分析 摘要：该程序操作简单，具有一定的应用性。数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。而最小生成树算法是算法设计与分析中的重要算法，最小生成树也是最短路径算法。最短路径的问题在现实生活中应用非常广泛，如邮递员送信、公路造价等问题。本设计以Visual Studio 2010作为开发平台，C/C++语言作为编程语言，以邻接矩阵作为存储结构，编程实现了最小生成树算法。构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM 经典算法的算法思想，最后用这种经典算法实现了最小生成树的生成。 引言：假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n（n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。一棵生成树的代价就是树上各边的代价之和。而实现这个运算的经典算法就是普利姆算法。
实验五 实验名称： 得到最小生成树 实验目的： 1.熟悉地掌握计算机科学技术常用的离散数学中的概念、性质和运算；通过实验提高学生编写实验报告、总结实验结果的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。 2.掌握图论中的最小生成树及Prim 和 Kruskal 算法等，进一步能用它们来解决实际问题。 实验内容： 输入一个图的权矩阵，得到该图的生成树，用Kruskal算法的最小生成树，用Prim算法的最小生成树。
Kruskal算法 假设T中的边和顶点均涂成红色，其余边为白色。开始时G中的边均为白色。 1）将所有顶点涂成红色； 2）在白色边中，挑选一条权最小的边，使其与红色边不形成圈，将该白色边涂红； 3）重复2）直到有n-1条红色边，这n-1条红色边便构成最小生成树T的边集合。 Prim算法 假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合,则prim算法通过以下步骤可以得到最小生成树: 1)初始化:U={u 0},TE={f}。此步骤设立一个只有结点u 0的结点集U和一个空的边集TE作为最小生成树的初始形态,在随后的算法执行中,这个形态会不断的发生变化,直到得到最小生成树为止。 2)在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边(u 0,v 0)，将此边加进集合TE中，并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V－U 中,其次边的权要最小。找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的那个顶点加入到U中。这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合,这一点在理解算法时要密切注意。 3)如果U=V,则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当U=V时,步骤2共执行了n－1次(设n为图中顶点的数目),TE中也增加了n－1条边,这n－1条边就是需要求出的最小生成树的边。
STP及其优化实验拓扑图：
实验步骤： 1. 设置SW1，SW2，SW3主机名分别为Core1,Core2, ED-SW 2. 把Core1与Core2间的两条链路绑定成etherchannel2，并设置成Trunk mode Core1: interface range fa0/23 - 24 switchport trunk encapsulation dot1q //支持ISL及dot1Q的交换机必须设置trunk的封装协议。低端的C2950，C2960，C2918只支持dot1Q，无此命令。 switch mode trunk //接口设置为Trunk模式。 channel-group 2 mode on //接口加入Etherchannel2。 Creating a port-channel interface Port-channel 2 //系统提示自动创建port-channel2。 interface Port-channel2 // Port-channel2接口配置必须同物理接口一致。 switchport trunk encapsulation dot1q switchport mode trunk Core2: interface range fa0/23 - 24 switchport trunk encapsulation dot1q switch mode trunk channel-group 2 mode on Creating a port-channel interface Port-channel 2 interface Port-channel2 switchport trunk encapsulation dot1q switchport mode trunk 3.验证etherchannel设置 Core1#sh etherchannel summary //显示etherchannel的详细信息 Flags: D - down P - in port-channel I - stand-alone s - suspended H - Hot-standby (LACP only) R - Layer3 S - Layer2 U - in use f - failed to allocate aggregator u - unsuitable for bundling w - waiting to be aggregated d - default port Number of channel-groups in use: 1 //目前已经建好1个etherchannel。Number of aggregators: 1 Group Port-channel Protocol Ports ------+-------------+-----------+----------------------------------------------- 2 Po2(SU) - fa0/23(P) fa0/24(P) // S - Layer2 U - in use P - in port-channel
编号： 审定成绩： 重庆邮电大学研究生堂下考试答卷 2013-2014学年第1 学期论文题目：最小生成树在旅游路线选择中的应用 学院名称： 学生姓名： 专业： 学号： 指导教师： 重庆邮电大学教务处制
摘要 随着生活节奏的加快，人民生活水平的提高，人们越来越热衷于四处旅游，同时，大家也不愿意将大部分的时间花费在路途上，人们旅游目的在于放松、赏景、游玩，旅游公司就不得不根据游客要求做出相应的旅游路线安排。很多旅游景点之间都相隔一定的距离，那么如何在众多旅游景点路线中选择最近的一条呢？因此，如何做到即保证游览各个景点又确保路途最近地从众多可行路线中选出最优路线成为了解决此问题的关键。 图论最小生成树理论常用于交通线路选择中，本文将其运用于旅游交通优化与线路组织上，即在赋权图中找出一颗最优树，以满足以最短路径最小连接各旅游目的城市和最小的建设成本。我们所学《图论及其算法》教材中介绍了其中的三种算法Prim 算法、Kruskal 算法和破圈法。本文涉及的抽象图形结构较为简单，使用各类算法的差别在此并无明显体现，一般来说，Kruskal 算法应用较为普遍，因此本文采用Kruskal 算法实现最优路径求取。 文中通过一个例子应用，将最小生成树的Kruskal 算法实际化，通过算法步骤分析，以及在VC++6.0中程序的运行，最终求出的最小生成树与实际相符，该算法思想成立，并具有一般性，能够增删节点、修改权值，也可运用到其他问题的解决中。 关键词：旅游路线问题 Kruskal算法最优路线最小生成树
一、引言 旅游交通是为旅游者由客源地到旅游目的地的往返，以及在旅游目的地各处旅游活动而提供的交通设施及服务，其便利程度，是衡量旅游业发达程度的重要标志。与一般交通不同，旅游交通过程本身也是旅游体验过程，对于游客来说，立足于最小的时间与经济成本获得最多的旅游体验，对于旅游组织者来说，则立足于最小的建设成本与最大的社会、经济、生态效益。道路是交通的载体，具有高度通达性、完善的旅游服务功能和景观化、生态化、人性化的道路是区域旅游交通完善的重要标志，基于此，有学者提出“风景道”、“旅游交通干道”等规划建设理念与原则。其中，旅游交通系统的优化很大程度取决于合理的道路布局，而如何使道路通达性与建设成本之间获得平衡，达到性价比最优，成为道路系统优化的重要指标。因此，其实质上可以简化为最短距离连接各旅游目的地最优解问题[1]。 旅游路线组织是旅游地理学研究的重要内容，其研究主要以游客的行为空间模式为导向，旅游路线是旅游产品的组成部分，作为产品就必须满足游客的需求，因此游客的行为模式就成为旅游路线设计的重要依据。 二、背景知识 1、图和树 图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。树是无圈连通无向图，如果树T的节点数为n，那么树的边数为n-1。 2、生成树 连通图G 上的一个子图，该子图连通，无回路且包含图G 的所有节点，称为连通图的极小连通子图。一个连通图可以有多棵不同的生成树。 3、最小生成树 对一个带权连通图，也有多可不同的生成树。由于该图是带权图，各边的权值不一定相等，因此这些生成树的各边权值之和也不一定相同，其中权值最小的生成树被称为该带权连通图的最小生成树[4]。 三、最小生成树的求解方法 构造最小生成树可以有多种算法。我们所学《图论及其算法》教材中介绍了其中的三种算法Prim 算法、Kruskal 算法和破圈法，本文分别用这三种算法来实现最小生成树的构造。
算法分析与设计之Prim 学院：软件学院学号：201421031059 ：吕吕 一、问题描述 1.Prim的定义 Prim算法是贪心算法的一个实例，用于找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。(强调的是树，树是没有回路的)。 2.实验目的 选择一门编程语言，根据Prim算法实现最小生成树，并打印最小生成树权值。 二、算法分析与设计 1.Prim算法的实现过程 基本思想：假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U ＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作： 在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。 此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。 Prim算法的核心:始终保持TE中的边集构成一棵生成树。 2.时间复杂度 Prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边得数目无关，N 为顶点数，而看ruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。 三、数据结构的设计 图采用类存储，定义如下： class Graph { private: int *VerticesList; int **Edge; int numVertices; int numEdges; int maxVertices; public: Graph(); ~Graph(); bool insertVertex(const int vertex); bool insertEdge(int v1,int v2,int cost); int getVertexPos(int vertex); int getValue(int i); int getWeight(int v1,int v2); int NumberOfVertices();
二、实验背景 学校为了开展计算机教学和网络办公，建立了一个计算机教室和一个校办公区，这两处的计算机网络通过两台交换机互相连接组成内部校园网，为了提高网络的可靠性，作为网络管理员，你要用2条链路将交换机互连，现要求在交换机上做适当的配置，使网络避免环路。 三、技术原理 生成树协议(spanning-tree)，作用是在交换网络中提供冗余备份链路，并且解决交换网络中的环路问题； 生成树协议是利用SPA算法，在存在交换环路的网络中生成一个没有环路的树形网络。运用该算法将交换网络的冗余备份链路从逻辑上断开，当主链路出现故障时，能够自动的切换到备份链路，保证数据的正常转发； 生成树协议版本：STP、RSTP(快速生成树)、MSTP(多生成树协议)； 生成树协议的特点是收敛时间长，从主要链路出现故障到切换至备份链路需要50秒的时间； 快速生成树协议在生成树协议的基础上增加了两种端口角色：替换端口和备份端口，分别做为根端口和指定端口的冗余端口。当根端口或指定端口出现故障时，冗余端口不需要经过50秒的收敛时间，可以直接切换到替换端口或备份端口，从而实现RSTP协议小于1秒的快速收敛。 四、实验步骤
实验拓扑 默认情况下STP协议启用的，通过两台交换机之间传送BPDU协议数据单元，选出根交换机、根端口等，以便确定端口的转发状态。上图中标记为橙色的端口处于block堵塞状态。 设置RSTP 查看交换机 show spanning-tree 状态，了解根交换机和根端口情况； 通过更改交换机生成树的优先级spanning-tree vlan * priority 4096 可以变化根交换机的角色； S1: Switch>en Switch#conf t Enter configuration commands, one per line. End with CNTL/Z. Switch(config)#hostname S1 S1(config)#end S1# %SYS-5-CONFIG_I: Configured from console by console
实验四、生成树协议 STP的应用实验 【相关知识】 1．生成树协议 STP简介 在局域网中，为了提高网络连接可靠性，经常提供冗余链路。所谓冗余链路就像公路、铁路一 样，条条道路通北京，这条不通走那条。例如在大型企业网中，多半在核心层配置备份交换机（网 桥），则与汇聚层交换机形成环路，这样做使得企业网具备了冗余链路的安全优势。但原先的交换机 并不知道如何处理环路，而是将转发的数据帧在环路里循环转发，使得网络中出现广播风暴，最终 导致网络瘫痪。 为了解决冗余链路引起的问题， IEEE802 通过了 IEEE 802.1d协议， 即生成树协议 （Spanning Tree Protocol，STP）。IEEE 802.1d协议通过在交换机上运行一套复杂的算法，使冗余端口置于“阻塞状 ，从而使网络中的计算机通信时只有一条链路生效，而当这个链路出现故障时，STP 将会重新计 态” 算出网络的最优链路，将“阻塞状态”的端口重新打开，从而确保网络连接的稳定可靠。 生成树协议和其它协议一样，是随着网络的不断发展而不断更新换代的。在生成树协议发展的 过程中，老的缺陷不断被克服，新的特性不断被开发出来。按照功能特点的改进情况，习惯上生成 树协议的发展过程被分为三代： 第一代生成树协议：STP/RSTP 第二代生成树协议：PVST/PVST+ 第三代生成树协议：MISTP/MSTP 2．IEEE 801.1D生成树协议简介 生成树协议（Spanning Tree Protocol，STP）最初是由美国数字设备公司（DEC）开发的，后经 IEEE 修改并最终制定了 IEEE 802.1d标准。 STP 协议的主要思想是当网络中存在备份链路时，只允许主链路激活，如果主链路失效，备份 链路才会被打开。大家知道，自然界中生长的树是不会出现环路的，如果网络也能够像树一样生长 就不会出现环路。STP 协议的本质就是利用图论中的生成树算法，对网络的物理结构不加改变，而 在逻辑上切断环路，封闭某个网桥，提取连通图，形成一个生成树，以解决环路所造成的严重后果。 为了理解生成树协议，必先了解以下概念： （1）桥协议数据单元（Bridge Protocol Data Unit，BPDU）：交换机通过交换 BPDU来获得建立 最佳树型拓扑结构所需的信息。生成树协议运行时， 交换机使用共同的组播地址 “01-80-C2-00-00-00”来发送 BPDU； （2）每个交换机有唯一的桥标识符（Brideg ID），由桥优先级和 MAC 地址组成； （3）每个交换机的端口有唯一的端口标识符（Port ID），由端口优先级和端口号组成； （4）对生成树的配置时，对每个交换机配置一个相对的优先级，对每个交换机的每个端口也配 置一个相对的优先级，该值越小优先级越高； （5）具有最高优先级的交换机被称为根桥（Root Bridge），如果所有设备都具有相同的优先级， 则具有最低 MAC 地址的设备将成为根桥； （6）网络中每个交换机端口都有一个根路径开销（Root Path Cost），根路径开销是某交换机到 根桥所经过的路径开销（与链路带宽有关）的总和； （7）根端口是各个交换机通往根桥的根路径开销最低的端口，若有多个端口具有相同的根路径 开销，则端口标识符小的端口为根端口； （8）在每个 LAN 中都有一个交换机被称为指定交换机（Designated Bridge），它是该 LAN 中与 根桥连接而且根路径开销最低的交换机； （9）指定交换机和 LAN 连接的端口被称为指定端口（Designated Port）。如果指定桥中有两个 以上的端口连在这个 LAN 上，则具有最高优先级的端口被选为指定端口。根桥上的端口都可以成为