This document explores the implementation of algorithms to find the Minimum Spanning Tree (MST) for a given set of connected, undirected graph problems.
Prim's Algorithm for Danse Graphs
Prim's algorithm is efficient for dense graphs. Its complexity is O(V^2) using an adjacency matrix or O(V log V + E) with an adjacency list and a priority queue optimization, where V is the number of vertices and E is the number of edges.
When using Prim's algorithm, pay close attention to vertex indexing. Some problems may use 1-based indexing for vertices, while the implementation might default to 0-based. Ensure consistency within the specified range of vertices.
Prim's Algorithm Implementation
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
const int MAX_VERTICES = 105;
const int INFINITY = 0x3fffffff;
struct Edge {
int to_vertex;
int weight;
Edge(int v, int w) : to_vertex(v), weight(w) {}
};
int num_vertices;
std::vector<Edge> adjacencyList[MAX_VERTICES];
bool visited[MAX_VERTICES];
int min_distance[MAX_VERTICES];
int primMST() {
std::fill(min_distance, min_distance + MAX_VERTICES, INFINITY);
min_distance[1] = 0; // Start from vertex 1
int total_weight = 0;
for (int i = 0; i < num_vertices; ++i) {
int current_vertex = -1;
int min_weight = INFINITY;
// Find the nearest unvisited vertex
for (int j = 1; j <= num_vertices; ++j) {
if (!visited[j] && min_distance[j] < min_weight) {
current_vertex = j;
min_weight = min_distance[j];
}
}
if (current_vertex == -1) {
return -1; // Graph is not connected
}
visited[current_vertex] = true;
total_weight += min_weight;
// Update distances for adjacent vertices
for (const auto& edge : adjacencyList[current_vertex]) {
int neighbor = edge.to_vertex;
if (!visited[neighbor] && edge.weight < min_distance[neighbor]) {
min_distance[neighbor] = edge.weight;
}
}
}
return total_weight;
}
int main() {
int vertex_a, vertex_b, edge_weight;
while (scanf("%d", &num_vertices) && num_vertices) {
for (int i = 1; i <= num_vertices; ++i) {
adjacencyList[i].clear();
}
std::fill(visited, visited + MAX_VERTICES, false);
int num_edges = num_vertices * (num_vertices - 1) / 2;
for (int i = 0; i < num_edges; ++i) {
scanf("%d %d %d", &vertex_a, &vertex_b, &edge_weight);
adjacencyList[vertex_a].push_back(Edge(vertex_b, edge_weight));
adjacencyList[vertex_b].push_back(Edge(vertex_a, edge_weight));
}
int mst_weight = primMST();
if (mst_weight > 0) {
printf("%d\n", mst_weight);
}
}
return 0;
}
Kruskal's Algorithm for Sparse Graphs
Kruskal's algorithm is generally preferred for sparse graphs. Its time complexity is O(E log E) due to the initial sorting of edges.
Kruskal's Algorithm Implementation
#include <cstdio>
#include <algorithm>
const int MAX_EDGES = 5000;
const int MAX_VERTICES = 105;
struct Edge {
int from_vertex;
int to_vertex;
int weight;
} edges[MAX_EDGES];
int parent[MAX_VERTICES];
// Find the representative of the set containing x (with path compression)
int findSet(int x) {
if (x == parent[x]) {
return x;
} else {
int root = findSet(parent[x]);
parent[x] = root; // Path compression
return root;
}
}
// Kruskal's algorithm to find MST weight
int kruskalMST(int num_vertices, int num_edges) {
int mst_weight = 0;
int edges_in_mst = 0;
// Initialize parent array for disjoint sets
for (int i = 1; i <= num_vertices; ++i) {
parent[i] = i;
}
// Sort edges by weight in ascending order
std::sort(edges, edges + num_edges, [](const Edge& a, const Edge& b) {
return a.weight < b.weight;
});
// Iterate through sorted edges
for (int i = 0; i < num_edges; ++i) {
int root_u = findSet(edges[i].from_vertex);
int root_v = findSet(edges[i].to_vertex);
// If adding this edge does not form a cycle
if (root_u != root_v) {
parent[root_u] = root_v; // Union the sets
mst_weight += edges[i].weight;
edges_in_mst++;
if (edges_in_mst == num_vertices - 1) {
break; // MST is complete
}
}
}
if (edges_in_mst != num_vertices - 1) {
return -1; // Graph is not connected
} else {
return mst_weight;
}
}
int main() {
int num_vertices, num_edges, u, v, weight;
while (scanf("%d", &num_vertices) && num_vertices) {
num_edges = num_vertices * (num_vertices - 1) / 2;
for (int i = 0; i < num_edges; ++i) {
scanf("%d %d %d", &edges[i].from_vertex, &edges[i].to_vertex, &edges[i].weight);
}
int mst_weight = kruskalMST(num_vertices, num_edges);
if (mst_weight != -1) {
printf("%d\n", mst_weight);
}
}
return 0;
}
Calculating Edge Weights from Coordinates
For problems where edge weights are not directly provided but can be derived from coordinates (e.g., Euclidean distance), calculate the distance between points (x1, y1) and (x2, y2) using the formula sqrt((x1-x2)^2 + (y1-y2)^2).
In such cases, the graph is typically complete, meaning every pair of vertices has an edge. The number of edges is C(n, 2) = n(n-1)/2, making Kruskal's algorithm a suitable choice.
MST with Cooordinate-Based Weights (Kruskal's)
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
const int MAX_VERTICES = 105;
const int MAX_EDGES = 5000;
struct Point {
double x;
double y;
} vertices_coords[MAX_VERTICES];
struct Edge {
int from_vertex;
int to_vertex;
double weight;
} edges[MAX_EDGES];
int parent[MAX_VERTICES];
int findSet(int x) {
if (x == parent[x]) {
return x;
} else {
int root = findSet(parent[x]);
parent[x] = root;
return root;
}
}
double kruskalMSTCoordinate(int num_vertices, int num_edges) {
double mst_total_weight = 0;
int edges_count = 0;
for (int i = 0; i < num_vertices; ++i) {
parent[i] = i;
}
std::sort(edges, edges + num_edges, [](const Edge& a, const Edge& b) {
return a.weight < b.weight;
});
for (int i = 0; i < num_edges; ++i) {
int root_u = findSet(edges[i].from_vertex);
int root_v = findSet(edges[i].to_vertex);
if (root_u != root_v) {
parent[root_u] = root_v;
mst_total_weight += edges[i].weight;
edges_count++;
if (edges_count == num_vertices - 1) {
break;
}
}
}
if (edges_count != num_vertices - 1) {
return -1.0; // Not connected
} else {
return mst_total_weight;
}
}
int main() {
int num_vertices;
while (scanf("%d", &num_vertices) && num_vertices) {
for (int i = 0; i < num_vertices; ++i) {
scanf("%lf %lf", &vertices_coords[i].x, &vertices_coords[i].y);
}
int edge_index = 0;
int num_possible_edges = num_vertices * (num_vertices - 1) / 2;
for (int i = 0; i < num_vertices - 1; ++i) {
for (int j = i + 1; j < num_vertices; ++j) {
edges[edge_index].from_vertex = i;
edges[edge_index].to_vertex = j;
edges[edge_index].weight = std::sqrt(std::pow(vertices_coords[i].x - vertices_coords[j].x, 2) + std::pow(vertices_coords[i].y - vertices_coords[j].y, 2));
edge_index++;
}
}
double mst_weight = kruskalMSTCoordinate(num_vertices, edge_index);
if (mst_weight != -1.0) {
printf("%.2lf\n", mst_weight);
}
}
return 0;
}
Handling Pre-existing Edges in MST
In scenarios where some connections are already established, these existing paths contribute to the count of edges needed for an MST (n-1 edges) but do not add to the total cost. When applying Kruskal's algorithm, these pre-existing edges are processed first, and if they connect two previously disconnected components, they increment the edge_count without adding their weight to the mst_weight.
Kruskal's with Pre-existing Edges
#include <cstdio>
#include <algorithm>
const int MAX_VERTICES = 105;
const int MAX_EDGES = 5000;
struct Edge {
int from_vertex;
int to_vertex;
int weight;
} edges[MAX_EDGES];
int parent[MAX_VERTICES];
int current_edge_count;
int findSet(int x) {
if (x == parent[x]) {
return x;
} else {
int root = findSet(parent[x]);
parent[x] = root;
return root;
}
}
int kruskalMSTWithExisting(int num_vertices, int num_potential_edges) {
int mst_weight = 0;
current_edge_count = 0;
for (int i = 1; i <= num_vertices; ++i) {
parent[i] = i;
}
std::sort(edges, edges + num_potential_edges, [](const Edge& a, const Edge& b) {
return a.weight < b.weight;
});
for (int i = 0; i < num_potential_edges; ++i) {
int root_u = findSet(edges[i].from_vertex);
int root_v = findSet(edges[i].to_vertex);
if (root_u != root_v) {
parent[root_u] = root_v;
current_edge_count++;
mst_weight += edges[i].weight;
if (current_edge_count == num_vertices - 1) {
break;
}
}
}
if (current_edge_count != num_vertices - 1) {
return -1;
} else {
return mst_weight;
}
}
int main() {
int num_vertices, num_potential_edges, u, v, weight, is_preexisting;
while (scanf("%d", &num_vertices) && num_vertices) {
num_potential_edges = num_vertices * (num_vertices - 1) / 2;
current_edge_count = 0;
for (int i = 1; i <= num_vertices; ++i) {
parent[i] = i;
}
for (int i = 0; i < num_potential_edges; ++i) {
scanf("%d %d %d %d", &edges[i].from_vertex, &edges[i].to_vertex, &edges[i].weight, &is_preexisting);
if (is_preexisting) {
int root_u = findSet(edges[i].from_vertex);
int root_v = findSet(edges[i].to_vertex);
if (root_u != root_v) {
parent[root_u] = root_v;
current_edge_count++;
}
}
}
int mst_weight = kruskalMSTWithExisting(num_vertices, num_potential_edges);
if (mst_weight != -1) {
printf("%d\n", mst_weight);
}
}
return 0;
}
MST with Named Vertices and Edge Inputs
This problem variant introduces named vertices (using capital letters) and a specific input format. Vertices are represented by characters 'A' through 'Z'. To simplify processing, character vertex names can be mapped to integer indices (e.g., char - 'A'). This avoids using more complex data structures like std::map for the disjoint set union (DSU) parent array.
Kruskal's Algorithm with Character Vertices
#include <cstdio>
#include <algorithm>
#include <iostream>
const int MAX_VERTICES = 30;
const int MAX_EDGES = 80;
struct Edge {
int from_vertex;
int to_vertex;
int weight;
} edges[MAX_EDGES];
int parent[MAX_VERTICES];
int findSet(int x) {
if (x == parent[x]) {
return x;
} else {
int root = findSet(parent[x]);
parent[x] = root;
return root;
}
}
bool compareEdges(const Edge& a, const Edge& b) {
return a.weight < b.weight;
}
int kruskalMSTCharVertices(int num_vertices, int num_edges) {
int mst_weight = 0;
int edges_in_mst = 0;
for (int i = 0; i < num_vertices; ++i) {
parent[i] = i;
}
std::sort(edges, edges + num_edges, compareEdges);
for (int i = 0; i < num_edges; ++i) {
int root_u = findSet(edges[i].from_vertex);
int root_v = findSet(edges[i].to_vertex);
if (root_u != root_v) {
parent[root_u] = root_v;
mst_weight += edges[i].weight;
edges_in_mst++;
if (edges_in_mst == num_vertices - 1) {
break;
}
}
}
if (edges_in_mst != num_vertices - 1) {
return -1;
} else {
return mst_weight;
}
}
int main() {
int num_vertices, num_connections, edge_weight;
char vertex_char, connected_vertex_char;
while (scanf("%d", &num_vertices) && num_vertices) {
int edge_index = 0;
for (int i = 0; i < num_vertices - 1; ++i) {
std::cin >> vertex_char >> num_connections;
while (num_connections--) {
std::cin >> connected_vertex_char >> edge_weight;
edges[edge_index].from_vertex = vertex_char - 'A';
edges[edge_index].to_vertex = connected_vertex_char - 'A';
edges[edge_index].weight = edge_weight;
edge_index++;
}
}
int mst_weight = kruskalMSTCharVertices(num_vertices, edge_index);
if (mst_weight != -1) {
printf("%d\n", mst_weight);
}
}
return 0;
}