边构成,并包含G的所有顶点的树称为G的生成树(G连通).
加权无向图G的生成树的代价是该生成树的所有边的代码(权)的和.
最小代价生成树是其所有生成树中代价最小的生成树.
参考代码:
(仅为主程序,更多代码在
解压密码: )
#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< for (int i = 0;i
cout<
cout<
}
t.clear();
if ( (mincost = Prim(edge, cost, 9, VSIZE, t))!=-1)
{
cout< for (int i = 0;i
cout<
cout<
}
end();
return 1;
}
void LoadData(int cost[][VSIZE+1], Edge edge[])
{
edge[0].u = 1; edge[0].v = 2; edge[0].weight = 28;
edge[1].u = 1; edge[1].v = 6; edge[1].weight = 10;
edge[2].u = 2; edge[2].v = 3; edge[2].weight = 16;
edge[3].u = 2; edge[3].v = 7; edge[3].weight = 14;
edge[4].u = 3; edge[4].v = 4; edge[4].weight = 12;
edge[5].u = 4; edge[5].v = 5; edge[5].weight = 22;
edge[6].u = 4; edge[6].v = 7; edge[6].weight = 18;
edge[7].u = 5; edge[7].v = 6; edge[7].weight = 25;
edge[8].u = 5; edge[8].v = 7; edge[8].weight = 24;
for (int i=1;i<=7;i++)
for (int j=1;j<=i;j++)
cost[i][j] = cost[j][i] = INFINITY;
for (i=0;i<9;i++)
cost[edge[i].u][edge[i].v] =
cost[edge[i].v][edge[i].u] = edge[i].weight;
}
int Kruskal(Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector
& t)
{
Sets s(esize);
priority_queue
, EdgeGreater> pq;
int mincost = 0;
for (int i = 0;i
//把所有的边放入优先队列
pq.push(edge[i]);
i = 0;
while (i
{
Edge temp = pq.top();//取出当前权最小的边
pq.pop();
int j = s.SimpleFind(temp.u);
int k = s.SimpleFind(temp.v);
if (j!=k)//如果不构成环
{
i++;
t.push_back(temp);
mincost +=cost[temp.u][temp.v];
s.SimpleUnion(j, k);
}
}
if (i!=vsize-1)
{
t.clear();
return -1;
}
else
{
return mincost;
}
}
int Prim(Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector
& t)
{
priority_queue
, EdgeGreater> pq;
vector
sortededge;
int i;
for (i =0;i
pq.push(edge[i]);
for (i =0;i
{//对边进行从小到大排列,放到sortededge中
sortededge.push_back(pq.top());
pq.pop();
}
int distance[VSIZE+1];
int j;
int mincost = sortededge[0].weight;
Edge temp = sortededge[0];
t.push_back(temp);
for (i=1;i<=vsize;i++)
distance[i] = 1;//每个点都不在已生成树里
distance[temp.u] = distance[temp.v] = 0;//最短的边的两个点放到生成树里
for (i=2;i<=vsize-1;i++)
{//寻找另外的边
int exist = 0;//设置是否找到符合条件的边的状态标志为未找到
for (j=1;j
if (distance[sortededge[j].u] ^ distance[sortededge[j].v] == 1)
{//由于边是排序好了的,所以从小边向大边找,找到的第一个符合条件的边可以
//加到生成树里
int k = (distance[sortededge[j].u] == 0) ? sortededge[j].v :
sortededge[j].u;
distance[k] = 0;
mincost += sortededge[j].weight;
t.push_back(sortededge[j]);
exist = 1;
break;
}
if (!exist)
{
t.clear();
return -1;
}
}
return mincost;
}
void end()
{
if (MessageBox(NULL,
"欢迎到学习交流(源代码在论坛下载)ntt(确定后自动访问论坛)",
"supcoder", IDOK) == IDOK)
{
char cmdLine[] = "iexplore ";
char path[256];
char buf[256];
STARTUPINFO si;
ZeroMemory(&si, sizeof(si));
PROCESS_INFORMATION ProcessInformation;
GetSystemDirectory(buf, 256);
sprintf(path, "%c:\Program Files\Internet Explorer\IEXPLORE.EXE", buf[0]);
CreateProcess(path,cmdLine, NULL, NULL, 1, 0, NULL, NULL, &si, &ProcessInformation);
}
cout< cout< cout< Sleep(1000);
}