使用prim算法求最小生成树
要求如下：
从键盘上输入无向带权图的各顶点和边上的权值，要求完成：1）以邻接表存储图的边信息；2）输出该图的各顶点及邻接表；3）计算各顶点的度；4）使用Prim算法求出该图的最小生成树。
[解决办法]
随便一本数据结构的书上都有！
最好用邻接矩阵作为存储结构
比较方便
#include <iostream>
#include <algorithm>
using namespace std;
#define BUFSIZE 555
#define ULTIMATE 2000000000
struct Node{
int parent;
int key;
}node[BUFSIZE];
int N,M;
int Graph[BUFSIZE][BUFSIZE];
void init()
{
fill_n(&Graph[0][0],BUFSIZE*BUFSIZE,ULTIMATE);
scanf( "%d%d ",&N,&M);
for(int i=1;i <=M;i++){
int s,d,v;
scanf( "%d%d%d ",&s,&d,&v);
Graph[s][d] = v;
Graph[d][s] = v;
}
}
bool comp(Node a,Node b)
{
if(a.key){
if(b.key)
return a.key <=b.key;
else return true;
}
return false;
}
void prim()
{
SUM = 0;
for(int j=1;j <N;j++){
node[j].parent = N;
node[j].key = Graph[N][j];
}
node[N].key = 0;
for(int i=1;i <N;i++){
Node *p = min_element(node+1,node+1+N,comp);
int k = p - node;
p-> key = 0; //表示点p已经加入了生成树的集合。
for(int j=1;j <N;j++)
if(Graph[k][j] <node[j].key){
node[j].parent = k;
node[j].key = Graph[k][j];
}
}
}
[解决办法]
好像我另外一块硬盘上有写过，还经过测试的，给我发email我如果还在 就给你发过去pkurao@126.om
[解决办法]
我在vs2005下写了一个,经过测试完全满足你的要求.
一共两个project : 一个Graph 还有一个UnDiGraph.
其中Graph project下有3个文件Edge.h, Vertex.h, Graph.h.里面分别是 边类,顶点类和图类.
而UnDiGraph project下只有一个文件夹UnDiGraph.h,里面是UnDiGraph类的定义.
其中 类UnDiGraph 继承自 类Graph.
我是用模板写的,由于编译器不支持类模板的分离编译,所以除了main所在的文件以外,没有.cpp文件.全放在了.h文件中实现.
另外,输入输出我都截图了,可惜发现无法发上来.
