最小生成树「建议收藏」

记录用来复习。

—————————————————————-

PRIMER

总体思路：和Dijstrak差点儿相同，都是用了简单的贪心策略，每次挑选距离生成树距离近期的没被合并进来的点作为吸收对象。

仅仅是primer在松弛那一步上把距离的更新作为总体距离的更新而Dijstrak则是单原点的距离更新！！。

// primer.cpp : 定义控制台应用程序的入口点。
//#include "stdafx.h"#include"iostream"#include"vector"#include"algorithm"#include"queue"#include"math.h"#include"string"#include"memory.h"using namespace std;#define max 100#define inf 9999int dis[max][max]={inf};int visited[max]={0};int n=0;//和dijstrak算法一样。仅仅是角度不一样。int primer(int s){	int sum=0;	visited[s]=1;	for(int k=0;k<n;k++)	{//initial!!!		int min=inf;		int mark=-1;		for(int i=0;i<n;i++)		{ //find min			if(visited[i]==0&&dis[s][i]<min)			{				min=dis[s][i];				mark=i;			}		}	    if(mark==-1) break;					//visited		visited[mark]=1;		sum+=dis[s][mark];//多了一步统计		for(int j=0;j<n;j++)		{//updata			if(visited[j]==0&&dis[s][j]>dis[mark][j])//把dis[s][j]看成是总体到其它各点的距离！！！
这里和djs不同.				dis[s][j]=dis[mark][j];		}	}	return sum;}int main(){ 	int e=0;	cin>>n>>e;	int tempa=0,tempb=0,value;	for(int i=0;i<100;i++)		for(int j=0;j<100;j++)			dis[i][j]=inf;	for(int i=0;i<e;i++)	{   //无向		cin>>tempa>>tempb>>value;		tempa--;		tempb--;		dis[tempa][tempb]=value;		dis[tempb][tempa]=value;	}	cout<<primer(0)<<endl;	return 0;}

KRUSKAL

kruskal的思路也是贪心。

可是和上面的primer不同，kruskal主要针对边的权大小来选择吸收的点。

简单来讲能够分成下面3步：

【1】依据边的权值大小来排序。

【2】检測候选边的端点是否来自同一集合。

【3】合并点。更新并查集。

// kruskal.cpp : 定义控制台应用程序的入口点。
//#include "stdafx.h"#include"iostream"#include"algorithm"#include"vector"#include"string"#include"memory.h"#include"stdlib.h"#include"queue"using namespace std;#define max 100int node[max]={0};int e=0;class road{public:	int a;	int b;	int value;};vector<road*> roads;bool cmp(road* r1,road* r2){	return r1->value<r2->value;}int find_set(int n){   if(node[n]==-1)	   return n;   find_set(node[n]);}int  merge(int a,int b){     if(a==b)	    return 0;	 else if(a>b)	    node[a]=b;	 else if(a<b)		 node[b]=a;	 return 1;}int  kruskal(){   //sort edges	sort(roads.begin(),roads.end(),cmp);	int sum=0;	for(int i=0;i<e;i++)	{		//find set		int a=find_set(roads[i]->a);		int b=find_set(roads[i]->b);		//merge		if(merge(a,b))//-1 is true!!			sum+=roads[i]->value;	}	return sum;}int main(){  	memset(node,-1,sizeof(node));	cin>>e;	int a=0,b=0,value=0;	for(int i=0;i<e;i++)	{	  cin>>a>>b>>value;	  road *r=new road;	  r->a=a;	  r->b=b;	  r->value=value;	  roads.push_back(r);	}	int sum=kruskal();	cout<<sum<<endl;	return 0;}

測试数据：

9
14
1 2 4
1 8 8
2 3 8
2 8 11
3 4 7
3 6 4
3 9 2
4 5 9
4 6 14
5 6 10
6 7 2
7 8 1
7 9 6
8 9 7

out:37