THUẬT TOÁN KRUSKAL

 THUẬT TOÁN KRUSKAL

#include<stdio.h>

// Do thi

#define MAX_VERTICES 100

typedef struct{
	int u, v;
	int w;
}Edge;

typedef struct{
	int n, m;
	Edge edges[MAX_VERTICES];
}Graph;

void init_graph(Graph* G, int n){
	G->n = n;
	G->m = 0;
}

void add_edge(Graph* G, int u, int v, int w){
	G->edges[G->m].u = u;
	G->edges[G->m].v = v;
	G->edges[G->m].w = w;
	G->m++;
}

// Giai thuat

int parent[MAX_VERTICES];

int FindRoot(int u){
	if (parent[u]==u)
		return u;
	return FindRoot(parent[u]);
}

void Swap(Edge* a, Edge* b){
	Edge temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

void Bubble_Sort(Edge a[], int n){
	int i, j;
	for(i=0; i<=n-2; i++){
		for(j=n-1; j>=i+1; j--){
			if(a[j].w < a[j-1].w){	
				Swap(&a[j],&a[j-1]);			
			}
		}
	}
}

int Kruskal(Graph* G, Graph* T){
		
	Bubble_Sort(G->edges,G->m);
	
	int e;
	init_graph(T,G->n);
	for(e=1; e<=G->n; e++)
		parent[e] = e;
	int sum_w = 0;
	
	for(e=0; e<G->m; e++){
		int u = G->edges[e].u;
		int v = G->edges[e].v;
		int w = G->edges[e].w;
		
		int root_u = FindRoot(u);
		int root_v = FindRoot(v);
		
		if (root_u != root_v){
			add_edge(T,u,v,w);
			parent[root_v] = root_u;
			sum_w += w;
		}		
	}
	return sum_w;
}

int main(){
//	freopen("dt.txt", "r", stdin);
	Graph G, T;
	int n, m, e, x, y, w;
	scanf("%d%d",&n,&m);
	init_graph(&G,n);
	for(e=1;e<=m;e++){
		scanf("%d%d%d",&x,&y,&w);
		add_edge(&G,x,y,w);
	}

	int sum_w = Kruskal(&G,&T);
	printf("%d \n",sum_w);
	
	for(e=0; e<T.m; e++){
	if(T.edges[e].u >T.edges[e].v)
		printf("%d %d %d \n",T.edges[e].v,T.edges[e].u,T.edges[e].w);
	else	
		printf("%d %d %d \n",T.edges[e].u,T.edges[e].v,T.edges[e].w);
}
	return 0;
}