离散数学--最小生成树实验报告
一、实验目的：掌握图的存储表示和以及图的最小生成树算法。
二、实验内容：
1.实现图的存储，并且读入图的内容。
2.利用克鲁斯卡尔算法求网络的最小生成树。
3.实现构造生成树过程中的连通分量抽象数据类型。
4.以文本形式输出对应图的最小生成树各条边及权值。
三、实验要求：
1．在上机前写出全部源程序；
2．能在机器上正确运行程序；
3．用户界面友好。
需求分析：
1、利用克鲁斯卡尔算法求网的最小生成树；
2、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列；
3、输入为存在边的顶点对，以及它们之间的权值；输出为所得到的邻接矩
阵以及按权排序后的边和最后得到的最小生成树；
克鲁斯卡尔算法：假设WN=(V,{E}) 是一个含有n 个顶点的连通网，按照构造最小生成树的过程为：先构造一个只含n 个顶点，而边集为空的子图，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至只有一棵树，也即子图中含有n-1条边为止。
测试数据：
自行指定图进行运算
四、详细设计
源程序
#include
#include
#define M 20
#define MAX 20
typedef struct
{
int begin;
int end;
int weight;
}edge;
typedef struct
{
int adj;
int weight;
}AdjMatrix[MAX][MAX];
typedef struct
{
AdjMatrix arc;
int vexnum, arcnum;
}MGraph;
void CreatGraph(MGraph *);
void sort(edge* ,MGraph *);
void MiniSpanTree(MGraph *);
int Find(int *, int );
void Swapn(edge *, int, int);
void CreatGraph(MGraph *G)
{
int i, j,n, m;
printf("请输入边数和顶点数:");
scanf("%d %d",&G->arcnum,&G->vexnum);
for (i = 1; i <= G->vexnum; i++)
{
for ( j = 1; j <= G->vexnum; j++)
{
G->arc[i][j].adj = G->arc[j][i].adj = 0;
}
}
for ( i = 1; i <= G->arcnum; i++)
{
printf("\n请输入有边的2个顶点");
scanf("%d %d",&n,&m);
while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum) {
printf("输入的数字不符合要求请重新输入:"); scanf("%d%d",&n,&m);
}
G->arc[n][m].adj = G->arc[m][n].adj = 1;
getchar();
printf("\n请输入%d与%d之间的权值:", n, m);
scanf("%d",&G->arc[n][m].weight);
}
printf("邻接矩阵为:\n");
for ( i = 1; i <= G->vexnum; i++)
{
for ( j = 1; j <= G->vexnum; j++)
printf("%d ",G->arc[i][j].adj);
}
printf("\n");
}
}
void sort(edge edges[],MGraph *G)
{
int i, j;
for ( i = 1; i < G->arcnum; i++)
{
for ( j = i + 1; j <= G->arcnum; j++)
{
if (edges[i].weight > edges[j].weight)
{
Swapn(edges, i, j);
}
}
}
printf("权排序之后的为:\n");
for (i = 1; i < G->arcnum; i++)
{
printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}
void Swapn(edge *edges,int i, int j)
{
int temp;
temp = edges[i].begin;
edges[i].begin = edges[j].begin;
edges[j].begin = temp;
temp = edges[i].end;
edges[i].end = edges[j].end;
edges[j].end = temp;
temp = edges[i].weight;
edges[i].weight = edges[j].weight;
edges[j].weight = temp;
}
void MiniSpanTree(MGraph *G)
{
int i, j, n, m;
int k = 1;
int parent[M];
edge edges[M];
for ( i = 1; i < G->vexnum; i++)
{
for (j = i + 1; j <= G->vexnum; j++) {
if (G->arc[i][j].adj == 1)
{
edges[k].begin = i;
edges[k].end = j;
edges[k].weight = G->arc[i][j].weight;
k++;
}
}
}
sort(edges, G);
for (i = 1; i <= G->arcnum; i++)
{
parent[i] = 0;
}
printf("最小生成树为:\n");
for (i = 1; i <= G->arcnum; i++)
{
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
if (n != m)
{
parent[n] = m;
printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}
}
int Find(int *parent, int f)
{
while ( parent[f] > 0)
{
f = parent[f];
}
return f;
}
int main(void)
{
MGraph *G;
G = (MGraph*)malloc(sizeof(MGraph));
if (G == NULL)
{
printf("memory allcation failed,goodbye"); exit(1);
}
CreatGraph(G);
MiniSpanTree(G);
system("pause");
return 0;
}
运行结果:
五、实验总结（结果分析和体会）
在编程时，因为考虑的情况比较多，所以容易造成错误和遗漏，为了避免这些问题的出现，可以先用笔把所有的程序在纸上，然后再根据列表编写程序，这样不仅简单易懂，还避免了一些不必要的错误。
编写完程序后进行调试，发现有很多错误，其中也不乏一些基本的小错误，所以程序写完后进行静态检查是必不可少的，其次是逻辑上的错误，对于这些错误，只能再认真检查整个程序，这就要求我们在编程时考虑要周到，或者可以请其他同学帮忙检查。
通过这次对算术表达式求值的设计，让我自己对克鲁斯卡尔算法的运用更深刻，能够基本上很好的运用克鲁斯卡尔算法来解决一些问题。不过从中也发现了很多问题，那就是虽然课本知识的掌握还不错，但是上机编程的能力还有所匮乏，应该加强这方面的锻炼，通过上机的实践来提升对基础知识的理解。还有就是应该多和同学交流，比如一个相同的问题，我有我的编程思路，他有他的，通过相互的交流、讨教，可以获得更广的知识信息，开拓思维，自己不懂的通过咨
询就可以掌握。
最小生成树问题课程设计报告
数据结构课程设计 目录 一. 设计目的.................................................................................................. 错误！未定义书签。 二. 设计内容 (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、功能模块图
最小生成树实验报告
数据结构课程设计报告题目：最小生成树问题 院（系）：计算机工程学院 学生姓名: 班级：学号: 起迄日期: 指导教师: 2011—2012年度第 2 学期 一、需求分析
1.问题描述： 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 2.基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 3.输入输出 以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。 二、概要设计 1.设计思路： 因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所以我选择采用了邻接表和邻接矩阵两种存储结构。 2.数据结构设计： 图状结构： ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R={VR} VR={
离散数学实验报告
《离散数学》实验报告专业网络工程 班级 姓名 学号 授课教师 二 O 一六年十二月
目录 实验一联结词的运算 实验二根据矩阵的乘法求复合关系 实验三利用warshall算法求关系的传递闭包实验四图的可达矩阵实现
实验一联结词的运算 一.实验目的 通过上机实验操作,将命题连接词运算融入到C语言的程序编写中,一方面加强对命题连接词运算的理解,另一方面通过编程实现命题连接词运算,帮助学生复习与锻炼C语言知识,将理论知识与实际操作结合,让学生更加容易理解与记忆命题连接词运算。 二.实验原理 (1) 非运算, 符号:? ,当P=T时 ,?P为F, 当P=F时 ,?P为T 。 (2) 合取, 符号: ∧ , 当且仅当P与Q的真值同为真,命题P∧Q的真值才为真;否则,P∧Q的真值为假。 (3) 析取, 符号: ∨ , 当且仅当P与Q的真值同为假,命题P∨Q的真值才为假;否则,P∨Q的真值为真。 (4) 异或, 符号: ▽ , 当且仅当P与Q的真值不同时,命题P▽Q的真值才为真;否则,P▽Q的真值为真。 (5) 蕴涵, 符号: →, 当且仅当P为T,Q为F时,命题P→Q的真值才为假;否则,P→Q 的真值为真。 (6) 等价, 符号: ? , 当且仅当P,Q的真值不同时,命题P?Q的真值才为假;否 则,P→Q的真值为真。 三.实验内容 编写一个程序实现非运算、合取运算、析取运算、异或运算、蕴涵运算、等价运算。四．算法程序 #include
数据结构课程设计最小生成树问题
数据结构与算法 课程设计报告 课程设计题目：最小生成树问题 专业班级：信息与计算科学1001班 姓名：谢炜学号：100701114 设计室号：理学院机房 设计时间： 2011-12-26 批阅时间： 指导教师：杜洪波成绩： 一、摘要： 随着社会经济的发展，人们的生活已经越来越离不开网络，网络成为人们社 会生活的重要组成部分。我们希望拥有一个宽松的上网环境，以便更好的进行信 息的交流，在此我们有必要提升我们的网络传播速度。从某种程度上来说网络传
播速度代表着一个国家网络化程度的高低。 为了解决网络传输速度的问题我们希望在各个城市之间多架设一些通信网络线路，以缓解网络不够流畅不够便捷的问题。而在城市之间架设网络线路受到资金因素等的限制，我们希望找到一条捷径这样我们即达到了连接了各个城市网络的目的又节省了建设成本。 通过以上的分析我们得出解决此问题的关键在于找到一个短的路径完成网络的假设。在此我们想将各个城市抽象成为一个个节点，连接各个城市之间的网络作为连接各个节点的边。于是我们就将城市的空间分布抽象成为一个网络图，再将各条边的距离抽象成为各节点之间的权值。在原来的基础上建立一个带有权值的网络图。于是原有的问题就转化为找图的最小生成树问题。 我们利用普利姆算法和卡鲁斯卡尔算法找到我们所需要的最小的生成树。 二、问题分析 在n个城市间建立通信网络，需架设n-1条路线。求解如何以最低的经济代价建设此通信网，这是一个最小生成树问题。我们可以利用普利姆算法或者克鲁斯卡尔算法求出网的最小生成树，输入各城市的数目以及各个城市之间的距离。将城市之间的距离当做网中各点之间的权值。 三、实现本程序需要解决的问题 （1）如何选择存储结构去建立一个带权的网络； （2）如何在所选存储结构下输出这个带权网络； （3）如何实现普利姆算法的功能； （4）如何从每个顶点开始找到所有的最小生成树的顶点； （5）如何输出最小生成树的边及其权值 此问题的关键就是利用普利姆算法，找到一个最小上的生成树，在一个就是输出我们所需要的信息，在此我们将各个城市看做是网中的各个顶点城市之间的距离看做是个顶点之间的权值。现在我们问题做如下的分析： 这个问题主要在于普利姆算法的实现。我们将各个城市的空间分布抽象成一个带有权值的网络，这个权值就是任意两个城市之间，各个城市就看做是网络的各个顶点。 我们建立的输入的数据格式为：首先提示输入带权的顶点数目，我定义为整形的数据型，然后输入每条边的信息，即边的两个顶点之间的权值，以十进制整数类型数据，这样我们就建立了一个带权的网络。 问题的输出我是将我们所得到的最小生成树的路线输出出来。 题目的要求就是我们在n个城市之间架设网络得到的最为经济的架设方法，我们进行以上的工作就是在找我们所需要的最小生成树，已解决我们的问题。 四、算法思想 普利姆算法求最小生成树的主要思想 假设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，{E}）为N的最小生成树。
最小生成树的Prim算法提高型实验报告
黄冈师范学院 提高型实验报告 实验课题最小生成树的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] ; //顶点向量
离散数学实验报告
离散数学实验报告（实验ABC） 专业班级 学生姓名 学生学号 指导老师 完成时间
目录 第一章实验概述..................................... 错误!未定义书签。 实验目的....................................... 错误!未定义书签。 实验内容....................................... 错误!未定义书签。 实验环境....................................... 错误!未定义书签。第二章实验原理和实现过程........................... 错误!未定义书签。 实验原理....................................... 错误!未定义书签。 建立图的邻接矩阵，判断图是否连通 ............ 错误!未定义书签。 计算任意两个结点间的距离 ................... 错误!未定义书签。 对不连通的图输出其各个连通支 ................ 错误!未定义书签。 实验过程（算法描述）........................... 错误!未定义书签。 程序整体思路 ............................... 错误!未定义书签。 具体算法流程 ................................ 错误!未定义书签。第三章实验数据及结果分析........................... 错误!未定义书签。 建立图的邻接矩阵并判断图是否连通的功能测试及结果分析错误!未定义书签。 输入无向图的边 .............................. 错误!未定义书签。 建立图的连接矩阵 ............................ 错误!未定义书签。 其他功能的功能测试和结果分析................... 错误!未定义书签。 计算节点间的距离 ............................ 错误!未定义书签。 判断图的连通性 .............................. 错误!未定义书签。 输出图的连通支 .............................. 错误!未定义书签。 退出系统 .................................... 错误!未定义书签。第四章实验收获和心得体会........................... 错误!未定义书签。
最小生成树-实验报告
实验五最小生成树 一、需求分析 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<
数据结构课程设计报告java最小生成树
上海电力学院 数据结构（JAVA）课程设计 题目:____最小生成树_______ 学生姓名：_****___________ 学号：_____*******_______ 院系：计算机科学与技术学院 专业年级： ______*****___级 20**年 *月**日
目录 1.设计题目 (1) 2.需求分析 (1) 1）运行环境 (1) 2）输入的形式和输入值的范围 (1) 3）输出的形式描述 (1) 4）功能描述 (1) 5）测试数据 (1) 3.概要设计 (1) 1）抽象数据类型定义描述 (1) .2）功能模块设计 (1) 3）模块层次调用关系图 (2) 4.详细设计。实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。 (2) 5.调试分析。包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会。 (6) 6.用户使用说明。详细列出每一步的操作说明。 (7) 7. 测试结果 (7) 8.附录：程序设计源代码 (9)
一、设计题目 1).问题描述 若要在 n 个城市之间建设通信网络，只需要架设n-1 条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。 2). 基本要求 以邻接多重表存储无向带权图，利用克鲁斯卡尔算法或普瑞姆算法求网的最小生成树。 二、需求分析 1）运行环境 软件在JDK运行，硬件支持windows系统 2）输入的形式和输入值的范围 自动生成顶点数据在10~20之间；各个顶点之间权值在25~50之间；通过程序改动亦可生成已知顶点权值之间的最小生成树，需将随机生成代码改为edge edge[]={new edge(0,1,16),new（0,2,18）......}； 将已知顶点、权值通过其函数输入再生成其所对应最小生成树。 3）输出的形式描述 输出随机生成顶点个数以及各个顶点之间权值；然后输出本次生成顶点之间构成的最小生成树。
Prim最小生成树算法实验报告材料
算法分析与设计之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();
最小生成树数据结构课程设计报告
河北科技大学 课程设计报告 学生姓名：白云学号：Z110702301 专业班级：计算机113班 课程名称：数据结构课程设计 学年学期： 2 01 3—2 014学年第2学期指导教师：郑广 2014年6月
课程设计成绩评定表
目录 一、需求分析说明 (1) 1.1最小生成树总体功能要求 (1) 1.2基本功能 (1) 1.3 模块分析 (1) 二、概要设计说明 (1) 2.1设计思路 (1) 2.2模块调用图 (2) 2.3数据结构设计 (2) 2.3.1.抽象数据类型 (2) 2.3.2方法描述 (2) 三、详细设计说明 (3) 3.1主函数模块 (3) 3.2邻接表输出子模块 (3) 3.3邻接矩阵输出子模块 (3) 3.4创建邻接矩阵子模块 (3) 3.5创建邻接表子模块 (3) 3.6 Prim子模块 (3) 3.7 Kruscal子模块 (4) 四、调试分析 (4) 4.1实际完成情况说明 (4) 4.2 出现的问题及解决方案 (4) 4.3程序中可以改进的地方 (4) 六、课程设计总结 (7) 七、测试数据 (7) 八、参考书目 (7)
一、需求分析说明 1.1最小生成树总体功能要求 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 1.2基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 1.3 模块分析 主模块：用于生成界面和调用各个子模块。 Kruscal模块：以kruscal算法实现最小生成树。 Prim模块：以prim算法实现最小生成树。 邻接表模块：用邻接表方式存储图。 邻接表输出模块：输出邻接表。 邻接矩阵模块：用邻接矩阵方式存储图。 邻接矩阵模块：输出邻接矩阵。 二、概要设计说明 2.1设计思路 问题的解决分别采用普利姆算法以及克鲁斯卡尔算法。 1) 普利姆算法就是先选择根，把它放入一个集合U中，剩余的顶点放在集合V中。然后选择该顶点与V中顶点之间权值最小的一条边，以此类推，如果达到最后一个则返回上一个顶点。 2) 克鲁斯卡尔算法就是写出所有的顶点，选择权最小的边，然后写出第二小的，以此类推，最终要有一个判断是否生成环，不生成则得到克鲁斯卡尔的最小生成树。
实验报告
算法与数据结构 实验报告 系（院）：计算机科学学院 专业班级：软工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菜单，菜单运行成果如图所示：
离散数学实验报告--四个实验!!!
《离散数学》 课程设计 学院计算机学院 学生姓名 学号 指导教师 评阅意见 提交日期 2011 年 11 月 25 日
引言 《离散数学》是现代数学的一个重要分支，也是计算机科学与技术，电子信息技术，生物技术等的核心基础课程。它是研究离散量（如整数、有理数、有限字母表等）的数学结构、性质及关系的学问。它一方面充分地描述了计算机科学离散性的特点，为学生进一步学习算法与数据结构、程序设计语言、操作系统、编译原理、电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、网络、计算机图形学等专业课打好数学基础；另一方面，通过学习离散数学课程，学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后爱念族皮及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。特别是对于那些从事计算机科学与理论研究的高层次计算机人员来说，离散数学更是必不可少的基础理论工具。 实验一、编程判断一个二元关系的性质（是否具有自反性、反自反性、对称性、反对称性和传递性） 一、前言引语：二元关系是离散数学中重要的内容。因为事物之间总是可以 根据需要确定相应的关系。从数学的角度来看，这类联系就是某个集合中元素之间存在的关系。 二、数学原理：自反、对称、传递关系 设A和B都是已知的集合，R是A到B的一个确定的二元关系，那么集合R 就是A×B的一个合于R={(x,y)∈A×B|xRy}的子集合 设R是集合A上的二元关系： 自反关系：对任意的x∈A,都满足
07_生成树实验
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的优先级 当两个端口都连在一个共享介质上，交换机会选择一个高优先级的端口进入
离散数学实验报告()
《离散数学》实验报告 专业网络工程 班级 姓名 学号 授课教师 二 O 一六年十二月
目录 实验一联结词的运算 实验二根据矩阵的乘法求复合关系 实验三利用warshall算法求关系的传递闭包实验四图的可达矩阵实现
实验一联结词的运算 一．实验目的 通过上机实验操作，将命题连接词运算融入到C语言的程序编写中，一方面加强对命题连接词运算的理解，另一方面通过编程实现命题连接词运算，帮助学生复习和锻炼C语言知识，将理论知识与实际操作结合，让学生更加容易理解和记忆命题连接词运算。二．实验原理 (1) 非运算, 符号: ,当P=T时，P为F, 当P=F时，P为T 。 (2) 合取, 符号: ∧ , 当且仅当P和Q的真值同为真，命题P∧Q的真值才为真；否则，P∧Q的真值为假。 (3) 析取, 符号: ∨ , 当且仅当P和Q的真值同为假，命题P∨Q的真值才为假；否则，P∨Q的真值为真。 (4) 异或, 符号: ▽ , 当且仅当P和Q的真值不同时，命题P▽Q的真值才为真；否则，P▽Q的真值为真。 (5) 蕴涵, 符号: →, 当且仅当P为T,Q为F时，命题P→Q的真值才为假；否则，P→Q 的真值为真。 (6) 等价, 符号: ?, 当且仅当P,Q的真值不同时，命题P?Q的真值才为假；否则，P→Q的真值为真。 三．实验内容 编写一个程序实现非运算、合取运算、析取运算、异或运算、蕴涵运算、等价运算。四．算法程序 #include
最小生成树问题中北大学数据结构课程设计资料
中北大学 数据结构与算法课程设计 说明书 学院、系：软件学院 专业：软件工程 班级： 学生姓名：学号： 设计题目：最小生成树问题 起迄日期: 2015年1月12日- 2015年1月29日指导教师:王秀娟 2015 年1月 29 日
1需求分析 1.1已知一个无向连通网表示n个城市以及城市间可能设置的通信网络线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。我们要选择一棵生成树，使总的耗费最小。 1.2该无向连通图的建立需要使用两种存储结构，即邻接表和邻接矩阵。 1.3实现最小生成树需要使用两种算法。即普里姆算法和克鲁斯卡尔。 1.4程序通过人机交互实现数据的输入和输出。 2选题要求 设计内容： 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用（邻接表和邻接矩阵）两种，采用课本上的两种求解算法。 设计要求： (1) 符合课题要求，实现相应功能； (2) 要求界面友好美观，操作方便易行； (3) 注意程序的实用性、安全性。 3程序设计方法及主要函数介绍 ADT Graph{ 数据对象V;V是具有相同特性的数据元素的集合，成为顶点集。 数据关系R： R = {VR} VR = {（v,w）|v,w为V集合中的元素，（v,w）表示v和w之间存在的路径} 基本操作P; CreateMGraph(MGraph *G) 初始条件：V是图的顶点集，VR是图的边的集合。 操作结果：按V和VR的定义构造图G，用邻接矩阵存储。 CreateALGraph(ALGraph *G)
离散数学 最小生成树
实验五 实验名称： 得到最小生成树 实验目的： 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条边就是需要求出的最小生成树的边。
n个城市最小生成树实验报告材料
数据结构 课程设计报告 起评分理论成绩实践成绩总成绩 院系： 专业： 班级： 学号： ： 教师： 时间：
目录 一、设计要求 (3) 1、问题描述 (3) 2、功能 (3) 3、数据 (3) 二、概述与分析 (3) 1、图 (3) 2、邻接矩阵 (3) 3、生成树 (4) 4、最小生成树 (5) 5、最小生成树的操作 (5) 三、程序设计及分析 (6) 四、流程图 (7) 1、模块结构流程图 (7) 2、Prim算法流程设计 (8) 五、测试分析 (8) 六、总结 (10) 七、源程序代码 (10)
一、设计要求： 1、问题描述 构造可以使n个城市连接的最小生成树。 2、功能 给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。本人采用的是Prim算法。 3、数据 城市间的距离网采用邻接矩阵表示（要求至少6个城市，10条边），邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。 表示城市间距离网的邻接矩阵（要求至少6个城市，10条边） 二、概述与分析 1、图 图的定义：图G是有两个集合V和E组成，记做G=（V,E），其中V是定点的有限集合，记做V(G)，E是连接V的两个不同的顶点的边的有限集合，记做E(G)。 2、邻接矩阵 邻接矩阵是图的一种存储方法，它是表示顶点之间相邻关系的矩阵。设 G=(V,E)是具有n(n>0)个顶点的图，顶点的顺序依次为（v 0,v 1,… ,v n-1 ）,则G的 邻接矩阵A是n阶方阵，其定义如下。 1)如果G是无向图，则 1 (v i,v j ) ∈E(G) A[i][j]= 0 其他 2)如果G是有向图，则 1
最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析)
算法设计与分析课程设计报告 学院计算机科学与技术 专业计算机科学与技术 年级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个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。一棵生成树的代价就是树上各边的代价之和。而实现这个运算的经典算法就是普利姆算法。
大数据结构课程设计-最小生成树
《数据结构》期末课程设计 题目第8题：最小生成树问题学院计算机学院 专业 班别 学号 姓名陈聪 2015年7月6日
一、需求分析 1、问题描述 若要在n个城市之间建设通讯网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通讯网，是一个网的最小生成树问题。 2、基本要求 （1）利用克鲁斯卡尔算法求网的最小生成树。 （2）实现并查集。以此表示构造生成树过程中的连通分量。 （3）以文本形式输出生成树中各条边以及他们的权值。 3、实现提示 通讯线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数，可利用C语言提供的随机数函数产生。 图的存储结构的选取应和所作操作向适应。为了便于选择权值最小的边，此题的存储结构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边(带权)的数组即边集数组表示图。 二、详细设计 根据课设题目要求，拟将整体程序分为三大模块，分别是：图的存储结构，并查集的实现，克鲁斯卡尔算法的实现。 1、边集数组的类型定义： typedef struct { int x, y; int w; }edge; x表示起点，y表示终点，w为权值。 2、并查集功能的实现由以下函数实现： Make_Set(int x)初始化集合； Find_Set(int x) 查找x元素所在的集合,回溯时压缩路径； Union(int x, int y, int w)合并x,y所在的集合。
3、克鲁斯卡尔算法的实现 该算法的实现位于主函数中： qsort(e, n, sizeof(edge), cmp); //将边排序 printf("最小生成树的各条边及权值为：\n"); for (i = 0; i < n; i++) { x = Find_Set(e[i].x); y = Find_Set(e[i].y); if (x != y ) { printf("%c - %c : %d\n", e[i].x + 'A', e[i].y + 'A', e[i].w); Union(x, y, e[i].w); } } 4、设计中还包含以下函数： （1）/* 比较函数，按权值(相同则按x坐标)非降序排序*/ int cmp(const void *a, const void *b) { if ((*(edge *)a).w == (*(edge *)b).w) { return (*(edge *)a).x - (*(edge *)b).x; } return (*(edge *)a).w - (*(edge *)b).w; } （2）快排函数qsort,包含在stdlib.h头文件里 qsort(e, n, sizeof(edge), cmp); （3）C语言提供的随机数函数srand( unsigned int seed ); 使用随机数函数如下： srand( (unsigned)time( NULL ) ); for( i = 0; i < n;i++ )