对于连接矩阵A, 元素A[i][j]表示无向图G中以i和j为顶点的边的长度。若A的数值如下，则图G的最小生成树中各边的长度和为 1 {0, 1, 2, 3, 4, 5} {1, 0, 2, 4, 3, 3} {2, 2, 0, 5, 2, 4} {3, 4, 5, 0, 1, 3} {4, 3, 2, 1, 0, 2} {5, 3, 4, 3, 2, 0}

可以使用 Prim 算法或 Kruskal 算法求解最小生成树。

以下是使用 Prim 算法的步骤：

1. 选择一个起点，将其加入到最小生成树中。
2. 从未选择的点中，找到与已选择的点之间距离最小的点，将其加入到最小生成树中。
3. 重复步骤2，直到所有的点都被选择为止。

根据题目中给出的矩阵，可以选择起点为 0，然后得到以下的最小生成树：

0 -- 1 (1)
1 -- 2 (2)
1 -- 4 (3)
4 -- 3 (1)
4 -- 5 (2)

最小生成树中各边的长度和为 1+2+3+1+2=9。

相关问题

C++实现【问题描述】Prim算法解决的是带权重的无向图上连接所有顶点的耗费最小的生成树。Q使用最小堆数据结构。 【输入形式】在屏幕上输入顶点个数和连接顶点间的边的权矩阵。 【输出形式】第1个顶点为起始点，顺序输出按照贪心选择得到的各顶点序号，及该顶点的前驱顶点序号，及路径长度。 【样例1输入】 8 0 15 7 0 0 0 0 10 15 0 0 0 0 0 0 0 7 0 0 9 12 5 0 0 0 0 9 0 0 0 0 0 0 0 12 0 0 6 0 0 0 0 5 0 6 0 14 8 0 0 0 0 0 14 0 3 10 0 0 0 0 8 3 0 【样例1输出】 3 1 7 6 3 5 5 6 6 8 6 8 7 8 3 4 3 9 2 1 15 【样例说明】 输入：顶点个数为8。连接顶点间边的权矩阵大小为8行8列，位置[i,j]上元素值表示第i个顶点到第j个顶点的距离，0表示两个顶点间没有边连接。 输出：第1个顶点为起始点，顺序输出按照贪心选择得到的各顶点序号，及该顶点的前驱顶点序号，及路径长度。

以下是C++实现Prim算法的代码，使用最小堆数据结构：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 100;
const int INF = 0x3f3f3f3f;

int n; // 顶点个数
int g[MAXN][MAXN]; // 边的权重矩阵
int dist[MAXN]; // 存储每个节点到已选中节点的最小距离
int pre[MAXN]; // 存储每个节点的前驱节点
bool vis[MAXN]; // 标记每个节点是否已经被选中

struct Node {
    int u, dist;
    bool operator<(const Node& rhs) const {
        return dist > rhs.dist; // 最小堆，按照距离从小到大排序
    }
};

void prim() {
    priority_queue<Node> pq;
    pq.push({0, 0}); // 从节点0开始
    dist[0] = 0;

    while (!pq.empty()) {
        int u = pq.top().u;
        pq.pop();

        if (vis[u]) continue;
        vis[u] = true;

        for (int v = 0; v < n; ++v) {
            if (!vis[v] && g[u][v] < INF && g[u][v] < dist[v]) {
                dist[v] = g[u][v];
                pre[v] = u;
                pq.push({v, dist[v]});
            }
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> g[i][j];
            if (g[i][j] == 0) g[i][j] = INF;
        }
        dist[i] = INF;
    }

    prim();

    for (int i = 1; i < n; ++i) {
        cout << i + 1 << " " << pre[i] + 1 << " " << dist[i] << endl;
    }

    return 0;
}

说明：

1. 输入格式为顶点个数和连接顶点间的边的权矩阵，其中0表示两个顶点间没有边连接。
2. 初始化距离矩阵`dist`为无穷大，表示所有节点到已选中节点的距离都未知。
3. 使用最小堆来存储节点和其到已选中节点的最小距离。
4. 每次从最小堆中取出距离最小的节点，标记为已选中，更新其他节点到已选中节点的最小距离。
5. 输出每个节点的序号、前驱节点序号和路径长度。注意节点序号从1开始，需要加1输出。

本题要求建立一个无向图，采用邻接矩阵做为存储结构。 例如 函数接口定义： void CreatMGraph(MGraph &G);//创建图G int locate(MGraph G,char v);//返回顶点v的下标 G 为图，采用邻接矩阵存储结构，v 是顶点的值。 裁判测试程序样例： #include <stdio.h> #define MVNum 100 //最大顶点数 typedef struct{ char vexs[MVNum]; //存放顶点的一维数组 int arcs[MVNum][MVNum]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和边数 }MGraph; void CreatMGraph(MGraph &G);/* 创建图 */ void printGraph(MGraph G);/*输出图 */ int locate(MGraph G,char v);//返回顶点v的下标 int main() { MGraph G; CreatMGraph(G);//创建图G printGraph(G);//打印该图 return 0; } void printGraph(MGraph G)//打印图 { int i,j; for(i=0;i<G.vexnum;i++) { printf("%c:",G.vexs[i]); for(j=0;j<G.vexnum;j++) if (G.arcs[i][j]) printf(" %c",G.vexs[j]); printf("\n"); } } /* 请在这里填写答案 */ 输入信息为：第一行给出图的顶点数n和边数e。第二行给出n个字符，表示n个顶点的数据元素的值。后面是e行，给出每一条边的两个顶点的值(顶点之间无空格)。 输出每个顶点的值以及各顶点的邻接点的值。 输入样例： 7 9 0123456 02 03 04 13 15 23 25 45 56 输出样例： 0: 2 3 4 1: 3 5 2: 0 3 5 3: 0 1 2 4: 0 5 5: 1 2 4 6 6: 5 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

题目描述

本题要求建立一个无向图，采用邻接矩阵做为存储结构。

例如 函数接口定义：

void CreatMGraph(MGraph &G);//创建图G
int locate(MGraph G,char v);//返回顶点v的下标
G 为图，采用邻接矩阵存储结构，v 是顶点的值。

裁判测试程序样例：

#include <stdio.h>
#define MVNum 100 //最大顶点数
typedef struct{
char vexs[MVNum]; //存放顶点的一维数组
int arcs[MVNum][MVNum]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和边数
}MGraph;
void CreatMGraph(MGraph &G);/* 创建图 */
void printGraph(MGraph G);/*输出图 */
int locate(MGraph G,char v);//返回顶点v的下标
int main() {
MGraph G;
CreatMGraph(G);//创建图G
printGraph(G);//打印该图
return 0;
}
void printGraph(MGraph G)//打印图
{
int i,j;
for(i=0;i<G.vexnum;i++)
{
printf("%c:",G.vexs[i]);
for(j=0;j<G.vexnum;j++)
if (G.arcs[i][j]) printf(" %c",G.vexs[j]);
printf("\n");
}
}

/* 请在这里填写答案 */

输入信息为：第一行给出图的顶点数n和边数e。第二行给出n个字符，表示n个顶点的数据元素的值。后面是e行，给出每一条边的两个顶点的值(顶点之间无空格)。

输出每个顶点的值以及各顶点的邻接点的值。

输入样例：

7 9
0123456
02
03
04
13
15
23
25
45
56

输出样例：

0: 2 3 4
1: 3 5
2: 0 3 5
3: 0 1 2
4: 0 5
5: 1 2 4 6
6: 5

算法1

(邻接矩阵) $O(E)$

建立无向图，采用邻接矩阵存储结构。

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码