最小生成二叉树-prim算法

时间:2022-06-14 12:12:18

1.prim算法:一种计算生成最小生成树的方法,它的每一步都会为一棵生长中的树添加一条边.

2.时间复杂度:

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAdEAAABuCAIAAAD3Sr7YAAAOwElEQVR4nO2dwXXjOBAFncOGwlDmpiD2MAEwhg1BCWwQ2kR8cw4+cQ+yKRDd/dEgYVnyVL1580gQbAA0WIIgSnh5AwCAe/HyDgDjeHt7++4qwEODcwFGgnNBg3MBRoJzQYNzAUaCc0GDcwFGgnNBg3MBRoJzQYNzAUaCc0GDcwFGgnNB03buFKDzZw7pOBmmafr161cmW7LcMmCULVntZKFl+vELAt/OEedGfaZ5D0YZ3B7V1c2G3KRVhH0pP4asc3XKvqND/py/fv3KdMdmDadp+vfff9eA1223emt6V7nNaCIPPBFN50Yd5r3nXjvSbTJ3qGBH5Extd9wvT8pdx7m7c4oI12Fp9Eet6vz792+b6AYU1VvTRS+p8oirp3MeuTjwLSSd+95jWB1kHR9kelqzj7nVy1RMREsWnbwUz35r3HucW+bp+huICNWYVGz//v3bPWprYvtxVGiUTdSk2YTkZYQHpNe5US+6Zvjnn39E57Qx3YKiRJGhWTfRrmaiSM9kePZbQzm3efXdv7rdqKK5A8l919EtS2+7dbYZolZ0tVSUVaaXrwSiXHgKBo5zp8K5ZWLkXBcd39Zkar131I3akb5W9fo2NFPiU98djXFu+VfRn1ZFfz/7Vx/l3LJXRaHc7eiscuj6HnRue3pFJluVx+1qT92r/mQGzudOnc51C3J33c65HiqdG1VVl7UjfSoGH82in/ruSDn3iv20qsqmt9eUpHOTf+ay92Re/9f0MrMNUv7vVsw9PV/5qAnigsBTsGOcG3WkqXNuwUXXwT2UeRYoGVBUzN4yjHPf371xrviT2213175zsbsicT20PmZQpWQq1szs5ln7ivtZXHmtVtxpXzd+uSGemoAHZ9/cQtQhk+Pc95ykNGvO6FmgZnzdcM2Ec6+Ulztyru0TerfXufrSl6/JuiOKo27fsi1dz6qcK5qwrw4493n5FufaDqzvHX0of4cmY9oM0W3lXpzegh6cjnFu5nJkjq6vou/bvrI72rrdNQCPjupT3ovOkXnt0XmiFJz7vHzRfG6J7VS9M7xub1/z2Nm/TG+MSoxm4dwK61uveegp6HhuYR3caSPoQ2NtMnU+n2u7l/6ri3HuFM8buL0nWYdmOjw4w59b0EFsotvN3lv3SJnNvndMdkW3Re7rQfXUpluNn3pfZH9vwV6mqMdkLpbV0L5LOW1HzbYs3c/cXdtLopqL+Lrh0VG3bvBc7Pvur3sXTJ5zbc7oXN1RbWa7Ee12NcrWZ9pO3TbP/WHwGzcAI+E3bkCDcwFGgnNBg3MBRoJzQYNzAUaCc0GDcwFGgnNBg3MBRoJzQYNzAUaCc0Hz8gYAAPfiZQGAcby9vX13FeChwbkAI8G5oMG5ACPBuaDBuQAjwbmgwbkAI8G5oMG5ACPBuaDBuQAjwbmgSTn3r7//y2dwMzcj7Cs3YpomsaszAxwB54Km27l//f3f+s/NYHdFhDVOJmyeVaPXjfX/Mj1iX4kAV5LOfT2f1i43X+pDp/PlfNqmv55Pp/Prx5nFkSLQR+qaEx6StnNXJ5a7ize2tTItM5d6jUoRobpaVarW3bCZAYaQce7r+TTdtHiZp2Lv05iVOdfdy3ya59OndC/zemoRFOs+Mg3numKtdiOf2pw2ZpQ5ytbEHbdW41wxyGWoCwdJOPcyV0PbYuh6O7YRZ6Hcab68nj+ku41U7Jki4GFQznU96I5VhZrdaO7cQjJOBj3OLa1qDYtz4Qht5xZj009W6ZauLKS7Ve6yrNIN4yLdhyX73EI0aK0SxZxANIB1nXt8tLsE41mbzW4D7CblXKPDm0sLHZdTuBvlOt7eTlcwvfDAtOcWotkD+7FYuSuCCOcusb7LU5p+rPQaTeMynwDD2eXcz3FupdIPcTb9uZ0RLk+Fx6Pj+Vwtx2XEODc6aoksWU3jNudqGerCWA7N59amfD2f5ovW5+v5ZJ58cCLBw7BzbmEx41yR06Ynh892d0UPTu1Mrk3nAzT4CrLPLdw8WY5Sax2/nk/zPIf2DITrBIKHYc+zYtH8wHq0SqyCRM8tVOeKuYUrGecusX8zcQB6yX4n4jKvL/OlHB3pmk/cNge38NzC47PnOxE6w2Kmd5ecc5tF57HDWzGr0JQyQJ6j30MbMSnAxMIjs39uoTxk53ardJs/mluIys1j53Or9MVMMpTn9hYHUHL8u79HjYlxHxt+4wZgJPzeAmhwLsBIcC5ocC7ASHAuaHAuwEhwLmhwLsBIcC5ocC7ASHAuaHAuwEhwLmhe3gAA4F4wzgUYyRvjXJDgXICR4FzQ4FyAkeBc0OBcgJHgXNDgXICR4FzQ4FyAkeBc0OBcgJHgXNDcz7nRshEHEWvqNH8MN/PLudVP7jbXYdNr/OgqDfkl32g5ot6yMhXIlHXnnydudqrmD/B3RbPgXNAMcK679KRYv2eRv4Be4a7vkF++rOm4/Mo90e+d60Uoeusjclqt29IzNSlfPMQLidtMXdxu5w50sV2OurkodTJakqRzy2V1qlV0yt8cfz2fTufL5xKVXo6ukj44nV+DIK91UflCwnqa9mRrHjTCv1xRMzchHqJpfWutZ3waJXatdXaleQ+7RzU2TsY7otzJs/YOuazViOocxY/kaBO7muaW66bnr3OUR1+ZPNF6pu57rKgfJvt8RMa520XOtiule7dxdTv3iSt2jRNnn5ha9Txo3dTlatb8YZo2Zm5BdO7FDDeODHKjxGaeKCXpC5vf5hEnRoga6iYkKyDqX9Yhv1sm6lq5cbra24uYvLKedfPrmEkSzo3XWt8eu21v7ubo1g7WnVSuUTUplsmsFsmcpmmaTvP8WY1EPf1m5chdrj7nfmfTBjt3Md3dpiedG92EGYVpYa1B3AzlhuugKOzB7UhwVX10hkwDq6Pu6dEFqSKIIqrEZnHR6UncsW20HF+1HS3xt2OQu2Sce5nNSr6rD6IbuLjJw9HUDue6ywzfdHYTT7EW/C3xYzNVT2WmYgnkK/XRzOXqce79muYx7DO05myDXapS9+boDkzemULBlQXcbZ2nTBS61DWpMjTdlIzTPL2sbXRBqvxuu0Se6vpEYZctR5xbYoe39mjSql8yzvXuy4+0+J2q+2b2dvKWTQY70emFLTJfK1eZJHZQrp77pxfyl0tdhQdq2pc4V3ff4+PcTH0yuiy382qzZ+n4yYClCl2FNeNoM1ZVtYm2Pu4p4oK4FyHThGRAncEKNJry0h+p6X+6hstO5376oBzTVeO720dF0U29Z5wbOndzluugz51cPYc617tc+XHudzdt5LNi0Tu18qi74aKdK9xkczbjR+pJirvp3AgRym2OjqNrLtpii67C2uLEblUfW73ookV/qd48S2s+d8mNc3V/jjg0n6tu39fzab6oe3qoc/cOBqN6qpbpuYX85crOLdyxaR6Dn88VHVR8LhydIlyWvGPFLZpxgesm9xTXSjZIPrhuoLstgkdVFSVWzhWR8+1yr48I6xbUzKlf3aOPeZtB3GyW7HML289ziknFcG7w9Xya57n7Uau7zueG9TzyIVrqcn35fO6wpt11nHv8uQXXLzolukWjUElzrbuRBXa/BmTO3e3c3vz6dcgVaFOmR5yrc9oOZl/U7Ydsi+mK7vxDcsCb/U5EMbirPjtX0jUfJ7WxE523Eg88tzCf1yFdop5HlLutS3S5VDMfq2nKufm5rd7dakOQGTRZ8endMpRwk3u0ihYF6Uq0TXPrLMRXVsxeDfcUG8EtrqxMGdm9wm7RUZOb13kf+c8V1l23r/aOD1aOfg/t4LOse4vac3I5xpSBvrBNX3GJvrhpR8e5YnJAfBbc+7nEFX2XRqoqMzS9vMMXzYKSJ0bi01q3LwDuduXlqESrbx05Ki46ZOvwFegZAzu3u3h9NZPicvy7v3ey7p7Q5WAy/BxJFfQF7RkU8n5N4zduAEbC7y2ABucCjATnggbnAowE54IG5wKMBOeCBucCjATnggbnAowE54IG5wKMBOeC5uUNAADuBeNcgJG8Mc4FCc4FGAnOBQ3OBRgJzgUNzgUYCc4FDc4FGAnOBQ3OBRgJzgUNzgUYCc4FTda5XT+V37uEVNeJu3/Af0dxXeuy7K4G/CRwLmg61omIUtwTRRwbKlmWDb7jZ/yjejbLapaCc2FJO7f8iexqOZfb8rLV8hsdC/OY1cHs+uA7Fsj5CHPxg99xhYunZsA411Wk8JdY9SRyXBRn33oTuhruODoqK2o1/v1jyTh3u6pWuahiYau9WqzCuLs7gwfr4ZZVxrpNGs7Vg9Mqp93ucm5G0+4Qe4fgxASFLksUh2dhObjWer2oYkaL8RLrjsidEhsLMp7m2S7IGAY/vNbkH8Cw+Vw9XI0mJfSb9+bY0z0r2ZbF6F7XJ7oCDHKhpO3cYn3vT1YF9iwefgvnZitUaMecRxceD4Mj3SbD5nOb6nHHudHpSyzxqDL7TBeNvqvETFmoFpakc42KPtKqN+d6OrdYftw97r7lvx37qEQlyViv2yhRcKYXmoycz11iUS6x3fSkRNPdUa30yrL6xaPKJlqk/4kKwE9ll3M/FVgOgY+Oc8sP44z61uCbUly9fu5Uw/MgOM5t0vF8rpaIcK6YW4jCirKSzl1a2o1qXo1t3fq7Mwy62vCHcGg+tx7nHnPu8no+zRfXfIfHuVFwnNukY25hx9RBJoPwmluWVnnJ9Q2Xbr82uB6D60P4988k+9zC9iOsYh61dz63UdA8z474js7nhsGZz23SHucKxZS7Td2IgaSbM3JWcqR8RTjXBtEvJFFx7ksCwv1jyX4nopiNrR4XKJ5bqOlW2PaptG167rmF+byOVh3pOnPMKLdBam4hP7xdAukkrWT9pXdt8C7yrxO6PvnXAPjxHP0e2qO9IS/t3KobEwsZUnMLzfRy6FplW3aNFjOHmnMLGfSMgTskd1948s2Bn83x7/4+gK3KMXb4EZlzEsZNwG/cAIyE31sADc4FGAnOBQ3OBRgJzgUNzgUYCc4FDc4FGAnOBQ3OBRgJzgUNzgUYCc4FzcsbAADci/8Be0JddoTpY+8AAAAASUVORK5CYII=" alt="" />

