//无向图最小生成树,prim算法+映射二分堆,邻接表形式,复杂度O(mlogn)
//返回最小生成树的长度,传入图的大小n和邻接表list
//可更改边权的类型,pre[]返回树的构造,用父结点表示,根节点(第一个)pre值为-1
//必须保证图的连通的!
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;
#define MAXN 200
#define inf 1000000000
typedef double elem_t;
struct edge_t{
int from,to;
elem_t len;
edge_t* next;
};
#define _cp(a,b)((a)<(b))
struct heap{
elem_t h[MAXN+1];
int ind[MAXN+1],map[MAXN+1],n,p,c;
void init(){n=0;}
void ins(int i,elem_t e){
//插入第i个数到堆中
for(p=++n;p>1&&_cp(e,h[p>>1]);h[map[ind[p]=ind[p>>1]]=p]=h[p>>1],p>>=1);
h[map[ind[p]=i]=p]=e;
}
//从堆中删除第i个数
int del(int i,elem_t& e){
i=map[i];if(i<1||i>n) return 0;
for(e=h[p=i];p>1;h[map[ind[p]=ind[p>>1]]=p]=h[p>>1],p>>=1);
for(c=2;c<n&&_cp(h[c+=(c<n-1&&_cp(h[c+1],h[c]))],h[n]);h[map[ind[p]=ind[c]]=p]=h[c],p=c,c<<=1);
h[map[ind[p]=ind[n]]=p]=h[n];n--;return1;
}
//从堆中删除最小的数,并返回改最小值的原始下标i
int delmin(int&i,elem_t& e){
if (n<1) return0;i=ind[1];
for(e=h[p=1],c=2;c<n&&_cp(h[c+=(c<n-1&&_cp(h[c+1],h[c]))],h[n]);h[map[ind[p]=ind[c]]=p]=h[c],p=c,c<<=1);
h[map[ind[p]=ind[n]]=p]=h[n];n--;return1;
}
};
elem_t prim(int n,edge_t list[],int*pre){
heap h;
elem_t min[MAXN],ret=0,e;
edge_t* t;
int v[MAXN],i;
for (h.init(),i=0;i<n;i++)
min[i]=(i?inf:0),v[i]=0,pre[i]=-1,h.ins(i,min[i]);
while (h.delmin(i,e))
for(v[i]=1,ret+=e,t=list[i].next;t;t=t->next)
if(!v[t->to]&&t->len<min[t->to])
pre[t->to]=t->from,h.del(t->to,e),h.ins(t->to,min[t->to]=t->len);
return ret;
}
//初始化连接表
void Init(edge_t list[],int n)
{
int i;
for (i = 0; i < n; i ++)
list[i].next = NULL;
}
edge_t* FindEnd(edge_t* list)
{
edge_t* p = list;
while(p &&p->next != NULL)
p =p->next;
return p;
}
void CreateLink(edge_t list[],int m,int n)
{
edge_t* end;
edge_t* p;
Init(list,n);
int i,x,y,z;
for (i = 0; i < m; i ++)
{
scanf("%d%d%d",&x,&y,&z);
end =FindEnd(list[x].next);//查找链表的最后一个节点
p =(edge_t*)malloc(sizeof(edge_t));
p->from =x;
p->to = y;
p->len =z;
p->next =NULL;
if (!end)
list[x].next= p;
else
end->next= p;
end =FindEnd(list[y].next);//查找链表的最后一个节点
p =(edge_t*)malloc(sizeof(edge_t));
p->from =y;
p->to = x;
p->len =z;
p->next =NULL;
if (!end)
list[y].next= p;
else
end->next= p;
}
}
int main(void)
{
clock_t start,finish;
start = clock();
freopen("最小生成树(kruskal邻接表形式).txt","r",stdin);
edge_t list[MAXN];
int pre[MAXN];
int n,m,i;
scanf("%d%d",&n,&m);
CreateLink(list,m,n);
double ans = prim(n,list,pre);
cout << ans<< endl;
for (i = 1; i < n; i ++)
cout<< pre[i]<< "---"<< i <<endl;
finish = clock();
cout << (finish -start) / CLOCKS_PER_SEC << "ms"<< endl;
return 0;
}
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。