I have been making an algorithm that builds a Minimum Spanning Tree where I insert the number of cities (vertexes), airports (edges connecting to a "sky" vertex - vertex 0) and the number of roads (edges connected to other cities).
I then insert the city the airport (source vertex) is built and the cost (edge cost). After this, I insert the cities connected by roads (source and destiny vertexes) and the cost (edge cost).
The outputs are the MST cost, the number of airports and number of roads.
I already have these mechanisms working but they are a bit buggy. I can't seem to fix these issues.
Also, I was wondering if I can make a function that detects if the undirected graph in the MST is connected (all vertexes are connected). If the function detects that the MST is not connected, the program should output "Insuficient information.".
Full code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// A structure to represent a weighted edge in graph.
struct Edge {
int src, dest, weight;
};
// A structure to represent a connected, undirected and weighted graph.
struct Graph {
// V -> Vertex Number (Number of cities), E -> Number of edges (Number of roads + airport connections).
int V;
int E;
// The graph is represented as an array of edges.
// Since the graph is undirected, the edge
// from src to dest is also edge from dest
// to src. Both are counted as 1 edge here.
struct Edge* edge;
};
// Creates a graph with V vertexes and E edges.
struct Graph* createGraph(int V, int E)
{
struct Graph* graph = malloc(sizeof *graph);
graph->V = V;
graph->E = E;
graph->edge = (struct Edge*)malloc(E * sizeof(struct Edge));
return graph;
};
// A structure to represent a subset for union-find.
struct subset {
int parent;
int rank;
};
// A utility function to find set of an element (uses path compression technique).
int find(struct subset subsets[], int i)
{
// Find root and make root as parent of i (uses path compression technique).
if (subsets[i].parent != i)
subsets[i].parent
= find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// A function that does union of two sets of x and y (uses union by rank).
void Union(struct subset subsets[], int x, int y)
{
int xroot = find(subsets, x);
int yroot = find(subsets, y);
// Attach smaller rank tree under root of high rank tree (Union by Rank).
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
// If ranks are same, then make one as root and increment its rank by one.
else
{
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
// Compare two edges according to their weights.
// Used in qsort() for sorting an array of edges.
int myComp(const void* a, const void* b)
{
struct Edge* a1 = (struct Edge*)a;
struct Edge* b1 = (struct Edge*)b;
if (a1->weight > b1->weight) {
return a1->weight > b1->weight;
}
if (a1->weight < b1->weight) {
return a1->weight < b1->weight;
}
if (a1->weight == b1->weight) {
return a1->weight == b1->weight;
}
}
// The main function to construct MST using Kruskal's algorithm.
void KruskalMST(struct Graph* graph)
{
int V = graph->V;
struct Edge
result[V]; // Saves the resulting MST.
int e = 0; // An index variable, used for result[].
int i = 0; // An index variable, used for sorted edges.
// Step 1: Sort all the edges in non-decreasing order of their weight.
// If we are not allowed to change the given graph, we can create a copy of array of edges.
qsort(graph->edge, graph->E, sizeof(graph->edge[0]),
myComp);
// Allocate memory for creating V ssubsets.
struct subset* subsets
= (struct subset*)malloc(V * sizeof(struct subset));
// Create V subsets with single elements.
for (int v = 0; v < V; ++v) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
// Number of edges to be taken is equal to V-1.
while (e < V - 1 && i < graph->E) {
// Step 2: Pick the smallest edge.
// And increment the index for next iteration.
struct Edge next_edge = graph->edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
// If including this edge does't cause cycle,
// include it in result and increment the index
// of result for next edge.
if (x != y) {
result[e++] = next_edge;
Union(subsets, x, y);
}
// Else discard the next_edge.
}
int minimumCost = 0;
int nRoads = 0;
int nAirports = 0;
for (i = 0; i < e; ++i)
{
if (result[i].dest == 0) {
nAirports++;
} else {
nRoads++;
}
minimumCost += result[i].weight;
}
printf("Minimum Spanning Tree with minimal cost: %d\n",minimumCost);
printf("Number of airports: %d\n",nAirports);
printf("Number of roads: %d",nRoads);
return;
}
int main()
{
int v = 0; // Number of vertexes(cities) in the graph (includes the "sky" vertex).
int a = 0; // Number of airports.
int edges = 0; // Number of roads.
int e = 0; // Number Total number of edges in the graph.
int city = 0;
int airport = 0;
int city1 = 0;
int city2 = 0;
int cost = 0;
printf("Input the number of cities: \n");
scanf("%d", &v);
printf("Input the number of airports: \n");
scanf("%d", &a);
printf("Input the number of roads: \n");
scanf("%d", &e);
edges = a + e;
if (a > 0) {
v = v + 1;
}
struct Graph* graph = createGraph(v, edges);
for (int i = 0; i < a; i++) {
printf("Input the city and the building cost of the airport: \n");
scanf("%d %d", &city, &airport);
graph->edge[i].src = city;
graph->edge[i].dest = 0; // "sky" vertex.
graph->edge[i].weight = airport;
}
for (int j = a; j < edges; j++) {
printf("Input the cities and the cost of the road: \n");
scanf("%d %d %d", &city1, &city2, &cost);
if (a == 0) {
graph->edge[j].src = city1 - 1;
graph->edge[j].dest = city2 - 1;
graph->edge[j].weight = cost;
} else {
graph->edge[j].src = city1;
graph->edge[j].dest = city2;
graph->edge[j].weight = cost;
}
}
KruskalMST(graph);
return 0;
}
Example of a bug - 0 airports declared but still counts an airport:
Input the number of cities:
4
Input the number of airports:
0
Input the number of roads:
4
Input the cities and the cost of the road:
1 2 1
Input the cities and the cost of the road:
2 3 2
Input the cities and the cost of the road:
3 4 1
Input the cities and the cost of the road:
4 1 1
Minimum Spanning Tree with minimal cost: 3
Number of airports: 1
Number of roads: 2
The expected number of airports should be 0.