搜档网
当前位置:搜档网 › Kruskal算法说明及图解

Kruskal算法说明及图解

Kruskal算法说明及图解
Kruskal算法说明及图解

1.无向网图及边集数组存储示意图

vertex[6]=

2.Kruskal 方法构造最小生成树的过程

(a)一个图 (b)最小生成树过程1

V0 V1 V2 V3 V4 V5

下标 0 1 2 3 4 5 6 7 8 from 1 2 0 2 3 4 0 3 0 to

4

3 5 5 5 5 1

4 2 weight 12

17

19

25

25

26

34

38

46

V1

V0

V4 V5

V2 V3

V1

V0 V5 V2 V3 V4

(c)最小生成树过程2 (d)最小生成树过程3

(e)最小生成树过程4

(c)最小生成树过程5 3.伪代码

1)初始化辅助数组parent[vertexNum];num=0; 2) 依次考查每一条边for(i=0; i

parent[vex2]=vex1; num++;

if(num==vertexNum-1) 算法结束 4.构造过程中参数变化

顶点集 数组 parent V0 V1 V2 V3 V4 V5

被考查边 输出

说明

初始化

parent -1 -1 -1 -1 -1 -1

6棵生成树,均只有根结点 parent -1 -1 -1 -1 1 -1 (v1,v4)12 (v1,v4)12 vex1=1,vex2=4;parent[4]=1; parent -1 -1 -1 2 1 -1 (v2,v3)17 (v2,v3)17 vex1=2,vex2=3;parent[3]=2; parent -1 -1 -1 2 1 0 (v0,v5)19 (v0,v5)19 vex1=0,vex2=5;parent[5]=0; parent 2 -1 -1 2 1 0 (v2,v5)25 (v2,v5)25 vex1=2,vex2=0;parent[0]=2; parent 2 -1 -1 2 1 0 (v3,v5)25 vex1=2,vex2=2;所在根结点相同 parent 2 -1 1 2 1 0 (v4,v6)26 (v4,v6)26 vex1=1,vex2=2;parent[2]=1; parent 2

-1

1

2

1

生成树根结点是v1

5.主要代码

/**********构造函数************/

template

EdgeGraph::EdgeGraph(DataType a[], int n, int e)

{

vertexNum=n; edgeNum=e;

int i,j,weight;

for (int k=0; k

vertex[k]=a[k];

for (k=0; k

{

cout<<"输入边依附的两个顶点的编号:";

cin>>i>>j;

edge[k].from=i;

edge[k].to=j;

cout<<"请输入权重:";

cin>>weight;

edge[k].weight=weight;

}

}

/**********Kruskal算法构造最小生成树************/

template

void EdgeGraph::Kruskal()

{ int num;

int parent[MaxVertex], vex1, vex2;

for (int i=0; i

parent[i]=-1;

for (i=0,num=0; i

{

vex1=FindRoot(parent, edge[i].from);

vex2=FindRoot(parent, edge[i].to);

if (vex1!=vex2)

{

cout << "(" << edge[i].from <<"->"<

parent[vex2]=vex1;

num++;

if (num==vertexNum-1) return;

}

}

}

/**********寻找根节点************/

template

int EdgeGraph::FindRoot(int parent[], int v)

{

int t=v;

while(parent[t] > -1)

t=parent[t];

return t;

}

/**********遍历输出************/

template

void EdgeGraph::Print()

{

for (int i=0; i

{

cout<<"("<

"<

}

}

6.结果截图

发现不按大小输入weight的值则不能正确生成最小生成树如

排好序输入时则得到正确的最小生成树

结果正确,所以需要按大小顺序输入权值大小的Kruskal算法实际上对较复杂无向网图来说不适用。故思考在程序中添加一个对权值排序的函数(修改对应的from,to)

c语言经典算法

C语言的学习要从基础,100个经典的算法 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? ________________________________________________________________ 程序分析:兔子的规律为数列1,1,2,3,5,8,13,21.... __________________________________________________________________ 程序源代码: main() { long f1,f2; int i; f1=f2=1; for(i=1;i<=20;i++) { printf("%12ld %12ld",f1,f2); if(i%2==0) printf("\n");/*控制输出,每行四个*/ f1=f1+f2;/*前两个月加起来赋值给第三个月*/ f2=f1+f2;/*前两个月加起来赋值给第三个月*/ } } 上题还可用一维数组处理,you try! 题目:判断101-200之间有多少个素数,并输出所有素数。 _________________________________________________________________ 程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除,则表明此数不是素数,反之是素数。 ___________________________________________________________________ 程序源代码: #include "math.h" main() { int m,i,k,h=0,leap=1; printf("\n"); for(m=101;m<=200;m++) { k=sqrt(m+1); for(i=2;i<=k;i++) if(m%i==0) {leap=0;break;} if(leap) {printf("%-4d",m);h++; if(h%10==0) printf("\n"); } leap=1; } printf("\nThe total is %d",h); } 题目:打印出所有的“水仙花数”,所谓“水仙花数”是指一个三位数,其各位数字立方和等于该数本身。例如:153是一个“水仙花数”,因为153=1的三次方+5的三次方+3的三次方。 __________________________________________________________________ 程序分析:利用for循环控制100-999个数,每个数分解出个位,十位,百位。 ___________________________________________________________________ 程序源代码:

Kruskal算法求最小生成树

荆楚理工学院 课程设计成果 学院:_______计算机工程学院__________ 班级: 14计算机科学与技术一班 学生姓名: 志杰学号: 2014407020137 设计地点(单位)_____B5101_________ ____________ 设计题目:克鲁斯卡尔算法求最小生成树__________________________________ 完成日期:2015年1月6日 指导教师评语: ______________ _________________________ ___________________________________________________________________________________ ___________________________________________________________________________________________ ___________________________ __________ _ 成绩(五级记分制):_____ _ __________ 教师签名:__________ _______________

注:介于A和C之间为B级,低于C为D级和E级。按各项指标打分后,总分在90~100为优,80~89为良,70~79为中,60~69为及格,60分以下为不及格。

目录 1 需求分析 (1) 1.1系统目标 (1) 1.2主体功能 (1) 1.3开发环境 (1) 2 概要设计 (1) 2.1功能模块划分 (1) 2.2 系统流程图 (2) 3 详细设计 (3) 3.1 数据结构 (3) 3.2 模块设计 (3) 4测试 (3) 4.1 测试数据 (3) 4.2测试分析 (4) 5总结与体会 (6) 5.1总结: (6) 5.2体会: (6) 参考文献 (7) 附录全部代码 (8)

C语言经典算法100例题目

看懂一个程序,分三步:1、流程;2、每个语句的功能;3、试数; 小程序:1、尝试编程去解决他;2、看答案;3、修改程序,不同的输出结果; 4、照答案去敲; 5、调试错误; 6、不看答案,自己把答案敲出来; 7、实在不会就背会。。。。。周而复始,反复的敲。。。。。 【程序1】 题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? ============================================================== 【程序2】 题目:企业发放的奖金根据利润提成。利润(I)低于或等于10万元时,奖金可提10%;利润高 于10万元,低于20万元时,低于10万元的部分按10%提成,高于10万元的部分,可可提 成7.5%;20万到40万之间时,高于20万元的部分,可提成5%;40万到60万之间时高于 40万元的部分,可提成3%;60万到100万之间时,高于60万元的部分,可提成1.5%,高于 100万元时,超过100万元的部分按1%提成,从键盘输入当月利润I,求应发放奖金总数? ============================================================== 【程序3】 题目:一个整数,它加上100后是一个完全平方数,再加上168又是一个完全平方数,请问该数是多少?============================================================== 【程序4】 题目:输入某年某月某日,判断这一天是这一年的第几天? ============================================================== 【程序5】 题目:输入三个整数x,y,z,请把这三个数由小到大输出。 ============================================================== 【程序6】 题目:用*号输出字母C的图案。 ============================================================== 【程序7】 题目:输出特殊图案,请在c环境中运行,看一看,Very Beautiful! ============================================================== 【程序8】 题目:输出9*9口诀。 ============================================================== 【程序9】 题目:要求输出国际象棋棋盘。 ============================================================== 【程序10】 题目:打印楼梯,同时在楼梯上方打印两个笑脸。 -------------------------------------------------------------------------------- 【程序11】 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月 后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? ==============================================================

kruskal算法求最小生成树

#include #include #include #include using namespace std; #define maxn 110 //最多点个数 int n, m; //点个数,边数 int parent[maxn]; //父亲节点,当值为-1时表示根节点 int ans; //存放最小生成树权值 struct eage //边的结构体,u、v为两端点,w为边权值

{ int u, v, w; }EG[5010]; bool cmp(eage a, eage b) //排序调用 { return a.w < b.w; } int Find(int x) //寻找根节点,判断是否在同一棵树中的依据 { if(parent[x] == -1) return x; return Find(parent[x]); } void Kruskal() //Kruskal算法,parent能够还原一棵生成树,或者森林{ memset(parent, -1, sizeof(parent)); sort(EG+1, EG+m+1, cmp); //按权值将边从小到大排序 ans = 0; for(int i = 1; i <= m; i++) //按权值从小到大选择边 { int t1 = Find(EG[i].u), t2 = Find(EG[i].v); if(t1 != t2) //若不在同一棵树种则选择该边,合并两棵树 { ans += EG[i].w; parent[t1] = t2; printf("最小生成树加入的边为:%d %d\n",EG[i].u,EG[i].v); } } } int main() { printf("输入顶点数和边数:"); while(~scanf("%d%d", &n,&m)) { for(int i = 1; i <= m; i++) scanf("%d%d%d", &EG[i].u, &EG[i].v, &EG[i].w); Kruskal(); printf("最小生成树权值之和为:%d\n", ans); } return 0; }

C语言经典算法100例(1---30)

2008-02-18 18:48 【程序1】 题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? 1.程序分析:可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去 掉不满足条件的排列。 2.程序源代码: main() { int i,j,k; printf("\n"); for(i=1;i<5;i++) /*以下为三重循环*/ for(j=1;j<5;j++) for (k=1;k<5;k++) { if (i!=k&&i!=j&&j!=k) /*确保i、j、k三位互不相同*/ printf("%d,%d,%d\n",i,j,k); } } ============================================================== 【程序2】 题目:企业发放的奖金根据利润提成。利润(I)低于或等于10万元时,奖金可提10%;利润高 于10万元,低于20万元时,低于10万元的部分按10%提成,高于10万元的部分,可可提 成7.5%;20万到40万之间时,高于20万元的部分,可提成5%;40万到60万之间时高于 40万元的部分,可提成3%;60万到100万之间时,高于60万元的部分,可提成1.5%,高于 100万元时,超过100万元的部分按1%提成,从键盘输入当月利润I,求应发放奖金总数? 1.程序分析:请利用数轴来分界,定位。注意定义时需把奖金定义成长整型。 2.程序源代码: main() { long int i; int bonus1,bonus2,bonus4,bonus6,bonus10,bonus; scanf("%ld",&i); bonus1=100000*0.1;bonus2=bonus1+100000*0.75; bonus4=bonus2+200000*0.5; bonus6=bonus4+200000*0.3; bonus10=bonus6+400000*0.15; if(i<=100000)

Kruskal算法说明及图解

1.无向网图及边集数组存储示意图 vertex[6]= 2.Kruskal 方法构造最小生成树的过程 (a)一个图 (b)最小生成树过程1 V0 V1 V2 V3 V4 V5 下标 0 1 2 3 4 5 6 7 8 from 1 2 0 2 3 4 0 3 0 to 4 3 5 5 5 5 1 4 2 weight 12 17 19 25 25 26 34 38 46 V1 V0 V4 V5 V2 V3 V1 V0 V5 V2 V3 V4

(c)最小生成树过程2 (d)最小生成树过程3 (e)最小生成树过程4 3.伪代码 1)初始化辅助数组parent[vertexNum];num=0; 2) 依次考查每一条边for(i=0; i

最小生成树的Kruskal算法实现

#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("请输入边数和顶点数:\n"); 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("请输入有边的2个顶点\n"); scanf("%d %d",&n,&m); while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum) { printf("输入的数字不符合要求请重新输入:\n"); scanf("%d%d",&n,&m); } G->arc[n][m].adj = G->arc[m][n].adj = 1; getchar(); printf("请输入%d与%d之间的权值:\n", 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++) {

线性方程组的数值算法C语言实现(附代码)

线性方程组AX=B 的数值计算方法实验 一、 实验描述: 随着科学技术的发展,线性代数作为高等数学的一个重要组成部分, 在科学实践中得到广泛的应用。本实验的通过C 语言的算法设计以及编程,来实现高斯消元法、三角分解法和解线性方程组的迭代法(雅可比迭代法和高斯-赛德尔迭代法),对指定方程组进行求解。 二、 实验原理: 1、高斯消去法: 运用高斯消去法解方程组,通常会用到初等变换,以此来得到与原系数矩阵等价的系数矩阵,达到消元的目的。初等变换有三种:(a)、(交换变换)对调方程组两行;(b)、用非零常数乘以方程组的某一行;(c)、将方程组的某一行乘以一个非零常数,再加到另一行。 通常利用(c),即用一个方程乘以一个常数,再减去另一个方程来置换另一个方程。在方程组的增广矩阵中用类似的变换,可以化简系数矩阵,求出其中一个解,然后利用回代法,就可以解出所有的解。 2、选主元: 若在解方程组过程中,系数矩阵上的对角元素为零的话,会导致解出的结果不正确。所以在解方程组过程中要避免此种情况的出现,这就需要选择行的判定条件。经过行变换,使矩阵对角元素均不为零。这个过程称为选主元。选主元分平凡选主元和偏序选主元两种。平凡选主元: 如果()0p pp a ≠,不交换行;如果()0p pp a =,寻找第p 行下满足() 0p pp a ≠的第一 行,设行数为k ,然后交换第k 行和第p 行。这样新主元就是非零主元。偏序选主元:为了减小误差的传播,偏序选主元策略首先检查位于主对角线或主对角线下方第p 列的所有元素,确定行k ,它的元素绝对值最大。然后如果k p >,则交换第k 行和第p 行。通常用偏序选主元,可以减小计算误差。 3、三角分解法: 由于求解上三角或下三角线性方程组很容易所以在解线性方程组时,可将系数矩阵分解为下三角矩阵和上三角矩阵。其中下三角矩阵的主对角线为1,上三角矩阵的对角线元素非零。有如下定理: 如果非奇异矩阵A 可表示为下三角矩阵L 和上三角矩阵U 的乘积: A LU = (1) 则A 存在一个三角分解。而且,L 的对角线元素为1,U 的对角线元素非零。得到L 和U 后,可通过以下步骤得到X : (1)、利用前向替换法对方程组LY B =求解Y 。 (2)、利用回代法对方程组UX Y =求解X 。 4、雅可比迭代:

C语言经典算法大全

C语言经典算法大全 老掉牙 河内塔 费式数列 巴斯卡三角形 三色棋 老鼠走迷官(一) 老鼠走迷官(二) 骑士走棋盘 八个皇后 八枚银币 生命游戏 字串核对 双色、三色河内塔 背包问题(Knapsack Problem) 数、运算 蒙地卡罗法求PI Eratosthenes筛选求质数 超长整数运算(大数运算) 长PI 最大公因数、最小公倍数、因式分解 完美数 阿姆斯壮数 最大访客数 中序式转后序式(前序式) 后序式的运算 关于赌博 洗扑克牌(乱数排列) Craps赌博游戏 约瑟夫问题(Josephus Problem) 集合问题 排列组合 格雷码(Gray Code) 产生可能的集合

m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法- 改良的插入排序Shaker 排序法- 改良的气泡排序Heap 排序法- 改良的选择排序快速排序法(一) 快速排序法(二) 快速排序法(三) 合并排序法 基数排序法 搜寻 循序搜寻法(使用卫兵) 二分搜寻法(搜寻原则的代表)插补搜寻法 费氏搜寻法 矩阵 稀疏矩阵 多维矩阵转一维矩阵 上三角、下三角、对称矩阵 奇数魔方阵 4N 魔方阵 2(2N+1) 魔方阵

1.河内之塔 说明河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的,河内为越 战时北越的首都,即现在的胡志明市;1883年法国数学家Edouard Lucas曾提及这个故事,据说创世纪时Benares有一座波罗教塔,是由三支钻石棒(Pag)所支撑,开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘(Disc),并命令僧侣将所有的金盘从第一根石棒移至第三根石棒,且搬运过程中遵守大盘子在小盘子之下的原则,若每日仅搬一个盘子,则当盘子全数搬运完毕之时,此塔将毁损,而也就是世界末日来临之时。 解法如果柱子标为ABC,要由A搬至C,在只有一个盘子时,就将它直接搬至C,当有两个盘 子,就将B当作辅助柱。如果盘数超过2个,将第三个以下的盘子遮起来,就很简单了,每次处理两个盘子,也就是:A->B、A ->C、B->C这三个步骤,而被遮住的部份,其实就是进入程式的递回处理。事实上,若有n个盘子,则移动完毕所需之次数为2^n - 1,所以当盘数为64时,则所需次数为:264- 1 = 18446744073709551615为5.05390248594782e+16年,也就是约5000世纪,如果对这数字没什幺概念,就假设每秒钟搬一个盘子好了,也要约5850亿年左右。 #include void hanoi(int n, char A, char B, char C) { if(n == 1) { printf("Move sheet %d from %c to %c\n", n, A, C); } else { hanoi(n-1, A, C, B); printf("Move sheet %d from %c to %c\n", n, A, C); hanoi(n-1, B, A, C); } } int main() { int n; printf("请输入盘数:"); scanf("%d", &n); hanoi(n, 'A', 'B', 'C'); return 0; }

Kruskal算法

Kruskal 算法构造最小生成树 构造赋权图(,,)G V E W =,其中12{,,,}n V v v v = 为顶点集合,其中i v 表示第i 个顶点,12{,,,,}i E e e e = 为边的集合,()ij n n W w ?=为邻接矩阵,其中 i j i j ij i j v v v v w v v ∈??=?∞??顶点与之间的距离,当(,) E ,与之间没有边时 科茹斯克尔(Kruskal )算法如下: (1)选1e E ∈(E 为边的集合),使得1e 是权重最小的边。 (2)若12,,e i e e …,已选好,则从12{,,e }i E e e -…,中选取1i e +,使得 i )121{,,e }i e e +…,中无圈,且 ii )是1i e +是12{,,e }i E e e -…,中权重最小的边。 (3)直到选得1V e - 为止。(V 是集合V 中元素的个数) 例:已知9个村庄之间的两两距离见表5,要架设通讯线路把9个村庄连接起来,求所需要通讯线的最小长度。 表5 10个村庄的两两距离数据(单位:km ) (,,)G V E W =,其中129{,, ,}V v v v = 为顶点集合,其中i v 表示第i 个村庄,12{,,,,}i E e e e = 为边的集合,99()ij W w ?=为邻接矩阵,其中 i j i j ij i j v v v v w v v ∈??=?∞??村庄与之间的距离,当(,) E ,与之间没有通讯路线时 科茹斯克尔(Kruskal )算法如下: (1)选1e E ∈(E 为边的集合),使得1e 是距离最小的边。

c语言经典算法100例

60.题目:古典问题:有一对兔子,从出生后第3个月 起每个月都生一对兔子,小兔 子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总 数 为多少? _________________________________________________________________ _ 程序分析:兔子的规律为数列1,1,2,3,5,8,13,21.... _________________________________________________________________ __ 程序源代码: main() { long f1,f2; int i; f1=f2=1; for(i=1;i<=20;i++) { printf("%12ld %12ld",f1,f2); if(i%2==0) printf("\n");/*控制输出,每行四个*/

f1=f1+f2;/*前两个月加起来赋值给第三个月*/ f2=f1+f2;/*前两个月加起来赋值给第三个月*/ } } 上题还可用一维数组处理,you try! 61.题目:判断101-200之间有多少个素数,并输出所有素数。 _________________________________________________________________ _ 1 程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被 整 除,则表明此数不是素数,反之是素数。 _________________________________________________________________ __ 程序源代码: #include "math.h" main() { int m,i,k,h=0,leap=1;

最小生成树(Prim、Kruskal算法)整理版

一、树及生成树的基本概念 树是无向图的特殊情况,即对于一个N个节点的无向图,其中只有N-1条边,且图中任意两点间有且仅有一条路径,即图中不存在环,这样的图称为树,一般记为T。树定义有以下几种表述: (1)、T连通、无圈、有n个结点,连通有n-1条边;(2)、T无回路,但不相邻的两个结点间联以一边,恰得一个圈;(3)、T连通,但去掉任意一边,T就不连通了(即在点集合相同的图中,树是含边数最少的连通图);(4)、T的任意两个结点之间恰有一条初等链。 例如:已知有六个城市,它们之间要架设电话线,要求任 意两个城市均可以互相通话,并且电话线的总长度最短。若用 六个点v1…v6代表这六个城市,在任意两个城市之间架设电话 线,即在相应的两个点之间连一条边。这样,六个城市的一个 电话网就作成一个图。任意两个城市之间均可以通话,这个图 必须是连通图,且这个图必须是无圈的。否则,从圈上任意去 掉一条边,剩下的图仍然是六个城市的一个电话网。图5-6是 一个不含圈的连通图,代表了一个电话线网。 生成树(支撑树) 定义:如果图G’是一棵包含G的所有顶点的树,则称G’是G的一个支撑树或生成树。例如,图5-7b是图5-7a的一个支撑树。 定理:一个图G有生成树的条件是G是连通图。 证明:必要性显然; 充分性:设图G是连通的,若G不含圈,则按照定义,G是一个树,从而G是自身的一个生成树。若G含圈,则任取G的一个圈,从该圈中任意去掉一条边,得到图G的一生成子图G1。若G1不含圈,则G1是G的一个生成树。若G1仍然含圈,则任取G1的一个圈,再从圈中任意去掉一条边,得到图G的一生成子图G2。依此类推,可以得到图G的一个生成子 图G K,且不含圈,从而G K是一个生成树。 寻找连通图生成树的方法: 破圈法:从图中任取一个圈,去掉一条边。再对剩下的图 重复以上步骤,直到不含圈时为止,这样就得到一个生成树。 取一个圈(v1,v2,v3,v1),在一个圈中去掉边e3。在剩下的图 中,再取一个圈(v1,v2,v4,v3,v1),去掉边e4。再从圈(v3,v4,v5,v3) 中去掉边e6。再从圈(v1,v2,v5,v4,v3,v1)中去掉边e7, 这样,剩下的图不含圈,于是得到一个支撑树,如图所示。 避圈法:也称为生长法,从图中某一点开始生长边,逐步扩展成长为一棵树,每步选取与已入树的边不构成圈的那些边。

C语言经典算法题目及答案

题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? 1.程序分析:可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去 掉不满足条件的排列。 2.程序源代码: main() { int i,j,k; printf("\n"); for(i=1;i<5;i++) /*以下为三重循环*/ for(j=1;j<5;j++) for (k=1;k<5;k++) { if (i!=k&&i!=j&&j!=k) printf("%d,%d,%d\n",i,j,k); } } ============================================================== 【程序2】 题目:企业发放的奖金根据利润提成。利润(I)低于或等于10万元时,奖金可提10%;利润高 于10万元,低于20万元时,低于10万元的部分按10%提成,高于10万元的部分,可可提成7.5%;20万到40万之间时,高于20万元的部分,可提成5%;40万到60万之间时高于40万元的部分,可提成3%;60万到100万之间时,高于60万元的部分,可提成1.5%,高于 100万元时,超过100万元的部分按1%提成,从键盘输入当月利润I,求应发放奖金总数? 1.程序分析:请利用数轴来分界,定位。注意定义时需把奖金定义成长整型。 2.程序源代码: main() { long int i; int bonus1,bonus2,bonus4,bonus6,bonus10,bonus; scanf("%ld",&i); bonus1=100000*0.1;bonus2=bonus1+100000*0.75; bonus4=bonus2+200000*0.5; bonus6=bonus4+200000*0.3; bonus10=bonus6+400000*0.15; if(i<=100000) bonus=i*0.1; else if(i<=200000) bonus=bonus1+(i-100000)*0.075; else if(i<=400000) bonus=bonus2+(i-200000)*0.05; else if(i<=600000) bonus=bonus4+(i-400000)*0.03;

实验5 最小生成树算法的设计与实现(报告)

实验5 最小生成树算法的设计与实现 一、实验目的 1、根据算法设计需要, 掌握连通图的灵活表示方法; 2、掌握最小生成树算法,如Prim、Kruskal算法; 3、基本掌握贪心算法的一般设计方法; 4、进一步掌握集合的表示与操作算法的应用。 二、实验内容 1、认真阅读算法设计教材和数据结构教材内容, 熟习连通图的不同表示方法和最小生成树算法; 2、设计Kruskal算法实验程序。 有n个城市可以用(n-1)条路将它们连通,求最小总路程的和。 设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止。 三、Kruskal算法的原理方法 边权排序: 1 3 1 4 6 2 3 6 4 1 4 5 2 3 5 3 4 5 2 5 6 1 2 6 3 5 6 5 6 6 1. 初始化时:属于最小生成树的顶点U={}

不属于最小生成树的顶点V={1,2,3,4,5,6} 2. 根据边权排序,选出还没有连接并且权最小的边(1 3 1),属于最小生成树 的顶点U={1,3},不属于最小生成树的顶点V={2,4,5,6}

3. 根据边权排序,选出还没有连接并且权最小的边(4 6 2),属于最小生成树的顶点U={{1,3},{4,6}}(还没有合在一起,有两颗子树),不属于最小生成树的顶点V={2,5} 4. 根据边权排序,选出还没有连接并且权最小的边(3 6 4),属于最小生成树的顶点U={1,3,4,6}(合在一起),不属于最小生成树的顶点V={2,5}

5. 根据边权排序,选出还没有连接并且权最小的边(3 6 4),属于最小生成树的顶点U={1,2,3,4,6},,不属于最小生成树的顶点V={5} 6. 根据边权排序,选出还没有连接并且权最小的边(3 6 4),属于最小生成树的顶点U={1,2,3,4,5,6}此时,最小生成树已完成

经典滤波算法及C语言程序

经典的滤波算法(转) 1、限幅滤波法(又称程序判断滤波法) A、方法: 根据经验判断,确定两次采样允许的最大偏差值(设为A) 每次检测到新值时判断: 如果本次值与上次值之差<=A,则本次值有效 如果本次值与上次值之差>A,则本次值无效,放弃本次值,用上次值代替本次值 B、优点: 能有效克服因偶然因素引起的脉冲干扰 C、缺点 无法抑制那种周期性的干扰 平滑度差 2、中位值滤波法 A、方法: 连续采样N次(N取奇数) 把N次采样值按大小排列 取中间值为本次有效值 B、优点: 能有效克服因偶然因素引起的波动干扰 对温度、液位的变化缓慢的被测参数有良好的滤波效果 C、缺点: 对流量、速度等快速变化的参数不宜 3、算术平均滤波法 A、方法: 连续取N个采样值进行算术平均运算 N值较大时:信号平滑度较高,但灵敏度较低 N值较小时:信号平滑度较低,但灵敏度较高 N值的选取:一般流量,N=12;压力:N=4 B、优点: 适用于对一般具有随机干扰的信号进行滤波 这样信号的特点是有一个平均值,信号在某一数值范围附近上下波动 C、缺点: 对于测量速度较慢或要求数据计算速度较快的实时控制不适用 比较浪费RAM

递推平均滤波法对偶然出现的脉冲性干扰的抑制作用较差 4、递推平均滤波法(又称滑动平均滤波法) A、方法: 把连续取N个采样值看成一个队列 队列的长度固定为N 每次采样到一个新数据放入队尾,并扔掉原来队首的一次数据.(先进先出原则) 把队列中的N个数据进行算术平均运算,就可获得新的滤波结果 N值的选取:流量,N=12;压力:N=4;液面,N=4~12;温度,N=1~4 B、优点: 对周期性干扰有良好的抑制作用,平滑度高 适用于高频振荡的系统 C、缺点: 灵敏度低 对偶然出现的脉冲性干扰的抑制作用较差 不易消除由于脉冲干扰所引起的采样值偏差 不适用于脉冲干扰比较严重的场合 比较浪费RAM 5、中位值平均滤波法(又称防脉冲干扰平均滤波法) A、方法: 相当于“中位值滤波法”+“算术平均滤波法” 连续采样N个数据,去掉一个最大值和一个最小值 然后计算N-2个数据的算术平均值 N值的选取:3~14 B、优点: 融合了两种滤波法的优点 对于偶然出现的脉冲性干扰,可消除由于脉冲干扰所引起的采样值偏差 C、缺点: 测量速度较慢,和算术平均滤波法一样 比较浪费RAM 6、限幅平均滤波法 A、方法: 相当于“限幅滤波法”+“递推平均滤波法” 每次采样到的新数据先进行限幅处理, 再送入队列进行递推平均滤波处理 B、优点: 融合了两种滤波法的优点 对于偶然出现的脉冲性干扰,可消除由于脉冲干扰所引起的采样值偏差 C、缺点: 比较浪费RAM

Kruskal算法求最小生成树(java)

Kruskal算法求最小生成树(JA V A) 代码: package homework; import java.util.Scanner; import java.util.Arrays; import java.util.ArrayList; class Edge { public int start;//始边 public int end;//终边 public double cost;//权重 } public class MinSpanningTree_Kruskal{ private static int MAX = 100; private ArrayList edge = new ArrayList();//整个图的边 private ArrayList target = new ArrayList();//目标边,最小生成树private int[] parent = new int[MAX];//标志所在的集合 private static double INFINITY = 99999999.99;//定义无穷大 private double mincost = 0.0;//最小成本 private int n;//结点个数 public MinSpanningTree_Kruskal(){} public static void main(String args[]){ MinSpanningTree_Kruskal sp = new MinSpanningTree_Kruskal(); sp.init(); sp.kruskal(); sp.print(); }//初始化 public void init(){ Scanner scan = new Scanner(System.in); int p,q; double w; System.out.println("请输入结点个数:"); n = scan.nextInt(); System.out.println("请输入各条边及权值(每次输入一组数据按回车确认," + "最后输入-1 -1 -1 结束输入过程)"); while(true){ p = scan.nextInt(); q = scan.nextInt(); w = scan.nextDouble();

求最小生成树(Kruskal算法)实验报告

学生实验报告 学院:软件与通信工程学院 课程名称:离散数学(软件) 专业班级: 12软件2班 姓名:杨滨 学号: 0123707

学生实验报告(2) 一、实验综述 1、实验目的及要求 (1)了解求最优化问题的贪心算法,了解贪心法的基本要素,学会如何使用贪心策略设计算法; (2)掌握Prim 算法和Kruskal 算法的思想及两者之间的区别; (3)编写程序,分别利用Prim 算法和Kruskal 算法实现,求出最小代价生成树,输出构成最小代价生成树的边集。 实验要求: 给出如右图的边权图,求最小生成树。 认真完成实验题,能正确运行,提交实验报告并上 传程序,实验报告要求写出操作步骤、结果、问题、解 决方法、体会等。 2、实验仪器、设备或软件 计算机、VC++6.0、office 、相关的操作系统等。 二、实验过程(实验步骤、记录、数据、分析) #include #define VERTS 6 struct edge { int from,to; //起顶点,终顶点 int find,val; //标记,顶点间边长 struct edge *next; }; typedef struct edge node; node *find_min_cost(node *); void min_tree(node *); int v[VERTS+1]={0}; //记录顶点即下标,值即出现过的次数 void main() { int data[10][3]={{1,0,6},{0,3,5},{3,5,2},{5,4,6}, {4,1,3},{2,1,5},{2,0,1},{2,3,5},{2,5,4},{2,4,6}};

C语言经典算法详解

一分而治之算法 分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题,可以: 1) 把它分成两个或多个更小的问题; 2) 分别解决每个小问题; 3) 把各小问题的解答组合起来,即可得到原问题的解答。小问题通常与原问题相似,可以递归地使用分而治之策略来解决。下列通过实例加以说明。 例:利用分而治之算法求一个整数数组中的最大值。

练习:[找出伪币] 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的,并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。

二贪心算法 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 贪心算法(Greedy algorithm)是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,它省去了为找最优解要穷尽所有可能而必须耗费的大量时间,它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪婪法不要回溯。 贪心算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序,按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解,则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题,往往可能有好几种量度标准。初看起来,这些量度标准似乎都是可取的,但实际上,用其中的大多数量度标准作贪婪

相关主题