60 {
61 size_t size = adj.size();
62 size_t total_groups = size;
63
64 if (size <= 1) {
65 return adj;
66 }
67
68
69
70 std::vector<std::vector<int>> MST(size, std::vector<int>(size, INT_MAX));
71 for (int i = 0; i < size; i++) {
72 MST[i][i] = 0;
73 }
74
75
76
77
78
79 std::vector<std::pair<int, int>> parent(size, std::make_pair(0, 0));
80
81 for (int i = 0; i < size; i++) {
82 parent[i].first =
83 i;
84 }
85
86
87 while (total_groups > 1) {
88 std::vector<std::pair<int, int>> smallest_edge(
89 size, std::make_pair(-1, -1));
90
91
92
93 for (int i = 0; i < size; i++) {
94 for (int j = i + 1; j < size; j++) {
95 if (adj[i][j] == INT_MAX || adj[i][j] == 0) {
96 continue;
97 }
98
99
100
103
104 if (parentA != parentB) {
105
106
107 int start = smallest_edge[parentA].first;
108 int end = smallest_edge[parentA].second;
109
110
111
112 if (start == -1 || adj[i][j] < adj[start][end]) {
113 smallest_edge[parentA].first = i;
114 smallest_edge[parentA].second = j;
115 }
116
117
118 start = smallest_edge[parentB].first;
119 end = smallest_edge[parentB].second;
120
121 if (start == -1 || adj[j][i] < adj[start][end]) {
122 smallest_edge[parentB].first = j;
123 smallest_edge[parentB].second = i;
124 }
125 }
126 }
127 }
128
129
130
131 for (int i = 0; i < size; i++) {
132
133 if (smallest_edge[i].first != -1) {
134
135 int start = smallest_edge[i].first;
136 int end = smallest_edge[i].second;
137
138
139 int parentA = i;
141
142
143
144
145 if (parentA == parentB) {
146 continue;
147 }
148
149
150
151
152 if (parent[parentA].second < parent[parentB].second) {
153 parent[parentB].first = parentA;
154 parent[parentB].second++;
155 } else {
156 parent[parentA].first = parentB;
157 parent[parentA].second++;
158 }
159
160
161 MST[start][end] = adj[start][end];
162 MST[end][start] = adj[end][start];
163 total_groups--;
164 }
165 }
166 }
167 return MST;
168}
int findParent(std::vector< std::pair< int, int > > parent, const int v)
Recursively returns the vertex's parent at the root of the tree.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4