Thuật toán Prim:

Bước 1 (Khởi tạo):

            T = f; D(T) = 0; VT = f; u =<Đỉnh xuất phát bất kỳ>;

V = V\u; VT = VT È u;

Bước 2 (Lặp):

            while (V≠f ) {

                        <Chọn e = (v, t) là cạnh có trọng số nhỏ nhất sao cho vÎV, tÎVT >;

                        if ( d(e) = ¥ ) { <đồ thị không liên thông>; return (¥);}

                        T = TÈ{e}; D(T) = D(T) + d(e);

                        V = V \ v; VT = VTÈv;

            }

Bước 3 (Trả lại kết quả):

            Return( T, D(T));

CODE

#include <stdio.h>

#include <conio.h>

#define MAX_VALUE 9999

int **a,n,*dau,*cuoi;

void Prim(int start){

            int i,j,k,min,dmin1,dmin2,t,sum=0;

            int *d = new int[n];

            /* Khoi tao */

            for(i=0;i<n;i++){

                        d[i]=0;

            }

            d[start]=1;

            k=0;

            //

            while(k<n-1){

                        dmin1 = -1;

                        dmin2 = -1;

                        min = MAX_VALUE;

                        for(i=0;i<n;i++){

                                    if(d[i]==1){

                                                for(j=0;j<n;j++){

                                                            if(d[j]==0 && a[i][j]!=0 && a[i][j]<min){

                                                                        min = a[i][j];

                                                                        dmin1 = i;

                                                                        dmin2 = j;

                                                            }

                                                }

                                    }

                        }

                        if(dmin1 == -1){

                                    break;

                        }

                        dau[k] = dmin1;

                        cuoi[k] = dmin2;

                        sum+=a[dmin1][dmin2];

                        d[dmin2]=1;

                        k++;

            }

            /*In ket qua*/

            printf("

Cay khung nho nhat = %d",sum);

            printf("

Chua cac canh :

");

            for(i=0;i<n-1;i++){

                        printf("%d %d

",dau[i]+1,cuoi[i]+1);

            }

}

void main(){

            clrscr();

            int i,j;

            FILE *in;

            in = fopen("prim.txt","r");

            //Doc chi so mang va tao mang 2 chieu

            fscanf(in,"%d",&n);

            a = new int*[n];

            for(i=0;i<n;i++){

                        a[i] = new int[n];

            }

            //Doc gia tri mang

            for(i=0;i<n;i++){

                        for(j=0;j<n;j++){

                                    fscanf(in,"%d",&a[i][j]);

                        }

            }

            //In

            for(i=0;i<n;i++){

                        for(j=0;j<n;j++){

                                    printf("%d ",a[i][j]);

                        }

                        printf("

");

            }

            printf("

");

            //

            dau = new int[n-1];

            cuoi = new int[n-1];

            Prim(0);

            getch();

}