Tìm cây khung nhỏ nhất trên đồ thị bằng thuật toán Prim và Kruskal?

Mấy thuật toán này khá phổ biến và có nhiều tài liệu trên mạng, trước khi viết code thì xem xem thuật toán làm việc ntn, bạn đã thử tìm trên google chưa ? thử đi, có nhiều nguồn hướng dẫn lắm.

Hồi trước mình kiểm tra toán rời rạc có làm cái Shortest path với Minimun spanning tree (Prim)

Hồi sáng lên trường làm về 2 bài này, giờ tiện tay post code lên cho mấy bạn chưa học tham khảo.

Nhưng chỉ có code thôi, tại mình cũng không biết giải thích sao cho dễ hiểu. Việc tìm hiểu mấy bạn phải tự đọc tài liệu thôi. Nếu đồ án yêu cầu trình bày đầy đủ thì bạn trình bày cho họ từ khái niệm cây khung là gì, Thuật toán Prim xử lý như thế nào? … Rồi giải thích từng hàm trong code của bạn cho người ta hiểu là xong. (Có hình minh họa càng tốt)

#include<stdio.h>
#include<conio.h>

main()
{
	int i,j,a,b,n,t=1;
    int min,mincost=0,cost[9][9];
	
	printf("\n********giai thua kruskal********\n");
	printf("\nnhap so dinh cua do thi:");
	scanf("%d",&n);
	
	printf("\nnhap gia tri ma tran ke:\n");  
	for(i=1;i<=n;i++)                 //luu gia tri ma tran ke gan vao mang 2 chieu cost[][].
		for(j=1;j<=n;j++)
		{
			scanf("%d",&cost[i][j]);
			if(cost[i][j]==0)             // giua 2 dinh k co canh thi coi gia tri la vo han
				cost[i][j]=999;
		}
	
	printf("cac canh cua cay khung nho nhat la :\n");
	while(t < n)                 //tim du cac canh (so canh = so dinh - 1) thi dung lai
	{
		for(i=1,min=999;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				if(cost[i][j] < min)   // so sanh gia tri tat ca cac canh de tim canh nho nhat
				{
					min=cost[i][j];               // luu gia tri canh vua tim duoc = min
					a=i;                        // luu a,b la 2 dinh cua canh vua tim duoc
					b=j;
				}
			}
	    printf("%d canh (%d,%d) =%d\n",t++,a,b,min);   // in ra canh voi gia tri cua no.
		mincost +=min;                               // cong tong gia tri cac canh tim duoc luu vao gia tri cua cay khung
		cost[a][b]=cost[b][a]=999;     // gan gia tri canh vua tim = vo han. (de vong sau k chon nua)
	}
	printf("\n\tgia tri cay khung nho nhat nho nhat = %d\n",mincost);
	getch();
}

Mình buộc phải đăng ký tài khoản để nói lên cái sai của bạn trong bài này mà hơn 2 năm nay chả có ai trả lời cả. Bài của bạn chỉ đưa ra các cạnh có trọng số nhỏ nhất nhưng chưa chú ý đến việc chúng có tạo thành chu trình hay không ? Nếu 2 đỉnh đang xét tạo thành chu trình thì phải bỏ qua chúng và xét các cặp đỉnh khác mới tạo thành cây khung được.
xin lỗi vì đã đào bới nhưng nếu để đây và không nói gì hẵng nhiều người sẽ phải mất thời gian với đống code được coi là sai ở trên.

xin lỗi vì đã đào bới nhưng nếu để đây và không nói gì hẵng nhiều người sẽ phải mất thời gian với đống code được coi là sai ở trên.

Miễn là có ý kiến mang tính xây dựng là được