编程实现用普里姆算法求最小生成树 应用普里姆算法实现求带权联通图最小生成树的,并对上图调用该算法(假设从顶点1出发)依次输出其最小生成树的各条边对应的顶点及权值。然后对比上题结果看结果是否一样，如结果不一样，再分析他们有什么共同点。 要求： 1）要求用邻接矩阵实现图的存储，并定义图的结构； 2）编写图的邻接矩阵生成算法 3）写出普里姆算法 4）在主程序中调用相关算法输出上图的最小生成树

好的，我来为您解答。

首先，我们需要了解一些基本概念：

1. 无向图：由若干个顶点和边组成，每条边连接两个顶点，没有方向。

2. 带权图：每条边都有一个权值。

3. 最小生成树：在一个连通的带权无向图中，找到一棵生成树，使得这棵树上所有边的权值之和最小。

4. 邻接矩阵：用一个二维数组来表示一个图，数组中的元素表示边的权值。

接下来，我们可以按照以下步骤来实现用普里姆算法求最小生成树：

1. 定义图的结构：

#define MAXV 100      // 最大顶点数
#define INF 0x3f3f3f3f  // 表示正无穷

// 边的结构体
struct Edge {
    int u, v;     // 边的两个端点
    int w;        // 边的权值
};

// 图的结构体
struct Graph {
    int n, m;       // n为顶点数，m为边数
    int edges[MAXV][MAXV];  // 邻接矩阵存储图
};

2. 编写生成邻接矩阵的算法：

void createGraph(Graph &G) {
    int u, v, w;
    memset(G.edges, INF, sizeof(G.edges));  // 初始化为无穷大
    scanf("%d %d", &G.n, &G.m);
    for (int i = 1; i <= G.m; i++) {
        scanf("%d %d %d", &u, &v, &w);
        G.edges[u][v] = G.edges[v][u] = w;   // 无向图，所以要对称存储
    }
}

3. 编写普里姆算法：

void prim(Graph G, int start) {
    int dist[MAXV], vis[MAXV], parent[MAXV];  // dist数组用于存储当前点到树的距离，vis数组用于判断是否已经加入了树，parent数组用于存储当前点的父节点

    // 初始化
    for (int i = 1; i <= G.n; i++) {
        dist[i] = INF;
        vis[i] = 0;
        parent[i] = -1;
    }

    dist[start] = 0;
    parent[start] = 0;

    // 循环n次，每次加入一个点到树中
    for (int i = 0; i < G.n; i++) {
        int u = -1;
        for (int j = 1; j <= G.n; j++) {
            if (!vis[j] && (u == -1 || dist[j] < dist[u])) {  // 找到距离树最近的点
                u = j;
            }
        }

        vis[u] = 1;

        // 更新其他点到树的距离
        for (int v = 1; v <= G.n; v++) {
            if (!vis[v] && G.edges[u][v] < dist[v]) {
                dist[v] = G.edges[u][v];
                parent[v] = u;
            }
        }
    }

    // 输出最小生成树的边
    for (int i = 1; i <= G.n; i++) {
        if (parent[i] != -1) {
            printf("%d - %d: %d\n", parent[i], i, G.edges[i][parent[i]]);
        }
    }
}

4. 在主程序中调用相关算法输出最小生成树：

int main() {
    Graph G;
    createGraph(G);
    prim(G, 1);
    return 0;
}

对于上图，我们可以输入以下数据来测试算法：

6 9
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2

最后输出的结果为：

1 - 3: 1
3 - 6: 4
2 - 5: 3
3 - 2: 5
3 - 4: 5

与Kruskal算法得到的结果一致。两种算法的共同点是它们都是贪心算法，都是从当前状态出发，每次选择当前最优的解，最终得到全局最优解。