# 最小生成樹演算法(minimum spanning tree)

## Kruskal`s algorithm MST

#include <stdio.h> 
#include <stdlib.h> 
struct Edge{
	int src;//source
	int dest;//destination
	int weight;
};

struct Graph{
	int V;//number of vertex
	int E;//number of edge
	
	struct Edge *edge;//graph contain edge
};
struct subset{
	int parent;//root of this vertex 
	int rank;//to compare union order
};
//initialize graph
struct Graph* createGraph(int V,int E){
	//allocate memory
	struct Graph* graph=(struct Graph*)malloc(sizeof(struct Graph));
	//push value
	graph->V=V;
	graph->E=E;
	graph->edge=(struct Edge*)malloc(graph->E*sizeof(struct Edge));//allocate E times to the poiner edge
	
	return graph;
};
int find(struct subset subsets[],int i){//all subset,edge
	if(subsets[i].parent!=i)//root not i itself
		subsets[i].parent=find(subsets,subsets[i].parent);//find until reach
		
	return subsets[i].parent;//if reach the root
}

void Union(struct subset subsets[],int x,int y){
	int xroot=find(subsets,x);
	int yroot=find(subsets,y);
	
	if(subsets[xroot].rank>subsets[yroot].rank){//rank:xroot>yroot
		subsets[yroot].parent=xroot;//change yroot parent
	}
	
	else if(subsets[xroot].rank<subsets[yroot].rank){//rank:xroot<yroot
		subsets[xroot].parent=yroot;//change xroot parent
	}
	else{//rank:xroot=yroot
		subsets[yroot].parent=xroot;//change yroot parent
		subsets[xroot].rank++;//rank up
	}
}
int myComp(const void*a,const void *b){// compare rule
	struct Edge* a1=(struct Edge*)a;//parameter convert
	struct Edge* b1=(struct Edge*)b;
	//must >，that will from small to large 
	return a1->weight > b1->weight;//a1 and b1 is pointer so use -> not .
}
void KruskalMST(struct Graph* graph){
	
	int V=graph->V;//get V graph
	//result edge
	struct Edge result[V];//don't allocate,number of edge will be V
	int e=0;//selected edge order
	int i=0;//tested edge
	//allocate and initial subsets
	struct subset* subsets=(struct subset*)malloc(V*sizeof(struct subset));//number of vertices subset[]
	for(int v=0;v<V;v++){
		subsets[v].parent=v;//itself
		subsets[v].rank=0;//from 0
	}
	//qsort let smallest at front
	qsort(graph->edge,graph->E,sizeof(graph->edge[0]),myComp);//edge in graph,number of edge in graph,size of edge,rule
	
	while(e < (V-1) && i < (graph->E)){//when e is V-1，i must < graph->E
		
		//test if have cylce or not
		//find and Union
		struct Edge next_edge = graph->edge[i];//fixed the edge
		i++;//to next graph of edge
		int x=find(subsets,next_edge.src);//src
		int y=find(subsets,next_edge.dest);//dest
		
		//if no cycle put in result
		if(x!=y){
			result[e]=next_edge;
			e++;//to next result
			Union(subsets,x,y);//if no cycle,union
		}
	}
	//print src,dest,weight
printf(
        "Following are the edges in the constructed MST\n");
	int minWeight=0;
	for(i=0;i<e;i++){//print out all e
		printf("%d---%d:%d\n",result[i].src,result[i].dest,result[i].weight);
		minWeight+=result[i].weight;
		
	}
	printf("minWeight:%d",minWeight);
		
}

int main(){
	/* Let us create following weighted graph
             10
        0--------1
        |  \     |
       6|   5\   |15
        |      \ |
        2--------3
            4       */
    int V = 4; // Number of vertices in graph
    int E = 5; // Number of edges in graph
    struct Graph* graph = createGraph(V, E);
 
    // add edge 0-1
    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = 10;
 
    // add edge 0-2
    graph->edge[1].src = 0;
    graph->edge[1].dest = 2;
    graph->edge[1].weight = 6;
 
    // add edge 0-3
    graph->edge[2].src = 0;
    graph->edge[2].dest = 3;
    graph->edge[2].weight = 5;
 
    // add edge 1-3
    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 15;
 
    // add edge 2-3
    graph->edge[4].src = 2;
    graph->edge[4].dest = 3;
    graph->edge[4].weight = 4;
 
    KruskalMST(graph);
 
    return 0;
}

## Prim's algorithm MST

#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
// Number of vertices in the graph
#define V 5
void printMST(int parent[], int graph[V][V])//MST store in parent
{
    printf("Edge \tWeight\n");
    for (int i = 1; i < V; i++)
        printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
}

int minKey(int key[],bool mstSet[]){
	int min=INT_MAX,min_index;
	
	for(int v=0;v<V;v++){
		if(key[v]<min&&mstSet[v]==false){
			min=key[v];
			min_index=v;
		}
	}
	return min_index;
}

void primMST(int graph[V][V]){
	int parent[V];//min_index
	int key[V];//min
	bool mstSet[V];
	//initialize
	for(int i=0;i<V;i++){
		key[i]=INT_MAX;
		mstSet[i]=false;
	}
	 
	key[0] = 0;
    parent[0] = -1; // First node is always root of MST
    
    
	//minKey and add to parent
	for(int i=0;i<V-1;i++){//edge
	
		int u=minKey(key,mstSet);
		mstSet[u]=true;
		
		for(int v=0;v<V;v++){//matrix number
			//graph weight push in key
		if(mstSet[v]==false && graph[u][v] && graph[u][v]<key[v]){//update key
			parent[v]=u;
			key[v]=graph[u][v];
		}
		}
	}
	printMST(parent,graph);

};
int main()
{
    /* Let us create the following graph
        2 3
    (0)--(1)--(2)
    | / \ |
    6| 8/ \5 |7
    | /     \ |
    (3)-------(4)
            9         */
    int graph[V][V] = { { 0, 2, 0, 6, 0 },
                        { 2, 0, 3, 8, 5 },
                        { 0, 3, 0, 0, 7 },
                        { 6, 8, 0, 0, 9 },
                        { 0, 5, 7, 9, 0 } };
 
    // Print the solution
    primMST(graph);
 
    return 0;
}