通过邻接矩阵图表示的简易实现中,找到所有最小权边共需O(V)的运行时间。使用简单的二叉堆与邻接表来表示的话,普里姆算法的运行时间则可缩减为 O(ElogV),其中E为连通图的边数,V为顶点数。如果使用较为复杂的斐波那契堆,则可将运行时间进一步缩短为O(E+VlogV),这在连通图足够 密集时(当E满足Ω(VlogV)条件时),可较显著地提高运行速度。

3.代码实现:

 #include <stdio.h>
#define MAXV 100 //最大顶点个数
#define INF 32767 //INF表示∞
typedef struct
{ int edges[MAXV][MAXV];//邻接矩阵
int vexnum,arcnum; //顶点数,弧数
} MGraph;//图的邻接矩阵类型 void init(MGraph &g);//初始化邻接矩阵
void DispMat(MGraph g);//输出邻接矩阵g
void prim(MGraph g,int v);
int main()
{
int u=3;
MGraph g;//图的邻接矩阵
init(g);//初始化邻接矩阵
printf("图G的邻接矩阵:\n");
DispMat(g);
printf("\n");
printf("普里姆算法求解结果:\n");
prim(g,0);
printf("\n");
return 0;
} void prim(MGraph g,int v)//从v号节点开始---生成最小生成树
{
//(V-U)---未加入最小生成树的点
//U---已加入最小生成树的点
int i,j,k;
int MinCost[MAXV]; //(V-U)中各点离U的最小距离
int MinCostNum[MAXV];//(V-U)中各点离U的最小距离对应在U中的点
int min;//min记录离U最近的距离
MinCost[v]=0;//v加入U
for (i=0;i<g.vexnum;i++) //初始化MinCost[]和MinCostNum[]
{
MinCost[i]=g.edges[v][i];//每个节点距v的值
MinCostNum[i]=v;//(V-U)中的节点i距U中最近的点是v
}
for (i=1;i<g.vexnum;i++)
{
min=INF;
for (j=0;j<g.vexnum;j++)//在(V-U)中找出离U最近的顶点k
if (MinCost[j]!=0 && MinCost[j]<min) //未加入U(即V-U)中的点且距离U最近
{
min=MinCost[j];
k=j; //k记录离U最近的顶点
}
if(min!=INF)//(V-U)中离U最近点k--距U中最近的一个点是MinCostNum[k]
printf("边(%d,%d)权为:%d\n",MinCostNum[k],k,min);
MinCost[k]=0;//标记k已经加入U
//更新(V-U)中的点/////////////////////
for (j=0;j<g.vexnum;j++)//由于顶点k的新加入而修改数组lowcost和closest
if (MinCost[j]!=0 && g.edges[k][j]<MinCost[j])
{
MinCost[j]=g.edges[k][j];
MinCostNum[j]=k;
}
//经典之处///////////////////////////////////////
}
}
void init(MGraph &g)
{
int i,j;
g.vexnum=6;g.arcnum=10;
int A[MAXV][11];
for (i=0;i<g.vexnum;i++)
for (j=0;j<g.vexnum;j++)
A[i][j]=INF;
//数据结构书P189---图7.34
A[0][2]=1;A[0][4]=3;A[0][5]=7;
A[1][2]=9;
A[2][3]=2;
A[3][5]=4;
A[4][3]=6;A[4][5]=8;
/*for (i=0;i<g.vexnum;i++)//使邻接矩阵对称
for (j=0;j<g.vexnum;j++)
A[j][i]=A[i][j];*/
for (i=0;i<g.vexnum;i++)//建立邻接矩阵
for (j=0;j<g.vexnum;j++)
g.edges[i][j]=A[i][j]; }
void DispMat(MGraph g)//输出邻接矩阵g
{
int i,j;
for (i=0;i<g.vexnum;i++)
{
for (j=0;j<g.vexnum;j++)
if (g.edges[i][j]==INF)
printf("%3s","∞");
else
printf("%3d",g.edges[i][j]);
printf("\n");
}
}
/*
图G的邻接矩阵:
 ∞ ∞ 1 ∞ 3 5
 ∞ ∞  7 ∞ ∞ ∞
 ∞ ∞ ∞ 9 ∞ ∞
 ∞ ∞ ∞ ∞ ∞ 2
 ∞ ∞ ∞ 4 ∞ 6
 ∞ ∞ ∞ ∞ ∞ ∞
普里姆算法求解结果:
边(0,2)权为:1
边(0,4)权为:3
边(4,3)权为:6
边(3,5)权为:4
*/

