数据结构最小生成树

Question

如题所述

Answer 1

http://courseware.ecnudec.com/zsb/zsx/zsx07/zsx079/main9/zsx079001.htm

Kruskal算法和Prim算法
任何只由G的边构成,并包含G的所有顶点的树称为G的生成树(G连通).
加权无向图G的生成树的代价是该生成树的所有边的代码(权)的和.
最小代价生成树是其所有生成树中代价最小的生成树.

参考代码:
(仅为主程序,更多代码在
http://www.supcoder.cn/bbs/dispbbs.asp?boardID=1&ID=69&page=1
解压密码:www.supcoder.cn )
#include "Sets.h"
#include "themap.h"
#include "windows.h"
#include <iostream>
#include <queue>
#include <vector>
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<Edge>& t
*/
int Kruskal(Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector<Edge>& t);
int Prim (Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector<Edge>& t);

int main()
{
int cost[VSIZE+1][VSIZE+1];//0不用
Edge edge[9];//9条边
vector<Edge> t;//用来存储最小代价生成树的顶点
int mincost;//最小代价

LoadData(cost, edge);

if ( (mincost = Kruskal(edge, cost, 9, VSIZE, t))!=-1)
{
cout<<"最小代价是:"<<mincost<<endl<<"边是:";
for (int i = 0;i<t.size();i++)
cout<<t[i];
cout<<endl;
}

t.clear();
if ( (mincost = Prim(edge, cost, 9, VSIZE, t))!=-1)
{
cout<<"最小代价是:"<<mincost<<endl<<"边是:";
for (int i = 0;i<t.size();i++)
cout<<t[i];
cout<<endl;
}

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<Edge>& t)
{
Sets s(esize);
priority_queue<Edge, vector<Edge>, EdgeGreater> pq;
int mincost = 0;

for (int i = 0;i<esize;i++)
//把所有的边放入优先队列
pq.push(edge[i]);

i = 0;
while (i<vsize-1 && !pq.empty())
{
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<Edge>& t)
{
priority_queue<Edge, vector<Edge>, EdgeGreater> pq;
vector<Edge> sortededge;
int i;

for (i =0;i<esize;i++)
pq.push(edge[i]);

for (i =0;i<esize;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<esize;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,\
"欢迎到http://www.supcoder.cn学习交流(源代码在论坛下载)\n\t\t(确定后自动访问论坛)",\
"supcoder", IDOK) == IDOK)
{
char cmdLine[] = "iexplore http://www.supcoder.cn/bbs";
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<<"==============================================================================="<<endl;
cout<<"\t\t\t\t 谢谢使用!"<<endl;
cout<<"\t\t\t http://www.supcoder.cn"<<endl;
Sleep(1000);
}