C Programlama Prim Algoritması

Prim Algoritması, minimum spanning tree algoritmalarından biridir. Kenarların bir alt kümesini, tüm düğümleri kapsayacak ve kenarların toplam ağırlığını minimum yapacak şekilde bulur.

Bu algoritma 1930 yılında matematikçi Vojtech Jarnik tarafından bulunmuştur. Daha sonra bağımsız olarak 1957’de bilgisayar bilimcisi Robert C. Prim ve 1959’da Dijkstra tarafından tekrar bulunmuştur. Bu nedenle bu algoritmaya DJP veya Jarnik algoritması da denir.

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

int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];
int main() {
system("CLS");
printf("\n Enter the number of nodes:");
scanf("%d",&n);
printf("\n Enter the adjacency matrix:\n");

 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++) {
   scanf("%d",&cost[i][j]);
   if(cost[i][j]==0)
    cost[i][j]=999;
}

visited[1]=1;
printf("\n");

 while(ne<n) {
  for(i=1,min=999;i<=n;i++)
   for(j=1;j<=n;j++)
    if(cost[i][j]<min)
     if(visited[i]!=0) {
      min=cost[i][j];
      a=u=i;
      b=v=j;
}
  
  if(visited[u]==0 || visited[v]==0) {
   printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);
   mincost+=min;
   visited[b]=1;
}
   cost[a][b]=cost[b][a]=999;
}
   printf("\n Minimun cost=%d",mincost);
   
   return 0;
   getch();
}

}