C言語によるクラスカル法の実装解説：貪欲アルゴリズムで最小全域木(MST)を生成する方法

#include <stdio.h>
#include <stdlib.h>
typedef struct {
    int from;
    int to;
    int weight;
} Edge;

#include <stdio.h>
#include <stdlib.h>
int main(void) {
    int numVertices, numEdges;
    // 例として、標準入力から頂点数と辺数を読み込みます
    scanf("%d %d", &numVertices, &numEdges);
    // エッジ情報を保存するための配列を確保する
    Edge* edges = (Edge*)malloc(numEdges * sizeof(Edge));
    if (edges == NULL) {
        printf("エッジ配列のメモリ確保に失敗しました\n");
        return 1;
    }
    // ここで入力により各辺の情報を取得する処理を追加
    free(edges);
    return 0;
}

(サンプル入力に応じた出力が表示されます)

#include <stdio.h>
#include <stdlib.h>
int compareEdge(const void* a, const void* b) {
    Edge* edgeA = (Edge*)a;
    Edge* edgeB = (Edge*)b;
    return edgeA->weight - edgeB->weight;
}

#include <stdio.h>
#include <stdlib.h>
int find(int* parent, int vertex) {
    if (parent[vertex] != vertex) {
        parent[vertex] = find(parent, parent[vertex]);  // パス圧縮
    }
    return parent[vertex];
}

#include <stdio.h>
#include <stdlib.h>
void unionSets(int* parent, int* rank, int vertex1, int vertex2) {
    int root1 = find(parent, vertex1);
    int root2 = find(parent, vertex2);
    if (root1 == root2) return;
    // ランクが低い方を高い方に結合
    if (rank[root1] < rank[root2]) {
        parent[root1] = root2;
    } else if (rank[root1] > rank[root2]) {
        parent[root2] = root1;
    } else {
        parent[root2] = root1;
        rank[root1]++;
    }
}

#include <stdio.h>
#include <stdlib.h>
typedef struct {
    int from;
    int to;
    int weight;
} Edge;
int compareEdge(const void* a, const void* b) {
    Edge* edgeA = (Edge*)a;
    Edge* edgeB = (Edge*)b;
    return edgeA->weight - edgeB->weight;
}
int find(int* parent, int vertex) {
    if (parent[vertex] != vertex) {
        parent[vertex] = find(parent, parent[vertex]);  // パス圧縮
    }
    return parent[vertex];
}
void unionSets(int* parent, int* rank, int vertex1, int vertex2) {
    int root1 = find(parent, vertex1);
    int root2 = find(parent, vertex2);
    if (root1 == root2) return;
    if (rank[root1] < rank[root2]) {
        parent[root1] = root2;
    } else if (rank[root1] > rank[root2]) {
        parent[root2] = root1;
    } else {
        parent[root2] = root1;
        rank[root1]++;
    }
}
int main(void) {
    int numVertices, numEdges;
    // 頂点数と辺数を読み込み
    scanf("%d %d", &numVertices, &numEdges);
    // エッジ情報の配列を確保
    Edge* edges = (Edge*)malloc(numEdges * sizeof(Edge));
    if (edges == NULL) {
        printf("メモリ確保エラー\n");
        return 1;
    }
    // 各エッジの情報を入力
    for (int i = 0; i < numEdges; i++) {
        scanf("%d %d %d", &edges[i].from, &edges[i].to, &edges[i].weight);
    }
    // エッジのソート
    qsort(edges, numEdges, sizeof(Edge), compareEdge);
    // Union-Find 用の配列を初期化
    int* parent = (int*)malloc(numVertices * sizeof(int));
    int* rank = (int*)malloc(numVertices * sizeof(int));
    if (parent == NULL || rank == NULL) {
        printf("メモリ確保エラー\n");
        return 1;
    }
    for (int i = 0; i < numVertices; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
    // MSTの構築
    int mstWeight = 0;
    for (int i = 0; i < numEdges; i++) {
        int root1 = find(parent, edges[i].from);
        int root2 = find(parent, edges[i].to);
        if (root1 != root2) {  // サイクルが形成されなければ採用
            mstWeight += edges[i].weight;
            unionSets(parent, rank, root1, root2);
        }
    }
    printf("最小全域木の重み: %d\n", mstWeight);
    free(edges);
    free(parent);
    free(rank);
    return 0;
}

(入力に応じた最小全域木の合計重量が表示されます)