用c语言最小生成树写出小区光缆铺设

在C语言中，我们可以使用克鲁斯卡尔(Kruskal's Algorithm)或普里姆 Prim's Algorithm 来实现最小生成树算法，这对于小区光缆铺设这类问题非常合适，因为它需要找出最小代价的连接方式来覆盖所有的建筑物。

以克鲁斯卡尔算法为例，这里提供一个简单的C语言版本示例：

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

typedef struct Edge {
    int u, v; // 节点编号
    int weight; // 边的权重
} Edge;

bool compareEdges(const Edge *e1, const Edge *e2) {
    return e1->weight < e2->weight;
}

int kruskal(int vertices, Edge* edges) {
    int result = 0, i;
    Edge sortedEdges[vertices * (vertices - 1) / 2]; // 最小边的数量

    for(i = 0; i < vertices * (vertices - 1) / 2; i++) {
        sortedEdges[i] = edges[i];
    }

    qsort(sortedEdges, vertices * (vertices - 1) / 2, sizeof(Edge), compareEdges);

    bool visited[vertex + 1]; // 标记数组
    for(i = 0; i <= vertices; i++)
        visited[i] = false;

    for(i = 0; i < vertices * (vertices - 1) / 2; i++) {
        int u = sortedEdges[i].u, v = sortedEdges[i].v;
        if(!visited[u] && !visited[v]) {
            // 添加到最小生成树
            printf("Adding edge %d-%d with weight %d\n", u, v, sortedEdges[i].weight);
            result += sortedEdges[i].weight;
            visited[u] = true;
            visited[v] = true;
        }
    }
    return result;
}

int main() {
    int numVertices, numEdges, i;
    printf("Enter number of vertices: ");
    scanf("%d", &numVertices);
    Edge* edges = (Edge*)malloc(numVertices * numVertices * sizeof(Edge)); // 假设输入的边数足够
    printf("Enter number of edges and their weights:\n");
    for(i = 0; i < numEdges; i++) {
        scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].weight);
    }
    int totalCost = kruskal(numVertices, edges);
    free(edges);
    printf("Total cost of minimum spanning tree is %d.\n", totalCost);
    return 0;
}

在这个程序中，用户首先输入小区内的节点数量和每条光缆的起始点和权重，然后程序会按照克鲁斯卡尔算法找到最小生成树并输出总成本。