最小生成树matlab代码Kruskal算法,用于二维网络生成

这篇具有很好参考价值的文章主要介绍了最小生成树matlab代码Kruskal算法,用于二维网络生成。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、Kruskal算法

        克鲁斯卡尔算法(Kruskal)是一种使用贪婪方法的最小生成树算法。 该算法初始将图视为森林,图中的每一个顶点视为一棵单独的树。 一棵树只与它的邻接顶点中权值最小且不违反最小生成树属性(不构成环)的树之间建立连边。

二、具体效果

matlab最小生成树代码,matlab代码,算法,matlab,图论

 

最小生成树法生成网络文章来源地址https://www.toymoban.com/news/detail-535815.html

三、代码

clc
clear
close all
P=[20,100;3,31;83,44;93,19;77,14;85,44;18,35;84,39;18,49;37,46;9,86;46,85;68,40;9,5;45,15;23,89;5,40;44,61;72,50;46,68];
%计算距离矩阵
D=inf*ones(size(P,1),size(P,1));
for i=1:size(P,1)-1
    for j=i+1:size(P,1)
            D(i,j)=norm(P(i,:)-P(j,:));
    end
end
plot(P(:,1),P(:,2),'.k','MarkerSize',20)
hold on
%Kruskal算法
temp=[];   %已经选择的节点
while size(unique(temp),1)<size(P,1)
    %寻找最短的边
    [xx,yy]=find(D==min(min(D)));
    ii=xx(1);
    jj=yy(1);
    %判断ii和jj加进去是否成环
    io=judge(P,temp,ii,jj);
    if io==0
        temp=[temp;ii,jj];
        plot([P(ii,1),P(jj,1)],[P(ii,2),P(jj,2)],'-b')
        hold on
        pause(0.1)
    end
    D(ii,jj)=inf;
end

到了这里,关于最小生成树matlab代码Kruskal算法,用于二维网络生成的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 最小生成树——Kruskal算法详解

    1.Kruskal算法解决问题 :最小生成树 2.Kruskal所需要的前提知识: 边集数组(引用)和 结构体 3.Kruskal算法主要思想: Kruskal算法将 n 个点看成 n 个独立的连通分支。 首先按边权大小排序。 然后只要在 m 条边里按 下表从小到大遍历 选出 合适 的 n - 1 条(前提条件:选出的边不

    2024年02月03日
    浏览(41)
  • 最小生成树(Prim算法,Kruskal算法)

    (1)生成树: 如果在一个无向连通图不包含回路(连通图中不存在环),则为一个树 (2)最小生成树(minimal spanning tree): 在一个图所有生成树中,代价最小的生成树称为最小生成树 (3)生成树的代价: 在一个无向连通网中,生成树各边的权值之和称为该生成树的代价

    2024年02月08日
    浏览(44)
  • 图的最小生成树-Kruskal算法

    目录 问题引入  程序设计  程序分析 本节文章 【问题描述】 编写程序,利用带权无向图的邻接矩阵存储,实现图的最小生成树Kruskal算法。

    2024年02月08日
    浏览(58)
  • 859. Kruskal算法求最小生成树

    给定一个 nn 个点 mm 条边的无向图,图中可能存在重边和自环,边权可能为负数。 求最小生成树的树边权重之和,如果最小生成树不存在则输出  impossible 。 给定一张边带权的无向图 G=(V,E)G=(V,E),其中 VV 表示图中点的集合,EE 表示图中边的集合,n=|V|n=|V|,m=|E|m=|E|。 由

    2023年04月09日
    浏览(39)
  • 最小生成树算法之Kruskal算法(c++)

    与Prim算法生成图的最小生成的树算法不同在于: Prim算法是基于图中的顶点的,且不依赖于边,Prim从顶点出发拓展,依次找每个顶点相邻的权值最小的边,直至生成最小生成树。因此,Prim算法的时间复杂度是O(v^2),适合边稠密图。 而Kruskal算法恰恰相反,是基于图中的边的一

    2024年02月12日
    浏览(42)
  • 最小生成树(Prim算法与Kruskal算法)

    一个连通图的生成树是一个极小的连通子图,它含有图中全部的n个顶点,但只有足以构成一棵树的n-1条边。我们把构造连通网的最小代价生成树称为最小生成树。 例如下图中①、②、③都是左侧图的生成树,但③是构造连通网的最小代价,所以③是该图的最小生成树。 P

    2024年02月05日
    浏览(57)
  • 最小生成树—Kruskal算法和Prim算法

    连通图:在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与顶点v2是连通的。如果图中任 意一对顶点都是连通的,则称此图为连通图。 生成树:一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点 和n-1条边。 最小生成树:构成生成树的

    2024年02月05日
    浏览(46)
  • 图论13-最小生成树-Kruskal算法+Prim算法

    基本思想:按照权值从小到大的顺序选择 n-1 条边,并保证这 n-1 条边不构成回路 具体做法:首先构造一个只含 n 个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中 不产生 回路,直至森林变成一棵树为止。 2.2.1 如果图不联通,直接返回空,该

    2024年02月01日
    浏览(49)
  • 最小(代价)生成树—Prim算法与Kruskal算法

    目录  一、最小生成树的特点 二、最小生成树算法  ① Prim(普里姆)算法 ②Kruskal(克鲁斯卡尔)算法  ③Prim算法与Kruskal算法对比 最小生成树是带权连通图G=(V,E)的生成树中边的权值之和最小的那棵生成树。它具有以下特点: 图G中各边权值互不相等时有唯一的最小生成树。图

    2024年02月01日
    浏览(37)
  • 最小生成树Kruskal、Prim算法C++

    连通图: 在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1和顶点v2是连通的。如果图中任意一对顶点都是连通的,则称此图为连通图。 生成树: 一个连通图的最小连通子图称作为图的生成树。有 n个顶点 的连通图的生成树有 n个顶点和 n-1 条边。 最小生成树: 最小生活

    2024年02月10日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包