作业帮最小生成树的定义以及有关算法请给出定义与有关算法的名字（给名字即可,有具体代码更佳）
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/25 10:23:09
最小生成树的定义以及有关算法请给出定义与有关算法的名字（给名字即可,有具体代码更佳）
最小生成树的定义以及有关算法
请给出定义
与有关算法的名字（给名字即可,有具体代码更佳）
最小生成树的定义以及有关算法请给出定义与有关算法的名字（给名字即可,有具体代码更佳）
Kruskal算法和Prim算法
任何只由G的边构成,并包含G的所有顶点的树称为G的生成树(G连通).
加权无向图G的生成树的代价是该生成树的所有边的代码(权)的和.
最小代价生成树是其所有生成树中代价最小的生成树.
参考代码:
(仅为主程序,更多代码在
解压密码:www.supcoder.cn )
#include "Sets.h"
#include "themap.h"
#include "windows.h"
#include
#include
#include
using namespace std;
/*
功能:
演示Kruskal算法和Prim算法
集合的并,元素查找的操作及应用
说明:
代码均在vc++6.0环境下编译均通过
在非VC++6.0环境下编译请去掉头文件 windows.h 和函数 end()
如果NULL未定义请自定义
#define NULL 0 或
#define NULL ((void*)0)
作者:
baihacker
时间:
2007.2.3
*/
const VSIZE = 7;//7个顶点
const INFINITY = 10000;//10000作为无穷大来处理
void LoadData(int cost[][VSIZE+1],Edge edge[]);
void end();
/*
函数名:
Kruskal 和 Prim
参数:
边,代价,边数,顶点数,最小代价生成树的顶点
返回值:
返回值为-1,不存在最小代价生成树
返回值大于0时为最小代价生成树的代价
最小代价生成树的边在vector& t
*/
int Kruskal(Edge edge[],int cost[][VSIZE+1],int esize,int vsize,vector& t);
int Prim (Edge edge[],int cost[][VSIZE+1],int esize,int vsize,vector& t);
int main()
{
int cost[VSIZE+1][VSIZE+1];//0不用
Edge edge[9];//9条边
vector t;//用来存储最小代价生成树的顶点
int mincost;//最小代价
LoadData(cost,edge);
if ( (mincost = Kruskal(edge,cost,9,VSIZE,t))!=-1)
{
cout