最小生成树 普里姆算法和克鲁斯卡尔算法基本功能要求:①输入并存储至少8个顶点14条边的无向图.②分别编写普里姆算法和克鲁斯卡尔算法,求出最小生成树,输出最小生成树的生成过程.好
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/06 17:51:06
![最小生成树 普里姆算法和克鲁斯卡尔算法基本功能要求:①输入并存储至少8个顶点14条边的无向图.②分别编写普里姆算法和克鲁斯卡尔算法,求出最小生成树,输出最小生成树的生成过程.好](/uploads/image/z/6844503-39-3.jpg?t=%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91+%E6%99%AE%E9%87%8C%E5%A7%86%E7%AE%97%E6%B3%95%E5%92%8C%E5%85%8B%E9%B2%81%E6%96%AF%E5%8D%A1%E5%B0%94%E7%AE%97%E6%B3%95%E5%9F%BA%E6%9C%AC%E5%8A%9F%E8%83%BD%E8%A6%81%E6%B1%82%EF%BC%9A%E2%91%A0%E8%BE%93%E5%85%A5%E5%B9%B6%E5%AD%98%E5%82%A8%E8%87%B3%E5%B0%918%E4%B8%AA%E9%A1%B6%E7%82%B914%E6%9D%A1%E8%BE%B9%E7%9A%84%E6%97%A0%E5%90%91%E5%9B%BE.%E2%91%A1%E5%88%86%E5%88%AB%E7%BC%96%E5%86%99%E6%99%AE%E9%87%8C%E5%A7%86%E7%AE%97%E6%B3%95%E5%92%8C%E5%85%8B%E9%B2%81%E6%96%AF%E5%8D%A1%E5%B0%94%E7%AE%97%E6%B3%95%2C%E6%B1%82%E5%87%BA%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%2C%E8%BE%93%E5%87%BA%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%E7%9A%84%E7%94%9F%E6%88%90%E8%BF%87%E7%A8%8B.%E5%A5%BD)
最小生成树 普里姆算法和克鲁斯卡尔算法基本功能要求:①输入并存储至少8个顶点14条边的无向图.②分别编写普里姆算法和克鲁斯卡尔算法,求出最小生成树,输出最小生成树的生成过程.好
最小生成树 普里姆算法和克鲁斯卡尔算法
基本功能要求:
①输入并存储至少8个顶点14条边的无向图.
②分别编写普里姆算法和克鲁斯卡尔算法,求出最小生成树,输出最小生成树的生成过程.
好的有追分
我要源程序 代码 大牛们
最小生成树 普里姆算法和克鲁斯卡尔算法基本功能要求:①输入并存储至少8个顶点14条边的无向图.②分别编写普里姆算法和克鲁斯卡尔算法,求出最小生成树,输出最小生成树的生成过程.好
kruskal算法的时间复杂度主要由排序方法决定,其排序算法只与带权边的个数有关,与图中顶点的个数无关,当使用时间复杂度为O(eloge)的排序算法时,克鲁斯卡算法的时间复杂度即为O(eloge),因此当带权图的顶点个数较多而边的条数较少时,使用克鲁斯卡尔算法构造最小生成树效果最好!
克鲁斯卡尔算法
假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的过程为:先构造一个只含 n 个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有 n 棵树的一个森林.之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之.依次类推,直至森林中只有一棵树,也即子图中含有 n-1条边为止.
普里姆算法
假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,TV 是 WN 上最小生成树中顶点的集合,TE 是最小生成树中边的集合.显然,在算法执行结束时,TV=V,而 TE 是 E 的一个子集.在算法开始执行时,TE 为空集,TV 中只有一个顶点,因此,按普里姆算法构造最小生成树的过程为:在所有“其一个顶点已经落在生成树上,而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边,逐条加在生成树上,直至生成树中含有 n-1条边为止.
1.Kruskal
#include
#include
#include
using namespace std;
struct node
{
int v1;
int v2;
int len;
}e[10000];//定义边集
int cmp(const void *a,const void *b)//快排比较函数
{
return ((node*)a)->len-((node*)b)->len;
}
int v[100],a[100][100];//v为点集
void makeset(int n)
{
for(int i=0;i