#include
#define infinity 9999
#define MAX 20
int
G
[
MAX
]
[
MAX
]
,
spanning
[
MAX
]
[
MAX
]
,
n
;
int
prims
(
)
;
int
ReadMatrix
(
char
filepath
[
]
)
;
void
OutputMatrix
(
)
;
int
ReadMatrix
(
char
filepath
[
]
)
{
FILE*
f
=
fopen
(
filepath
,
“r”
)
;
if
(
f
==
NULL
)
{
printf
(
“\nCant open file”
)
;
return
0
;
}
fscanf
(
f
,
“%d”
,
&n);
for
(
int
i
=
0
;
i
<
n
;
i
++
)
for
(
int
j
=
0
;
j
<
n
;
j
++
)
fscanf
(
f
,
“%d”
,
&G[i][j]);
fclose
(
f
)
;
return
1
;
}
void
OutputMatrix
(
)
{
printf
(
“Number of Vertices: %d\n”
,
n
)
;
for
(
int
i
=
0
;
i
<
n
;
i
++
)
{
printf
(
“\n”
)
;
for
(
int
j
=
0
;
j
<
n
;
j
++
)
printf
(
“%d\t”
,
G
[
i
]
[
j
]
)
;
}
}
int
main
(
)
{
int
i
,
j
,
total_cost
;
ReadMatrix
(
“Prim.txt”
)
;
total_cost
=
prims
(
)
;
printf
(
“\nSpanning Tree Matrix:\n”
)
;
OutputMatrix
(
)
;
printf
(
“\n\nTotal cost of spanning tree=%d”
,
total_cost
)
;
return
0
;
}
int
prims
(
)
{
int
cost
[
MAX
]
[
MAX
]
;
int
u
,
v
,
min_distance
,
distance
[
MAX
]
,
from
[
MAX
]
;
int
visited
[
MAX
]
,
no_of_edges
,
i
,
min_cost
,
j
;
for
(
i
=
0
;
i
<
n
;
i
++
)
for
(
j
=
0
;
j
<
n
;
j
++
)
{
if
(
G
[
i
]
[
j
]
==
0
)
cost
[
i
]
[
j
]
=
infinity
;
else
cost
[
i
]
[
j
]
=
G
[
i
]
[
j
]
;
spanning
[
i
]
[
j
]
=
0
;
}
distance
[
0
]
=
0
;
visited
[
0
]
=
1
;
for
(
i
=
1
;
i
<
n
;
i
++
)
{
distance
[
i
]
=
cost
[
0
]
[
i
]
;
from
[
i
]
=
0
;
visited
[
i
]
=
0
;
}
min_cost
=
0
;
//cost of spanning tree
no_of_edges
=
n
–
1
;
//no. of edges to be added
while
(
no_of_edges
>
0
)
{
min_distance
=
infinity
;
for
(
i
=
1
;
i
<
n
;
i
++
)
if
(
visited
[
i
]
==
0
&&distance[i]
{
v=i;
min_distance
=
distance
[
i
]
;
}
u
=
from
[
v
]
;
spanning
[
u
]
[
v
]
=
distance
[
v
]
;
spanning
[
v
]
[
u
]
=
distance
[
v
]
;
no_of_edges
—
;
visited
[
v
]
=
1
;
for
(
i
=
1
;
i
<
n
;
i
++
)
if
(
visited
[
i
]
==
0
&&cost[i][v]
{
distance[i]=cost[i][v];
from
[
i
]
=
v
;
}
min_cost
=
min_cost
+
cost
[
u
]
[
v
]
;
}
return
(
min_cost
)
;
}
