-
Notifications
You must be signed in to change notification settings - Fork 0
/
PRIMS.C
executable file
·136 lines (107 loc) · 2.16 KB
/
PRIMS.C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
/*
Program Purpose : To Perform Prim's Algorithm for the minimum cost in
the Graph Path
Coded by : Devendra Walanj
Subject : Analysis of Algorithms
Semister : IV
*/
#include<stdio.h>
#include<conio.h>
int check[10];
void admat (int a[][10])
{
int i,j,e,w;
printf("Want to enter an edge (0:no;1:yes) : ");
scanf("%d",&e);
while(e)
{
printf("Enter node number from & to : ");
scanf("%d%d",&i,&j);
printf("Enter weight of edge : ");
scanf("%d",&w);
a[i][j] = w;
a[j][i] = w;
printf("\nWant to enter an edge (0:no;1:yes) : ");
scanf("%d",&e);
}
}
void primat (int a[][10],int n)
{
int i,j;
for(i=1;i<=n;i++)
printf("\t%d",i);
printf("\n");
for(i=1;i<=n;i++)
{
printf("%d",i+1);
for(j=1;j<=n;j++)
printf("\t%d",a[i][j]);
printf("\n");
}
}
void prims(int a[][10],int v)
{
int d[10],p[10]={0},visit[10]={0};
int curr,sum = 0,k,n,i,min;
curr = 1;
for(i=0;i<10;i++)
d[i] = 32767;
d[curr] = 0;
visit[curr] = 1;
n = 1;
while(n!=v)
{
for(k=1;k<=v;k++)
{
if(a[curr][k]!=0 && visit[k]==0)
if(a[curr][k]<d[k])
{
d[k] = a[curr][k];
p[k] = curr;
}
}
min = 32767;
for(i=1;i<=v;i++)
{
if(visit[i]==0)
if(d[i]<min)
{
min = d[i];
curr = i;
}
}
n = n + 1;
visit[curr] = 1;
}
printf("Minimum cost is : ");
for(i=1;i<=v;i++)
sum = sum + d[i];
printf("%d\n",sum);
}
void main()
{
int mat[10][10]={0};
int i,n,ch,v,m;
system("cls");
printf("Enter total No of Nodes : ");
scanf("%d",&n);
admat(mat);
prims(mat,n);
getch();
}
/*
OUTPUT :
Enter total No of Nodes : 4
Want to enter an edge (0:no;1:yes) : 1
Enter node number from & to : 2 4
Enter weight of edge : 2
Want to enter an edge (0:no;1:yes) : 1
Enter node number from & to : 1 3
Enter weight of edge : 5
Want to enter an edge (0:no;1:yes) : 1
Enter node number from & to : 4 3
Enter weight of edge : 6
Want to enter an edge (0:no;1:yes) : 0
Minimum cost is : 13
Press any key to continue
*/