1、采用Prim算法求取图的最小生成树。 2、输出求出的最小生成树 用c语言写代码

Prim算法是一种用于寻找无向加权图中最小生成树的贪心算法。以下是基本步骤：

1. 选择任意一个顶点作为起始点，将其加入到已选集合中，并初始化当前树的总权重为0。
2. 对于未选集合中的每一个边（u, v），如果这条边连接的两个顶点中，u已经在已选集合内，而v不在，就计算这条边的权重并更新当前树的总权重，然后将v添加到已选集合中。
3. 重复步骤2，直到所有顶点都被选入已选集合，或者无法再找到连接已选集合和未选集合的边。

对于C语言实现，这里是一个简单的版本（假设图是邻接矩阵表示，`w[i][j]`表示(i,j)之间的边的权重）：

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

// 图的邻接矩阵存储
#define V 9 // 代表图中的顶点数，可以替换为实际值
int w[V][V];

// 边结构体，包含起点、终点和权重
typedef struct Edge {
    int src;
    int dest;
    int weight;
} Edge;

// 较小的边函数
int min_edge(int src, int mstSet[]) {
    int min = INT_MAX;
    int min_index = -1;

    for (int v = 0; v < V; v++) {
        if (!mstSet[v] && w[src][v] <= min) {
            min = w[src][v];
            min_index = v;
        }
    }

    return min_index;
}

// Prim's Algorithm
void prim_mst() {
    int mstSet[V]; // 存储是否已经添加到最小生成树的标志
    int key[V], parent[V]; // 记录关键值和每个顶点的父亲

    // 初始化
    memset(mstSet, 0, sizeof(mstSet));
    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
    }
    key[0] = 0; // 将起始点的键设为0

    for (int count = 0; count < V - 1; count++) { // 遍历V次
        int u = min_edge(0, mstSet);
        mstSet[u] = 1; // 标记当前顶点已经被添加到最小生成树

        printf("Edge %d - %d with weight %d\n", u, parent[u], w[u][parent[u]]); // 输出一条边及其权重
        for (int v = 0; v < V; v++) {
            if (!mstSet[v] && w[u][v] < key[v]) {
                key[v] = w[u][v];
                parent[v] = u; // 更新父节点
            }
        }
    }
}

int main() {
    // 填充邻接矩阵w和调用prim_mst()
    prim_mst();

    return 0;
}

注意：这个代码示例适用于图的规模较小的情况，实际应用中可能需要优化，特别是当图的大小增加时。此外，上述代码仅用于演示，未处理可能出现的错误情况，如负权边等。在实际项目中，应确保输入的合法性并进行适当的错误检查。