Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar13 / src / mst-prim.cpp
diff options
context:
space:
mode:
Commit1b1a8c4758334d8e67408429a8ad23f374c1af20 (patch)
Author
 Stoycho Kyosev <skyosev@192.168.100.17>
2025-01-18 15:08:53 -0500
Committer
 Stoycho Kyosev <skyosev@192.168.100.17>
2025-01-18 15:08:53 -0500
Filesa57b3fe86779e1adbb11ffb42e6e2b35786af13f /Seminar13/src/mst-prim.cpp
Data-structures-and-algorithms-1b1a8c4758334d8e67408429a8ad23f374c1af20.tar
Data-structures-and-algorithms-1b1a8c4758334d8e67408429a8ad23f374c1af20.tar.gz
Data-structures-and-algorithms-1b1a8c4758334d8e67408429a8ad23f374c1af20.zip
Parent9951cc576ee6f1a5a3b641f9dcb5fe4af7a77b51 (diff)
Add mst
1 files changed, 115 insertions, 0 deletions
-rw-r--r--Seminar13/src/mst-prim.cpp115
diff --git a/Seminar13/src/mst-prim.cpp b/Seminar13/src/mst-prim.cpp
new file mode 100644
index 0000000..c342ce8
--- /dev/null
+++ b/Seminar13/src/mst-prim.cpp
@@ -0,0 +1,115 @@
+#include "../../Seminar12/src/graph_impl/weighted_graph/weighted_graph.h"
+#include <queue>
+#include <iostream>
+#include <limits.h>
+
+using vertex_t = weighted_graph::vertex_t;
+using vertex_index_t = weighted_graph::vertex_index_t;
+using weight_t = weighted_graph::weight_t;
+
+struct mst_info
+{
+ std::vector<vertex_index_t> tree;
+ int cost = 0;
+};
+
+mst_info prim(const weighted_graph& g, vertex_index_t start = 0)
+{
+ mst_info result;
+
+ if(g.vertex_count() == 0)
+ return result;
+
+ std::vector<bool> visited(g.vertex_count(), false);
+ result.tree.resize(g.vertex_count(), -1);
+ // min_cost[i] = minimum cost found!
+ std::vector<weight_t> min_cost(g.vertex_count(), INT_MAX);
+
+ struct vertex_comparator
+ {
+ bool operator()(const vertex_t& lhs, const vertex_t& rhs) const
+ {
+ return lhs.second > rhs.second;
+ }
+ };
+
+ std::priority_queue<vertex_t, std::vector<vertex_t>, vertex_comparator> p;
+
+ // initialize structures:
+ p.push({start, 0});
+ min_cost[start] = 0;
+
+ size_t found_edges = 0;
+
+ while(found_edges != g.vertex_count())
+ {
+ vertex_index_t current_vertex = p.top().first;
+ weight_t current_weight = p.top().second;
+
+ p.pop();
+
+ if(visited[current_vertex])
+ continue;
+
+ visited[current_vertex] = true;
+ result.cost += current_weight;
+ ++found_edges;
+
+ const auto& adjacent = g.adjacent(current_vertex);
+
+ for(const vertex_t& vertex : adjacent)
+ {
+ vertex_index_t found_index = vertex.first;
+ weight_t found_weight = vertex.second;
+
+ if(!visited[found_index] && found_weight < min_cost[found_index])
+ {
+ result.tree[found_index] = current_vertex;
+ p.push({found_index, found_weight});
+ min_cost[found_index] = found_weight;
+ }
+ }
+ }
+
+ return result;
+}
+
+int main()
+{
+ // Create a weighted graph with 7 vertices, undirected
+ weighted_graph g(7, false);
+
+ // Add edges with weights
+ g.add_edge(0, 1, 4);
+ g.add_edge(0, 2, 3);
+ g.add_edge(1, 2, 1);
+ g.add_edge(1, 3, 2);
+ g.add_edge(2, 4, 5);
+ g.add_edge(3, 4, 6);
+ g.add_edge(3, 5, 7);
+ g.add_edge(4, 6, 8);
+ g.add_edge(5, 6, 4);
+
+ // g.add_edge(0, 1, 10);
+ // g.add_edge(0, 2, 5);
+ // g.add_edge(1, 2, 1);
+ // g.add_edge(1, 3, 2);
+ // g.add_edge(2, 3, 3);
+
+ // Run Prim's algorithm
+ auto result = prim(g);
+
+ // Print the total cost of the MST
+ std::cout << "Total cost of MST: " << result.cost << '\n';
+
+ // Print the tree structure
+ std::cout << "Tree structure (parent array): ";
+ for (const auto x : result.tree)
+ {
+ std::cout << x << " ";
+ }
+
+ std::cout << '\n';
+
+ return 0;
+} \ No newline at end of file