// Kruskal算法实现.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
#define MAX 100
typedef int WeiType;
using namespace std;
//
struct Edge
{
int no; //边的序号
int x; //端点1序号
int y; // 端点2序号
WeiType weight; //权值
bool selected; //是否被选择
};
//边集和
Edge edge[MAX];
//已找到的最小生成树其中一部分的秩
int rank[MAX];
//已找到的最小生成树其中一部分的头结点
//用来判断一条边的2个端点是否在一个集合中,即加上这条边是否会形成回路
int parent[MAX];
//找出每一集合的头结点
int find_set(int x)
{
if(x != parent[x] )
parent[x] = find_set(parent[x]);
return parent[x];
}
//合并集合
void union_set(int x,int y,WeiType w,WeiType &sum)
{
if(x==y)
return;
if(rank[x]>rank[y])
parent[y]=x;
else
{
if(rank[x]==rank[y])
rank[y]++;
parent[x]=y;
}
sum +=w;
}
//依据边的权值升序快速排序
void fast_sort(Edge *edge,int begin,int end)
{
if(begin<end)
{
int i = begin-1,j=begin;
edge[0] = edge[end];
while(j<end)
{
if(edge[j].weight<edge[0].weight)
{
i++;
Edge temp1 = edge[i];
edge[i] = edge[j];
edge[j] = temp1;
}
j++;
}
Edge temp2 = edge[end];
edge[end] = edge[i+1];
edge[i+1] = temp2;
fast_sort(edge,begin,i);
fast_sort(edge,i+2,end);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int cases;
cout<<"请输入案例的个数:";
cin>>cases;
while(cases--)
{
int n;
//最小生成树的权值总和
WeiType sum = 0;
cout<<"请输入边的个数:";
cin>>n;
int i;
//初始化
char chx,chy;
WeiType weight;
for(i=1;i<=n;i++)
{
edge[i].no = i;
cout<<"请输入第"<<i<<"条边的二个端点的名称(小写字符):";
cin>>chx>>chy;
edge[i].x = chx-'a'+1;
edge[i].y = chy-'a'+1;
cout<<"这条边的权值为:";
cin>>weight;
edge[i].weight = weight;
edge[i].selected = false;
parent[edge[i].x] = edge[i].x;
parent[edge[i].y] = edge[i].y;
rank[edge[i].x] = 0;
rank[edge[i].y] = 0;
}
//快排
fast_sort(edge,1,n);
for(i=1;i<=n;i++)
{
int x,y;
x = find_set(edge[i].x);
y = find_set(edge[i].y);
//判断即加上这条边是否会形成回路
if(x != y )
{
//选择这条边
edge[i].selected = true;
//合并不会形成回路的二个集合
union_set(x,y,edge[i].weight,sum);
}
}
cout<<"最小生成树的边集为:"<<endl;
for(i=1;i<=n;i++)
{
if(edge[i].selected)
{
cout<<"序号:"<<edge[i].no<<" " <<"端点1:"<<(char)(edge[i].x+'a'-1)<<",端点2:"<<(char)(edge[i].y+'a'-1)<<endl;
}
}
cout<<"最小生成树的权值为:"<<sum<<endl;
}
system("pause");
return 0;
}
-------------------------------------------程序测试-------------------------------------------
请输入案例的个数:1
请输入边的个数:14
请输入第1条边的二个端点的名称(小写字符):a b
这条边的权值为:4
请输入第2条边的二个端点的名称(小写字符):a h
这条边的权值为:8
请输入第3条边的二个端点的名称(小写字符):b c
这条边的权值为:8
请输入第4条边的二个端点的名称(小写字符):b h
这条边的权值为:11
请输入第5条边的二个端点的名称(小写字符):c d
这条边的权值为:7
请输入第6条边的二个端点的名称(小写字符):c f
这条边的权值为:4
请输入第7条边的二个端点的名称(小写字符):c i
这条边的权值为:2
请输入第8条边的二个端点的名称(小写字符):d e
这条边的权值为:9
请输入第9条边的二个端点的名称(小写字符):d f
这条边的权值为:14
请输入第10条边的二个端点的名称(小写字符):e f
这条边的权值为:10
请输入第11条边的二个端点的名称(小写字符):f g
这条边的权值为:2
请输入第12条边的二个端点的名称(小写字符):g h
这条边的权值为:1
请输入第13条边的二个端点的名称(小写字符):g i
这条边的权值为:6
请输入第14条边的二个端点的名称(小写字符):h i
这条边的权值为:7
最小生成树的边集为:
序号:12 端点1:g,端点2:h
序号:11 端点1:f,端点2:g
序号:7 端点1:c,端点2:i
序号:1 端点1:a,端点2:b
序号:6 端点1:c,端点2:f
序号:5 端点1:c,端点2:d
序号:3 端点1:b,端点2:c
序号:8 端点1:d,端点2:e
最小生成树的权值为:37
请按任意键继续. . .
分享到:
相关推荐
编写算法能够建立带权图,并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。
( 最小生成树Kruskal算法(C++).pdf
实现了kruskal的算法,测试可行。
c++实现最小生成树Kruskal算法,课程作业,供大家参考~~
最小生成树的kruskal算法(c++源码)
(1)、实验题目:给定一个地区的n 个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并得到的最小生成树的代价。 (2)、实验要求: 1、城市间的距离网采用的邻接矩阵表示,邻接矩阵的存储结构定义采用...
图的深度优先搜索,广度优先搜索,最小生成树算法,包括kruskal、prim算法的代码,以及详细的注释。深度优先应用递归、广度优先搜索利用队列、kruskal利用STL中的关联容器set、prim算法利用二叉堆结构进行优化。
分别利用prim算法和kruskal算法实现求图的最小生成树 C++描述
C++语言程序 最小代价生成树(kruskal算法) 含代码解释
洛谷原模板题p3366 题目网址: https://www.luogu.com.cn/problem/P3366
prim用c++实现的最小生成树的源码,easy to understand!
//最小生成树的kruskal的算法 #include "stdafx.h" #include #include #include using namespace std; //int maxint=mar_maxint; class BinaryTree; class EdgeNode//边的数据结构 { private: int u,v;//边所在的...
win32控制台程序 vs2010以上编译运行通过 在main函数里定义图,然后调用2个封好的函数用2种不同的算法输出最小生成树 大连理工大学软件学院数据结构上机题
最小生成树(Prim,Kruskal)C++代码实现 (可运行,含测试用例,有输出,注释详细) 对于一个带权连通图,生成树不同,树中各边上权值总和也不同,权值总和最小的生成树则称为图的最小生成树。
Kruskal算法 1.首先将G的n个顶点看成n个孤立的连通分支,将所有的边按权从小到大排序e1,e2,e3...em 2.从第一条边开始,依边权递增的顺序查看每一条边,并按下述方法连接...此时,这个连通分支就是G的一颗最小生成树了
数据结构实验做的图的最小生成树算法,C++实现的Kruskal算法
基于Union-Find数据结构实现Kruskal求最小生成树,代码设计及变量命名附详细注释。基于Union-Find数据结构实现Kruskal求最小生成树,代码设计及变量命名附详细注释。
—————————最小... (1)利用克鲁斯卡尔算法求网的最小生成树。 (2)实现教科书6.5节中定义的抽象树类型 MFSet。以此表示构造生成树过程中的连通分量。 (3)以文本形式输出生成树中各条边以及他们的权值。
所以Kruskal算法的第一步是给所有的边按照从小到大的顺序排序。这一步可以直接使用库函数qsort或者sort。接下来从小到大依次考察每一条边(u,v)。 具体实现过程如下: <1> 设一个有n个顶点的连通网络为G(V,E)...