C语言写出，用贪心法求解无向图的最小生成树，要求有输入。

在C语言中，我们可以使用Kruskal算法（一种贪心算法），也称为最小生成树算法，来找到无向图的最小生成树。这个算法的基本思想是每次选择当前图中最短的边，直到所有顶点都连接在一起形成一棵树。以下是简单的C语言代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

#define V 9 // 图的顶点数

// 边的结构体表示
typedef struct {
    int u, v; // 邻接点
    int weight; // 权重
} Edge;

// 比较两个边的权重
bool compareEdges(Edge e1, Edge e2) {
    return e1.weight < e2.weight;
}

// 使用优先队列存放边
struct MinHeap {
    Edge* heap[V];
    int size;
};

// 插入元素到堆中
void insertMinHeap(struct MinHeap* minHeap, Edge new_edge) {
    minHeap->heap[minHeap->size++] = new_edge;
    // 保持堆的性质
    bubbleUp(minHeap, minHeap->size - 1);
}

// 将节点i下沉至其子节点满足堆的性质
void bubbleUp(struct MinHeap* minHeap, int i) {
    while (i > 0 && minHeap->heap[parent(i)].weight > minHeap->heap[i].weight) {
        swap(minHeap->heap[i], minHeap->heap[parent(i)]);
        i = parent(i);
    }
}

// 找出堆顶元素并删除它
Edge extractMin(struct MinHeap* minHeap) {
    if (minHeap->size == 0)
        return {-1, -1, 0}; // 空堆

    Edge smallest = minHeap->heap[0];
    minHeap->heap[0] = minHeap->heap[--minHeap->size]; // 移动最后一个元素到堆顶
    bubbleDown(minHeap, 0); // 保持堆的性质

    return smallest;
}

// 主函数实现Kruskal算法
int kruskalMST(int graph[V][V], int vertices) {
    struct MinHeap minHeap;
    for (int i = 0; i < vertices; ++i)
        minHeap.heap[i] = {i, -1, graph[i][i]}; // 初始化每个节点为孤立状态

    int edges_count = 0;
    bool edge_used[V * V] = {false}; // 标记已使用的边

    while (edges_count < vertices - 1) {
        Edge currentEdge = extractMin(&minHeap);

        // 如果这条边已经在最小生成树中，则跳过
        if (currentEdge.u != -1 && !edge_used[currentEdge.u * V + currentEdge.v]) {
            insertEdgeIntoUnion(currentEdge.u, currentEdge.v); // 合并边所连接的集合
            edge_used[currentEdge.u * V + currentEdge.v] = true;
            edges_count++;
        }
    }

    printf("Minimum spanning tree edges (Weight, Node1, Node2):\n");
    for (int i = 0; i < vertices; ++i) {
        if (graph[i][i] != 0) {
            printf("%d %d %d\n", graph[i][i], i, find(i));
        }
    }

    return edges_count;
}

// 查找给定节点属于哪棵树
int find(int node) {
    return node; // 无环的情况下，根节点就是自身
    // 如果需要考虑连通分量，可以使用更复杂的数据结构如邻接矩阵或数组
}

// 添加一条边到并查集
void insertEdgeIntoUnion(int u, int v) {
    u = root(u); // 转换为根节点
    v = root(v); // 转换为根节点

    if (u != v) {
        // 将较小的集合合并到较大的集合中
        if (unionSetSize[u] < unionSetSize[v])
            swap(u, v);

        graph[u][v] = graph[v][u] = unionSetSize[u]; // 更新邻接矩阵
        unionSetSize[u] += unionSetSize[v];
    }
}

// 获取节点所在的集合大小
int unionSetSize[V];

// 初始化并查集大小
void initSets() {
    for (int i = 0; i < V; ++i)
        unionSetSize[i] = 1;
}

int main() {
    int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                       {4, 0, 8, 0, 0, 0, 0, 11, 0},
                       {0, 8, 0, 7, 0, 4, 0, 0, 2},
                       {0, 0, 7, 0, 9, 14, 0, 0, 0},
                       {0, 0, 0, 9, 0, 10, 0, 0, 0},
                       {0, 0, 4, 14, 10, 0, 2, 0, 0},
                       {0, 0, 0, 0, 0, 2, 0, 1, 6},
                       {8, 11, 0, 0, 0, 0, 1, 0, 7},
                       {0, 0, 2, 0, 0, 0, 6, 7, 0}};
    initSets();
    int vertices = sizeof(graph) / sizeof(graph[0]);
    kruskalMST(graph, vertices);
    return 0;
}