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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include<process.h>
#define MAX 5
#define TEMP 0
#define PERM 1
#define FALSE 0
#define TRUE 1
#define infinity 6
using namespace std;
struct node
{
int predecessor;
int dist; /*Distance from predecessor */
int status;
};
struct edge
{
int u;
int v;
};
void display();
int maketree(edge [],int *);
int all_perm(node [] );
int integers[MAX][MAX];
int n;
int main()
{
ifstream inputf;
inputf.open("Inputs.txt");
string buffer;
for (int x=0;x<=5;x++)
{
for (int y = 0;y<=5;y++)
{
inputf>>integers[x][y];
cout << integers[x][y] << ',' << ends;
}
cout << endl;
}
inputf.close();
ofstream outfile ("outfile.txt");
int x;
int path[MAX];
int wt_tree,count;
struct edge tree[MAX];
display();
count = maketree(tree,&wt_tree);
cout<<"Weight of spanning tree is : "<<wt_tree;
cout<<"Edges to be included in spanning tree are : n";
for(x=0;x<=count;x++)
{
cout<<tree[x].u<<" -> n";
cout<<tree[x].v<<"n";
}
outfile.close();
return 0;
}
void display()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
cout<<"t"<<integers[i][j];
cout<<"n";
}
}
int maketree(edge tree[MAX],int *weight)
{
node state[MAX];
int i,k,min,count,current,newdist;
int m;
int u1,v1;
*weight=0;
/*Make all nodes temporary*/
for(i=1;i<=n;i++)
{
state[i].predecessor=0;
state[i].dist = infinity;
state[i].status = TEMP;
}
/*Make first node permanent*/
state[1].predecessor=0;
state[1].dist = 0;
state[1].status = PERM;
/*Start from first node*/
current=0;
count=0;
/*count represents number of nodes in tree */
while( all_perm(state) != TRUE ) /*Loop till all the nodes become PERM*/
{
for(i=1;i<=n;i++)
{
if ( integers[current][i] > 0 && state[i].status == TEMP )
{
if( integers[current][i] < state[i].dist )
{
state[i].predecessor = current;
state[i].dist = integers[current][i];
}
}
}
/*Search for temporary node with minimum distance and make it current node*/
min=infinity;
for(i=1;i<=n;i++)
{
if(state[i].status == TEMP && state[i].dist < min)
{
min = state[i].dist;
current=i;
}
}
state[current].status=PERM;
/*Insert this edge(u1,v1) into the tree */
u1=state[current].predecessor;
v1=current;
count++;
tree[count].u=u1;
tree[count].v=v1;
/*Add wt on this edge to weight of tree */
*weight=*weight+integers[u1][v1];
}/*End of while*/
return (count);
}/*End of maketree()*/
/*This function returns TRUE if all nodes are permanent*/
int all_perm(node state[MAX] )
{
int i;
for(i=1;i<=n;i++)
if( state[i].status == TEMP )
return FALSE;
else
return TRUE;
}/*End of all_perm()*/
|
