Kruskal算法(一) C语言详解

最小生成树

在含有n个顶点的连通图中选择n-1条边,构成一棵极小连通子图,并使该连通子图中n-1条边上权值之和达到最小,则称其为连通网的最小生成树。

例如,对于如上图G4所示的连通网可以有多棵权值总和不相同的生成树。

克鲁斯卡尔算法介绍

克鲁斯卡尔(Kruskal)算法,是用来求加权连通图的最小生成树的算法。

基本思想:按照权值从小到大的顺序选择n-1条边,并保证这n-1条边不构成回路。

具体做法:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中不产生回路,直至森林变成一棵树为止。

克鲁斯卡尔算法图解

以上图G4为例,来对克鲁斯卡尔进行演示(假设,用数组R保存最小生成树结果)。

更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

时间: 2024-11-06 05:38:39

Kruskal算法(一) C语言详解的相关文章

Dijkstra算法(一) C语言详解

迪杰斯特拉算法介绍 迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径. 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止. 基本思想 通过Dijkstra计算图G中的最短路径时,需要指定起点s(即从顶点s开始计算). 此外,引进两个集合S和U.S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离). 初始时,S中只有起点s:U中是除s之外的顶点,并且U中

Prim算法(一) C语言详解

普里姆算法介绍 普里姆(Prim)算法,和克鲁斯卡尔算法一样,是用来求加权连通图的最小生成树的算法. 基本思想 对于图G而言,V是所有顶点的集合:现在,设置两个新的集合U和T,其中U用于存放G的最小生成树中的顶点,T存放G的最小生成树中的边.从所有uU,v(V-U) (V-U表示出去U的所有顶点)的边中选取权值最小的边(u, v),将顶点v加入集合U中,将边(u, v)加入集合T中,如此不断重复,直到U=V为止,最小生成树构造完毕,这时集合T中包含了最小生成树中的所有边. 普里姆算法图解 以上图

Floyd算法(一) C语言详解

弗洛伊德算法介绍 和Dijkstra算法一样,弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法.该算法名称以创始人之一.1978年图灵奖获得者.斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名. 基本思想 通过Floyd计算图G=(V,E)中各个顶点的最短路径时,需要引入一个矩阵S,矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离. 假设图G中顶点个数为N,则需要对矩阵S进行N次更新.初始时,矩阵S中顶点a[i][j]的距离为顶点i到顶点

Kruskal算法(一)之 C语言详解

最小生成树 在含有n个顶点的连通图中选择n-1条边,构成一棵极小连通子图,并使该连通子图中n-1条边上权值之和达到最小,则称其为连通网的最小生成树.  例如,对于如上图G4所示的连通网可以有多棵权值总和不相同的生成树. 克鲁斯卡尔算法介绍 克鲁斯卡尔(Kruskal)算法,是用来求加权连通图的最小生成树的算法. 基本思想:按照权值从小到大的顺序选择n-1条边,并保证这n-1条边不构成回路. 具体做法:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中不产生

邻接矩阵有向图(一) C语言详解

邻接矩阵有向图的介绍 邻接矩阵有向图是指通过邻接矩阵表示的有向图. 上面的图G2包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"<A,B>,<B,C>,<B,E>,<B,F>,<C,E>,<D,C>,<E,B>,<E,D>,<F,G>"共9条边.   上图右边的矩阵是G2在内存中的邻接矩阵示意图.A[i][j]=1表示第i个顶点到第j个顶点是一条边

Python实现的数据结构与算法之基本搜索详解_python

本文实例讲述了Python实现的数据结构与算法之基本搜索.分享给大家供大家参考.具体分析如下: 一.顺序搜索 顺序搜索 是最简单直观的搜索方法:从列表开头到末尾,逐个比较待搜索项与列表中的项,直到找到目标项(搜索成功)或者 超出搜索范围 (搜索失败). 根据列表中的项是否按顺序排列,可以将列表分为 无序列表 和 有序列表.对于 无序列表,超出搜索范围 是指越过列表的末尾:对于 有序列表,超过搜索范围 是指进入列表中大于目标项的区域(发生在目标项小于列表末尾项时)或者指越过列表的末尾(发生在目标项

FLASH ActionScript语言详解

详解 - Go to 跳转到指定的帧 - Play 播放 - Stop 停止 - Toggle High Quality 在高画质和低画质间切换 - Stop All Sounds 停止所有声音的播放 - Get URL 跳转至某个超联结 - FSCommand 发送FSCommand命令 - Load Movie 装载影片 - Unload Movie 卸载影片 - Tell Target 告知目标 - If Frame Is Loaded ..判断帧是否被完全载入 - On Mouse Ev

邻接矩阵无向图(一) C语言详解

邻接矩阵无向图的介绍 邻接矩阵无向图是指通过邻接矩阵表示的无向图. 上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边.由于这是无向图,所以边(A,C)和边(C,A)是同一条边:这里列举边时,是按照字母先后顺序列举的. 上图右边的矩阵是G1在内存中的邻接矩阵示意图.A[i][j]=1表示第i个顶点与第j个顶点是邻接点,A[i][j]=0则表示它们不是邻接

邻接表无向图(一) C语言详解

邻接表无向图的介绍 邻接表无向图是指通过邻接表表示的无向图. 上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边. 上图右边的矩阵是G1在内存中的邻接表示意图.每一个顶点都包含一条链表,该链表记录了"该顶点的邻接点的序号".例如,第2个顶点(顶点C)包含的链表所包含的节点的数据分别是"0,1,3":而这"