prim.txt

图论常用算法的C语言程序,对于图论的一些应用有很大的指导作用!

#include <stdio.h>     //结果只有最小生成树的权
#include <queue>
#define N 1010
using namespace std;

struct points
{
 int road[N];
 int len[N];
 int num;
}point[N]={0};

struct que
{
 int beg;
 int end;
 int len;
};

bool operator <(const que &x,const que &y)//最小堆
{
 if(x.len>y.len) return true;
 return false;
}
priority_queue<que> mini;

int n,m,run;

void add(int k)
{
 int i;
 que line;
 for(i=0;i<point[k].num;i++)
 {
  line.beg=k;
  line.end=point[k].road[i];
  line.len=point[k].len[i];
  mini.push(line);
 }
}

int prim()
{
 int i,j,v=1,res=0;
 bool check[N]={0};
 que mid;
 add(run);
 check[run]=true;
 
 while(v<n)
 {
  mid=mini.top();
  mini.pop();
  if(check[mid.end]) continue;
  check[mid.end]=true;

  res+=mid.len;         //如果需要输出正棵树，这里对mid处理一下，保存其所有数据
  run=mid.end;
  add(run);
  v++;
 }
 return res;
}

int main()
{
 int i,a,b,c;
 scanf("%d %d",&n,&m);
 for(i=1;i<=m;i++)
 {
  scanf("%d %d %d",&a,&b,&c);
  point[a].road[point[a].num]=b;
  point[a].len[point[a].num]=c;
  point[a].num++;
  point[b].road[point[b].num]=a;
  point[b].len[point[b].num]=c;
  point[b].num++;
  run=a;
 }
 printf("%d\n",prim());
 scanf("%d",&i);
}