# Minimum Spanning Trees and Prim's Algorithm

**1. Introduction:**

Describe the problem: for the undirected graph weighted G = (V, E) find the way so that all the top things that way together and the total weight of the smallest way.

The idea of the algorithm:

Step 1: starting from any vertex k (usually selected first peak) has selected a minimum weight edge adjacent to the vertex k (min {A [k] [j]} j = 1..n) we 2 top passing mark and the next addition is found to be 1 to Step 2.

Step 2: Find the smallest edge of the graph with edge conditions found to have 1 top and 1 top mark not marked. That is, we find min {A [i] [j] j = 1..n}, i = 1..n such that i and j marks not marked to avoid the forming cycle. We increased the number of edges found on 1 and go to Step 3.

Step 3: If the edges found by n-1 end of the algorithm, reverse back to Step 2.

**2. Source code:**

#include <stdio.h> #include <values.h> #define max 100 #define FileInt "File7.inp" #define FileOut "File7.out" typedef struct Egde{ int x,y; }; //Read data from File void Read_File(int A[max][max],int &n) { FILE*f = fopen(FileInt,"rb"); fscanf(f,"%d",&n); for(int i =0;i<n;i++) { for(int j =0;j<n;j++) { fscanf(f,"%d",&A[i][j]); } } fclose(f); } //Print data into file void Write_File(Egde L[max],int n,int Sum) { FILE*f = fopen(FileOut,"wb"); fprintf(f,"%d\n",Sum); for(int i =0; i<n-1; i++) fprintf(f,"%d - %d\n",L[i].x+1,L[i].y+1); fclose(f); } //Prim Algorithm void Prim(int A[max][max], int n) { char D[max]; Egde L[max]; int min = MAXINT, Count = 0, Sum = 0; for(int i=0; i<n; i++) D[i]=0; for(int j=1; j<n; j++) if(min>A[0][j] && A[0][j]!=0){ min = A[0][j]; L[0].y = j; } L[0].x = 0; D[0] = 1; D[L[0].y] = 1; Sum+=min; Count++; do { min = MAXINT; for( i=0; i<n; i++) if(D[i]==1) for( j=0; j<n; j++) if(A[i][j]>0 && min>A[i][j] && D[j]==0){ min = A[i][j]; L[Count].x = i; L[Count].y = j; } Sum+=min; D[L[Count].y] = 1; Count++; } while(Count<n-1); Write_File(L,n,Sum); } //main function void main() { int A[max][max],n; Read_File(A,n); Prim(A,n); } |

**3. Result:**