最小生成二叉树-prim算法的更多相关文章

  1. 最小生成树问题(prim算法)POJ-1258 Agri-Net

    /* 这个题很水,但是,莫名其妙runtime error一晚上,重写了一遍就又没了,很伤心! 题意很简单,大致为n个村庄,连光缆,要求连上所有村庄的长度最短. 输入n,接着是n*n的矩阵,直接用pr ...

  2. 最小生成树(Kruskal和Prim算法)

    关于图的几个概念定义:          关于图的几个概念定义: 连通图:在无向图中,若任意两个顶点vi与vj都有路径相通,则称该无向图为连通图. 强连通图:在有向图中,若任意两个顶点vi与vj都有路 ...

  3. 最小生成树之Kruskal算法和Prim算法

    依据图的深度优先遍历和广度优先遍历,能够用最少的边连接全部的顶点,并且不会形成回路. 这样的连接全部顶点并且路径唯一的树型结构称为生成树或扩展树.实际中.希望产生的生成树的全部边的权值和最小,称之为最 ...

  4. 最小生成数kruskal算法和prim算法

    定义 连通图:在无向图中,若任意两个顶点vivi与vjvj都有路径相通,则称该无向图为连通图. 强连通图:在有向图中,若任意两个顶点vivi与vjvj都有路径相通,则称该有向图为强连通图. 连通网:在 ...

  5. 1&period;1&period;2最小生成树(Kruskal和Prim算法)

    部分内容摘自 勿在浮沙筑高台 http://blog.csdn.net/luoshixian099/article/details/51908175 关于图的几个概念定义: 连通图:在无向图中,若任意 ...

  6. 算法导论--最小生成树(Kruskal和Prim算法)

    转载出处:勿在浮沙筑高台http://blog.csdn.net/luoshixian099/article/details/51908175 关于图的几个概念定义: 连通图:在无向图中,若任意两个顶 ...

  7. Prim算法、Kruskal算法、Dijkstra算法

    无向加权图 1.生成树(minimum spanning trees) 图的生成树是它一棵含有所有顶点的无环联通子图 最小生成树:生成树中权值和最小的(所有边的权值之和) Prim算法.Kruskal ...

  8. Kruskal算法&amp&semi;Prim算法

    最小生成树是什么? Kruskal算法 图文转载自a2392008643的博客 此算法可以称为"加边法",初始最小生成树边数为0,每迭代一次就选择一条满足条件的最小代价边,加入到最 ...

  9. 最小生成树的两种方法(Kruskal算法和Prim算法)

    关于图的几个概念定义: 连通图:在无向图中,若任意两个顶点vivi与vjvj都有路径相通,则称该无向图为连通图. 强连通图:在有向图中,若任意两个顶点vivi与vjvj都有路径相通,则称该有向图为强连 ...

随机推荐

  1. IntellJ IDEA 所有快捷键

    登录下面网站. http://www.jetbrains.com/idea/documentation/ 下载Keymap for Windows/Linux 后面的PDF文档.

  2. ssh &amp&semi; display

    在Windows下用ssh连接服务器的话putty是一个小巧而且实用的工具,如果想要图形界面,可以使用X工具配合putty. 或者直接使用xmanager enterprise,非 常方便. 如果在U ...

  3. CSS预处理器实践之Sass、Less大比拼&lbrack;转&rsqb;

    什么是CSS预处理器? CSS可以让你做很多事情,但它毕竟是给浏览器认的东西,对开发者来说,Css缺乏很多特性,例如变量.常量以及一些编程语法,代码难易组织和维护.这时Css预处理器就应运而生了.Cs ...

  4. iOS 自定义 shareSDK 容器

    - (void)initializePlat { //添加新浪微博应用 [ShareSDK connectSinaWeiboWithAppKey:@"3201194191" app ...

  5. ASP&period;NET Core 行军记 -----第一步(艰辛的 MVC Hello World)

    现在ASP.NET Core还在不断成长.更新中,说不定到了明天又换了个模样,就如同一个小孩,从蹒跚学步,到奔向未来. 所以我们可以相应的去理解更新中所发生的变化,包容它.呵护它,而不是盲目的指责与批 ...

  6. Kernel 4&period;9的BBR拥塞控制算法。

    重要的事情说三遍! BBR并不能突破带宽限制!!! BBR并不能突破带宽限制!!! BBR并不能突破带宽限制!!! 它的功能如下: 1.在高丢包率与低速率的网络中提升传输效果,充分利用带宽. 2.降低 ...

  7. iOS swift的xcworkspace多项目管理(架构思想)

    iOS  swift的xcworkspace多项目管理(架构思想) 技术说明: 今天在这里分享 swift下的 xcworkspace多项目管理(架构思想),能为我们在开发中带来哪些便捷?能为我们对整 ...

  8. ASP&period;NET4&period;0所有网页指令

    ASP.NET网页指令(Page Directive)就是在网页开头的标签声明: <% Page Language="C#" %> 而指令的作用在于指定网页和用户控件编 ...

  9. jpa-规范

    看图

  10. 【windows核心编程】远程线程DLL注入

    15.1 DLL注入 目前公开的DLL注入技巧共有以下几种: 1.注入表注入 2.ComRes注入 3.APC注入 4.消息钩子注入 5.远线程注入 6.依赖可信进程注入 7.劫持进程创建注入 8.输 ...