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.

prim_exam

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:

7.input

 

7.out


Advertisements