#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
typedef struct {
int start;
int end;
int weight;
} Edge;
typedef struct {
Edge edges[MAX_VERTICES * MAX_VERTICES];
int numEdges;
} Graph;
void initGraph(Graph* g) {
g->numEdges = 0;
}
void addEdge(Graph* g, int start, int end, int weight) {
g->edges[g->numEdges].start = start;
g->edges[g->numEdges].end = end;
g->edges[g->numEdges].weight = weight;
g->numEdges++;
}
int compareEdges(const void* a, const void* b) {
return ((Edge*)a)->weight - ((Edge*)b)->weight;
}
int find(int parent[], int i) {
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
void Union(int parent[], int x, int y) {
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
void kruskalMST(Graph* g)
{ Edge result[g->numEdges];
int e = 0;
int i = 0;
qsort(g->edges, g->numEdges, sizeof(g->edges[0]), compareEdges);
int parent[MAX_VERTICES];
for (int v = 0; v < MAX_VERTICES; v++)
parent[v] = -1;
while (e < MAX_VERTICES - 1 && i < g->numEdges)
{ Edge nextEdge = g->edges[i++];
int x = find(parent, nextEdge.start);
int y = find(parent, nextEdge.end);
if (x != y) {
result[e++] = nextEdge; Union(parent, x, y);
}
}
printf("Edges in the minimum cost spanning tree:\n");
for (i = 0; i < e; i++) {
printf("(%d - %d) Weight: %d\n", result[i].start, result[i].end, result[i].weight);
}
}
int main()
{ Graph g; initGraph(&g);
int V;
printf("Enter the number of vertices: ");
scanf("%d", &V);
int graph[MAX_VERTICES][MAX_VERTICES];
printf("Enter the adjacency matrix for the graph:\n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
scanf("%d", &graph[i][j]);
// Assuming -1 for absence of edge, non-negative weights for edges
if (graph[i][j] != -1) {
addEdge(&g, i, j, graph[i][j]);
}
}
}
kruskalMST(&g);
return 0;
}
0 Comments