【数据结构】最小生成树 Prim算法 Kruskal算法
最小生成树应用场景：
假设以下场景，有一块木板，板上钉上一些钉子，这些钉子可以由一些细绳连接起来。假设每个钉子可以通过一根或者多根细绳连接起来，那么一定存在这样得情况，即用最少的细绳把所有的钉子连接起来。
更为实际的场景，在某地分布着N个村庄，现在需要在N个村庄之间修路，每个村庄之间的距离不同，问怎么修最短的路把村庄连接起来。
选定一个开始的结点，在一个点集合中，其余点在另一个点集合中，然后找取与这个结点相连的权值最小最小的边，加入第一个点集合，之后再次找寻与这两个节点相邻的权值最小的边加入，循环往复，直到所有的点都存在于第一个点集合中。
注意在选择权值最小的边时，不能够形成回路！！！！
不然就不叫树了啊！！！！
//建立图的邻接矩阵储存结构
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define M 20
#define FINITY 5000 typedef struct
{char vexs[M];int edges[M][M];int n,e;
}Mgraph;typedef struct edgedata
{int begin,end;int length;
}edge;//c=0，表示建立无向图
void creat(Mgraph *g,int c)
{FILE *f;f=fopen("test.txt","r");int i,j,k,w;if(f){fscanf(f,"%d%d",&g->n,&g->e);for(i=0;i<g->n;i++){fscanf(f,"%1s",&g->vexs[i]);}for(i=0;i<g->n;i++){for(j=0;j<g->n;j++){if(i==j) g->edges[i][j]=0;else g->edges[i][j]=FINITY;}}for(k=0;k<g->e;k++){fscanf(f,"%d%d%d",&i,&j,&w);g->edges[i][j]=w;if(c==0){g->edges[j][i]=w;}}fclose(f);}else{g->n=0;}
}void getedge(Mgraph g,edge edges[])
{int i,j,k=0;for(i=0;i<g.n;i++){for(j=0;j<i;j++){if(g.edges[i][j]!=0 && g.edges[i][j]<FINITY){edges[k].begin=i;edges[k].end=j;edges[k++].length=g.edges[i][j];}}}
}void quicksort(edge edges[],int left ,int right)
{edge x;int i,j,flag=1;if(left<right){i=left;j=right;x=edges[i];while(i!=j){while(i<j && x.length<edges[j].length) j--;//找比x.length小的边if(i<j){edges[i]=edges[j];i++;}while(i<j && x.length>edges[i].length) i++;if(i<j){edges[j]=edges[i];j--;}}edges[i]=x;quicksort(edges,left,i-1);quicksort(edges,i+1,right);}
}void kruskal(Mgraph g)
{printf("kruskal算法：\n");int i,j,k=0,ltfl;int cnvx[M];edge edges[M*M];edge tree[M];getedge(g,edges);quicksort(edges,0,g.e-1);for(i=0;i<g.n-1;i++)cnvx[i]=i;for(i=0;i<g.n-1;i++){while(cnvx[edges[k].begin]==cnvx[edges[k].end]) k++;tree[i]=edges[k];ltfl=cnvx[edges[k].end];for(j=0;j<g.n;j++){if(cnvx[j]==ltfl){cnvx[j]=cnvx[edges[k].begin];}}k++;}int w=0;printf("最小生成树是：\n");for(j=0;j<g.n-1;j++){printf("%c-%c %d\n",g.vexs[tree[j].begin],g.vexs[tree[j].end],tree[j].length);w+=tree[j].length;}printf("最小的权值为：%d\n\n",w);
}void prim(Mgraph g,edge tree[])
{printf("prim算法：\n");edge x;int w;int d,min,j,k,s,v;for(v=1;v<=g.n-1;v++){tree[v-1].begin=0;tree[v-1].end=v;tree[v-1].length=g.edges[0][v];}for(k=0;k<=g.n-3;k++){min=tree[k].length;s=k;for(j=k+1;j<=g.n-2;j++){if(tree[j].length<min){min=tree[j].length;s=j;}}v=tree[s].end;if(s!=k){x=tree[s];tree[s]=tree[k];tree[k]=x;}for(j=k+1;j<=g.n-2;j++){d=g.edges[v][tree[j].end];if(d<tree[j].length){tree[j].length=d;tree[j].begin=v;}}}w=0;for(j=0;j<=g.n-2;j++){printf("%c-%c %d\n",g.vexs[tree[j].begin],g.vexs[tree[j].end],tree[j].length);w+=tree[j].length;}printf("最小权值是：%d\n",w);
}void print(Mgraph *g)
{int i,j;printf("一共有%d个边,%d个点。\n",g->e,g->n);printf("各个元素信息：\n");for(i=0;i<g->n;i++){printf("%c ",g->vexs[i]);} printf("\n");printf("对应的邻接矩阵：\n");for(i=0;i<g->n;i++){for(j=0;j<g->n;j++){printf("%-5d",g->edges[i][j]);}printf("\n");}
}int main ()
{edge tree[M];Mgraph g;creat(&g,0);printf("\n");printf("输出：\n"); print(&g);kruskal(g);prim(g,tree);return 0;
}
Kruskal算法
这串代码和上面的功能一样，只不过可以更清楚地看到变化的过程
void kruskal(Mgraph g)
{int i,j,k=0,ltfl;int cnvx[M];edge edges[M*M];//存放图的所有边edge tree[M];//存放最小生成树的信息getedge(g,edges);//获取各个边的信息printf("Before quicksort:\n");for(i=0;i<g.e;i++){printf("%d %d %d\n",edges[i].beg,edges[i].en,edges[i].length);}printf("\n");quick_sort(edges,0,g.e-1);//按照权值从小到大排序printf("After quicksort:\n");for(i=0;i<g.e;i++){printf("%d %d %d\n",edges[i].beg,edges[i].en,edges[i].length);}printf("\n");for(i=0;i<g.n;i++)cnvx[i]=i;//设置每个点的连通分量为其顶点序号for(i=0;i<g.n-1;i++)//最小生成树，必须使用且仅使用n-1条边来连接网络中的n个顶点{//edges[k].beg 和 edges[k].en已经在一个连通分量中，再添加这两个顶点的边的话，会构成回路while(cnvx[edges[k].beg]==cnvx[edges[k].en])k++;tree[i]=edges[k];ltfl=cnvx[edges[k].en];//记录选中边的终点的连通分量编号for(j=0;j<g.n;j++)//把两个连通分量变成一个连通分量if(cnvx[j]==ltfl)cnvx[j]=cnvx[edges[k].beg];printf("************\n");printf("i=%d k=%d ltfl=%d \n",i,k,ltfl);for(int p=0;p<g.n;p++)printf("cnvx[%d]=%d\n",p,cnvx[p]);k++;}for(j=0;j<g.n-1;j++){printf("%c %c %d\n",g.vex[tree[j].beg],g.vex[tree[j].en],tree[j].length);}
}相关文章：
.net内存回收与Dispose﹐Close﹐Finalize方法
.net内存回收与Dispose﹐Close﹐Finalize方法 一. net的对象使用一般分为三种情况﹕ 1.创建对象2.使用对象3.释放对象 二.创建对象1.创建对象实际分为两个步骤﹕变量类型宣告和初始化对象 2.变量类型宣告(declare),如﹕ FileStream fs这行代码会在当前的变量作用域空间(栈或堆)…
SLAM学习--------相机位姿表示-李群李代数
slam 求解相机的位姿求解核心思想：将有约束的李群问题转换成无约束的李代数问题，然后使用高斯牛顿算法或者LM(列文伯格-马夸尔特法)求解。 人们找了很多以相机位姿为变量的误差函数，比如光度误差，重投影误差，3D几何误…
【ACM】杭电OJ 2063
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid2063 借鉴：http://blog.sina.com.cn/s/blog_ac5ed4f30101ewjk.html 二分图（二部图）：图论中的一种特殊模型。设G(V,E)是一个无向图，如果顶点V可以分割…
AngularJs表单自动验证
angular-auto-validate 地址：https://github.com/jonsamwell/angular-auto-validate 引用： <script src"/Assets/JS/AngularJS/angular-auto-validate/dist/jcs-auto-validate.js" charset"utf-8"></script> 依赖&#…
AlwaysVisibleControlExtender
今天早上学习了AlwaysVisibleControlExtender控件，感觉还是不错。下午就写点东西，总结一下使用方法。 简单使用示例(显示当前时间) 1）在VS下，新建一个ASP.NET AJAX-Enabled Web Project项目，命名为AlwaysVisibleC…
Depth graph
深度相机 定义：可以直接获取场景中物体距离摄像头物理距离的相机。在计算机视觉系统中，三维场景信息为图像分割、目标检测、物体跟踪等各类计算机视觉应用提供了更多的可能性，而深度图像（Depth map）作为一种普遍的三维…
【ACM】POJ 1852
【问题描述】 一队蚂蚁在一根水平杆上行走，每只蚂蚁固定速度 1cm/s. 当一只蚂蚁走到杆的尽头时，立即从秆上掉落. 当两只蚂蚁相遇时它们会掉头向相反的方向前进. 我们知道每只蚂蚁在杆上的初始位置, 但是, 我们不知道蚂蚁向哪个方向前行. 你的任务是计算…
ZStack--通过Ansible实现全自动化
2019独角兽企业重金招聘Python工程师标准>>> Agent是一种常见的IaaS软件管理设备的方式；例如，ZStack使用Python agents去管理KVM主机。因为海量的设备，安装和升级agents成为巨大的挑战，所以大多数IaaS软件把这个问题留…
SVO 半直接视觉里程计
SVO 从名字来看，是半直接视觉里程计，所谓半直接是指通过对图像中的特征点图像块进行直接匹配来获取相机位姿，而不像直接匹配法那样对整个图像使用直接匹配。整幅图像的直接匹配法常见于RGBD传感器，因为RGBD传感器能获取整幅图像的…
css构造文本
1. 1. 文本缩进text-indent：值；值为数字，最常用的数值单位是px(像素)，也可以直接是百分比！text-indent:100px;text-indent:10%;2. 文本对齐text-align:对其方式;可以的值为：left、center、right3. 文本行高…
【数据结构】单链表的逆序输出（两种方法）
第一种方法：转换指针方向 即：将一个已经创建好的单链表进行指针域的改变 今天突然被问到单链表逆序的问题，弄了好久才看出别人的程序有啥问题，就重新写了一遍。 今天才在CSDN客户端上看到美团的面试题是冒泡排序。 一个看似简单…
koa+mongoose基础入门
1.mongoose基本使用 1.安装mongodb npm install mongodb 2.引入mongodb数据表，连接mongodb，通过node来对mongodb进行异步的增删改查 const mongodb requrie(mongodb); mongodb.MongoClient.connect("mongodb://localhost/db1", function(err,…
视觉SLAM学习（三）--------SLAM 综述
SLAM概述 参考资料分享来自本人博客：https://blog.csdn.net/Darlingqiang/article/details/78840931 SLAM一般处理流程包括track和map两部分。所谓的track是用来估计相机的位姿，也叫front-end。而map部分(back-end)则是深度的构建，通过前面…
【数据结构】所有顶点对的最短路径 Floyd算法
所有顶点对的最短路径问题是指：对于给定的有向图G(V，E),求任意一对顶点之间的最短路径。 可以求解得到的 的递推公式： #include <stdio.h> #include <stdlib.h> const int FINITY 5000; const int M 20; typedef struct {ch…
backbone学习总结（二）
今天来看下backbone的路由控制的功能。其实个人感觉backbone，模块就那么几个，熟悉它的框架结构，以及组成，就差不多。 废话不多说，我们来看看还剩下的功能。 关于路由和历史管理 通过 Backbone.Router.extend 来创建路由…
人工智能--野人过河
课程简介 人工智能（Artificial Intelligence），英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能的定义可以分为两部分，即“人工”和“智能”。“人工”比较好…
java对cookie的操作
原文：http://www.cnblogs.com/muzongyan/archive/2010/08/30/1812552.html java对cookie的操作比较简单，主要介绍下建立cookie和读取cookie，以及如何设定cookie的生命周期和cookie的路径问题。 建立一个无生命周期的cookie，即随着…
【ACM】POJ 3069
【问题描述】 Saruman the White must lead his army along a straight path from Isengard to Helm’s Deep. To keep track of his forces, Saruman distributes seeing stones, known as palantirs, among the troops. Each palantir has a maximum effective range of R u…
sparkCore源码解析之思维脑图
2019独角兽企业重金招聘Python工程师标准>>> 在学习sparkCore时，有几个模块的概念理解不是很透彻，故对照源码进行学习，并将结果一脑图的形式呈现，方便后续的持续学习。 详细内容见： sparkCore源码解析之blo…
pangilin 安装编译
make pangolin 的时候报错 ootsun:/home/sun/AR/orb/Pangolin-0.5/build# make [ 1%] Building CXX object src/CMakeFiles/pangolin.dir/log/packetstream.cpp.o /home/sun/AR/orb/Pangolin-0.5/src/log/packetstream.cpp: 在函数‘void pangolin::WaitUntilPlaybackTim…
PHP实现求阶乘
function factorial ($x){if ($x > 1) {$s $x * factorial ($x - 1);} else {$s $x;}return $s; }$x 100;echo $x."的阶乘的为".factorial($x);转载于:https://blog.51cto.com/chensenlin/1854679
【ACM】杭电OJ 2064（汉诺塔III）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid2064 思路： 1、将n-1个盘从A移到C f(n-1)次 2、将第n个从A移到B 1次 3、将n-1个盘从C移到A f(n-1)次 4、将第n个从B移到C 1次 5、将n-1个盘从A移到C f(n-1)次 #include<cstdio> #inclu…
文件上传至阿里云
public static String uploadFile2OSS(InputStream instream, String fileName) throws IOException {String imageName null;OSSClient ossClient null;try {ClientConfiguration conf new ClientConfiguration();// 请求超时时间设置conf.setConnectionTimeout(5000);// 请…
ORB-SLAM2安装
安装顺利与否可能会与Ubuntu版本有关。（ubuntu16.04 gcc4.8.5这个很重要偶，本班的直接决定Pangolin能不能安装成功，如果遇到哦问题的朋友可以参考一下链接 http://blog.csdn.net/Darlingqiang/article/details/78928873）亲测可用…
iOS 系统分析（一） 阅读内核准备知识
原文出自【听云技术博客】：http://blog.tingyun.com/web/a... 0x01 iOS体系架构1.1 iOS 系统的整体体系架构 用户体验( The User Experience layer )：SpringBoard 同时支持 Spotlight。 应用软件开发框架（The Application Frameworks layer&a…
【数据结构】拓扑排序
如果一个有向图中没有包含简单的回路，这样的图为有向无环图。 图中的顶点代表事件（活动），图中的有向边说明了事件之间的先后关系。这种用顶点表示活动，用弧表示活动时间的优先关系的有向图称为顶点表示活动的网&#…
Java8自定义条件让集合分组
** 将一个指定类型对象的集合按照自定义的一个操作分组； 每组对应一个List、最终返回结果类型是:List<List<T>> param <T>*/static class GroupToList<T> implements Collector<T, List<List<T>>, List<List<T>&g…
ROS_Kinetic ubuntu 16.04
ROS_Kinetic系列学习(一)，在ubuntu 16.04安装ROS Kinetic。 http://wiki.ros.org/kinetic/Installation/Ubuntu 通过网页快速了解Linux（Ubuntu）和ROS机器人操作系统，请参考实验楼在线系统如下： 纯净定制版镜像已经…
android 获取手机GSM/CDMA信号信息,并获得基站信息
本文转自：http://software.intel.com/zh-cn/blogs/2011/12/16/android-gsmcdma/ 在Android中我们常用的轻松获取WIFI信号列表，那如何获取CDMA或者GSM的手机信号呢？系统提供了TelephonyManager类，此类非常丰富，基本你所…
【数据结构】关键路径
在有向图中，如果用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间，这样的活动称为边表示活动的网，简称AOE网（Activity On Edge）。通常可以用AOE网来估算工程的完成时间，他不…