圖 克魯斯卡爾 Kruskal 算法生成最小生成樹

基于尚硅谷的韓老師java數(shù)據(jù)結(jié)構(gòu)課程。
本算法人為理解并不難，其實就是把所有的邊按照權(quán)值進行由小到大的排序，
在把排序后的結(jié)果由小到大加起來，每加一次，進行回路判斷。
如果沒有回路就加，有回路就跳過，進行下一條邊。
我們把主要的回路判斷算法放在此處。

getEnds(int[],int)

int getEnds(int ends[],int i){
	while(ends[i]!=0){
		i=ends[i];
	}
	return i;
}

韓老師說，兩個結(jié)點的終點不能一致，這里如何理解終點？
就是開始生成最小生成樹的時候，沒加一條邊，都會有兩個頂點，其中每一個的頂點會對應(yīng)一個終點。
從最小的邊開始加的時候，兩個頂點的終點都是"0"，對應(yīng)的我們需要初始化一個全是0的數(shù)組ends[g->edges]，長度為邊數(shù)，讓每一個邊的終點此時的”終點“都對應(yīng)為 0，
在我們每進行一次加邊的操作，我們再對這個數(shù)組進行更新。

Kruskal(Graph ,Edges )

void Kruskal(Graph g,Edges e){
	int index=0;
	int ends[g->edge]={0};//保存最小生成樹中每個頂點的終點 

	//1.創(chuàng)建結(jié)果數(shù)組 ，保存最終的最小生成樹 Res 為Result的縮寫 
	Edges edgeRes =(Edges) malloc(g->edge*sizeof(struct Edge));
	
	//2.按照邊的權(quán)值大小排序，我已經(jīng)在main里排序過了
	
	//3.遍歷edges數(shù)組從最小邊開始加，加一次判回路一次，沒回路就加進來（edgeRes），有回路就換下一條
	
	 for(int i =0;i<g->edge;i++) {
	 	//拿到第i條邊的頂點的下標start 
		int p1= getIndex(g,e[i].start);
		//拿到第i條邊的頂點的下標start 
		int p2= getIndex(g,e[i].end);
		cout<<"p1 "<<p1<<"p2 "<<p2<<endl;
		
		//獲取p1頂點的在已有的最小生成樹中終點是？
		int m =getEnds(ends,p1);
		//獲取p2頂點的在已有的最小生成樹中終點是？
		int n =getEnds(ends,p2);
		cout<<"m "<<m<<"n "<<n<<endl;
		for(int j=0;j<g->edge;j++)
		cout<<ends[i];
		cout<<endl;
		//是否構(gòu)成回路
		if(m!=n) {//不構(gòu)成回路 
			ends[m] =n; //設(shè)置m 在已有最小生成樹的終點 
			edgeRes[index++]=e[i];
					}
	 }
	 //統(tǒng)計并打印最小生成樹
	  for(int i =0;i<index;i++){
	  	cout<<" "<<edgeRes[i].start<<" "<<edgeRes[i].end<<" "<<edgeRes[i].weight<<endl;
	  }	
}

main()

int main(){
	int n;
	cin>>n;
	Graph graph=Create();
	Edges edges;
	edges=( Edges)malloc((n*(n-1)/2)*sizeof(struct Edge));
	for(int i=0;i<n;i++){
		char e;cin>>e;
		addVex(graph,e);
	}
		
	E v1,v2;int w;
	while(cin>>v1>>v2){
		cin>>w;
		addEdge(graph,v1,v2,w,edges);
	}

	cout<<"第一次"<<endl;
	printMatrix(graph,edges);
	qsort(edges,graph->edge, sizeof(Edge), cmp);
	cout<<"庫魯斯卡爾："<<endl; 
	Kruskal(graph,edges);
	cout<<"排序后"<<endl;
	printMatrix(graph,edges);
	
}

整體

  #include<iostream> 
#define MAX 10
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
using namespace std;
typedef char E;
typedef struct Edge{
	E start;
	E end;
	int weight;
}*Edges;
typedef struct GraphMatrix{
	int vex,edge;
	int matrix[MAX][MAX];
	E data[MAX];
}*Graph;

