⑥ 使用 Prime 算法(或者 Kruskal 算法)从某个指定的顶点出发输出图 G 的 最小生成树；（要求把最小生成树的各条边输出成 A-B-wight,或者 (A,B,weight)的形式）；用C语言实现

以下是使用Kruskal算法从指定顶点出发输出图G的最小生成树的C语言实现，输出格式为(A,B,weight)：

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

#define MAX_VERTICES 100
#define MAX_EDGES 100

typedef struct {
    int u, v, weight;
} Edge;

int parent[MAX_VERTICES];
Edge edges[MAX_EDGES];

int find(int i) {
    while (parent[i] >= 0) {
        i = parent[i];
    }
    return i;
}

void unionSet(int i, int j) {
    if (parent[i] < parent[j]) {
        parent[i] += parent[j];
        parent[j] = i;
    } else {
        parent[j] += parent[i];
        parent[i] = j;
    }
}

void kruskal(int n, int m, int start) {
    int i, j, k;
    int numEdges = 0;
    int minWeight = 0;
    Edge minEdge;
    for (i = 0; i < n; i++) {
        parent[i] = -1;
    }
    for (i = 0; i < m; i++) {
        if (edges[i].u == start || edges[i].v == start) {
            // 只考虑从指定顶点出发的边
            continue;
        }
        edges[i].weight *= -1;  // 将边权取相反数，以便使用最大堆
    }
    // 使用最大堆存储边
    Heap *heap = createHeap(m, greater);
    for (i = 0; i < m; i++) {
        if (edges[i].u == start || edges[i].v == start) {
            continue;
        }
        insert(heap, edges[i]);
    }
    while (numEdges < n - 1) {
        if (isEmpty(heap)) {
            printf("The graph is not connected.\n");
            return;
        }
        minEdge = deleteRoot(heap);
        minEdge.weight *= -1;  // 恢复边权
        i = find(minEdge.u);
        j = find(minEdge.v);
        if (i != j) {
            printf("(%d,%d,%d) ", minEdge.u, minEdge.v, minEdge.weight);
            unionSet(i, j);
            numEdges++;
            minWeight += minEdge.weight;
        }
    }
    printf("\nThe total weight of the minimum spanning tree is %d.\n", minWeight);
}

int main() {
    int n, m, start, i;
    printf("Enter the number of vertices and edges of the graph: ");
    scanf("%d%d", &n, &m);
    printf("Enter the edges of the graph: ");
    for (i = 0; i < m; i++) {
        scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].weight);
    }
    printf("Enter the starting vertex: ");
    scanf("%d", &start);
    kruskal(n, m, start);
    return 0;
}

注意，上述代码使用了一个最大堆实现了Kruskal算法，以便处理边权取相反数后的最小值。如果不想使用最大堆，可以在输入边时将边权取相反数，然后在输出时再将边权恢复即可。