-
Notifications
You must be signed in to change notification settings - Fork 17
/
3prims.cpp
97 lines (83 loc) · 1.89 KB
/
3prims.cpp
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
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, pair<int, int>>> graph, mst;
int N, E;
int root(int n, int *parent)
{
while (n != parent[n])
{
n = parent[n];
}
return n;
}
int prim(int start)
{
int total = 0;
bool intree[100];
for (int i = 0; i < N; i++)
{
intree[i] = false;
}
int n = start;
while (!intree[n])
{
intree[n] = true;
int w = 1000000; // Infinite
int min = -1;
int min_next;
for (int i = 0; i < graph.size(); i++)
{
if (graph[i].second.first == n || graph[i].second.second == n)
{
int next;
if (graph[i].second.first == n)
next = graph[i].second.second;
else
next = graph[i].second.first;
if (!intree[next] && graph[i].first < w)
{
w = graph[i].first;
min = i;
min_next = next;
}
}
}
if (min != -1)
{
n = min_next;
mst.push_back(graph[min]);
total += graph[min].first;
}
}
return total;
}
int main()
{
cout << "Enter Graph " << endl;
cin >> N >> E;
for (int i = 0; i < E; i++)
{
char u, v;
int w;
cin >> u >> v >> w;
graph.push_back(make_pair(w, make_pair(u - 'A', v - 'A')));
}
mst.clear();
cout << "USING PRIMS" << endl;
int total = prim(0);
for (int i = 0; i < mst.size(); i++)
{
printf("%c %c %d\n", mst[i].second.first + 'A', mst[i].second.second + 'A', mst[i].first);
}
printf("Total cost of MST with Prim: %i\n", total);
return 0;
}
/*
Graph
4 5
A B 10
B C 15
A C 5
D B 2
D C 40
*/