Graph Create(){
	Graph g = (Graph)malloc(sizeof(GraphMatrix));
	g->vex=g->edge=0;
	memset(g->matrix,0,sizeof(g->matrix));
	return g;
}
void addVex(Graph g,E e){
	g->data[g->vex++]=e;
	
}
int getIndex(Graph g,E e){
	for(int i=0;i<g->vex;i++)
		if(g->data[i]==e)
			return i;
	return -1;
}
void addEdge(Graph g,E v1,E v2,int w,Edges e){
	int a=getIndex(g,v1);
	int b=getIndex(g,v2);
	g->matrix[a][b]=w;
	g->matrix[b][a]=w;
	
	e[g->edge].start=v1;
	e[g->edge].end=v2;
	e[g->edge].weight=w;

	g->edge++;
}
printMatrix(Graph g,struct Edge e[]){
	for(int i=0;i<g->vex;i++)
	{
		for(int j=0;j<g->vex;j++)
		 cout<<"\t"<<g->matrix[i][j];
		cout<<endl;
	}
	for(int i=0;i<g->edge;i++)
	 cout<<" "<<e[i].start<<" "<<e[i].end<<" "<<e[i].weight<<endl;
}
void Kruscal(Graph g){
	int vLen=g->vex;
}
int getEnds(int ends[],int i){
	while(ends[i]!=0){
		i=ends[i];
	}
	return i;
}
void Kruskal(Graph g,Edges e){
	int index=0;
	int ends[g->edge]={0};//保存最小生成樹中每個頂點的終點 
	
	//創(chuàng)建結(jié)果數(shù)組 ，保存最終的最小生成樹 Res 為Result的縮寫 
	Edges edgeRes =(Edges) malloc(g->edge*sizeof(struct Edge));
	
	//按照邊的權(quán)值大小排序，我已經(jīng)在main里排序過了
	
	//遍歷edges數(shù)組從最小邊開始加，加一次判回路一次，沒回路就加進來（edgeRes），有回路就換下一條
	
	 for(int i =0;i<g->edge;i++) {
	 	//拿到第i條邊的頂點的下標start 
		int p1= getIndex(g,e[i].start);
		//拿到第i條邊的頂點的下標start 
		int p2= getIndex(g,e[i].end);
		cout<<"p1 "<<p1<<"p2 "<<p2<<endl;
		
		//獲取p1頂點的在已有的最小生成樹中終點是？
		int m =getEnds(ends,p1);
		//獲取p2頂點的在已有的最小生成樹中終點是？
		int n =getEnds(ends,p2);
		cout<<"m "<<m<<"n "<<n<<endl;
		for(int j=0;j<g->edge;j++)
		cout<<ends[i];
		cout<<endl;
		//是否構(gòu)成回路
		if(m!=n) {//不構(gòu)成回路 
			ends[m] =n; //設(shè)置m 在已有最小生成樹的終點 
			edgeRes[index++]=e[i];
			cout<<"index "<<index<<endl;
		}
	 }
	 //統(tǒng)計并打印最小生成樹
	  for(int i =0;i<index;i++){
	  	cout<<" "<<edgeRes[i].start<<" "<<edgeRes[i].end<<" "<<edgeRes[i].weight<<endl;
	  }
	
	
}
int cmp(const void *a, const void *b){
    return ((struct Edge *)a)->weight - ((struct Edge *)b)->weight;
}




int main(){

	int n;
	cin>>n;
	Graph graph=Create();
	Edges edges;
	edges=( Edges)malloc((n*(n-1)/2)*sizeof(struct Edge));
	for(int i=0;i<n;i++){
		char e;cin>>e;
		addVex(graph,e);
	}
		
	E v1,v2;int w;
	while(cin>>v1>>v2){
		cin>>w;
		addEdge(graph,v1,v2,w,edges);
	}

	cout<<"第一次"<<endl;
	printMatrix(graph,edges);

	qsort(edges,graph->edge, sizeof(Edge), cmp);
	cout<<"庫魯斯卡爾："<<endl; 
	Kruskal(graph,edges);
	cout<<"排序后"<<endl;
	printMatrix(graph,edges);
	
	
}