大家好，又见面了，我是全栈君。
记录用来复习。
—————————————————————-
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
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116421.html原文链接：https://javaforall.net
