求无向网最小生成树

求无向网最小生成树有多种算法，其中比较经典的算法包括Prim算法和Kruskal算法。

1. Prim算法

Prim算法是一种贪心算法，它从一个顶点开始，不断地选择与当前生成树相邻的最小权值边所连接的顶点加入生成树中，直到所有顶点都被加入为止。

具体实现流程如下：

（1）任选一个顶点作为起点，将其加入生成树。

（2）将与该顶点相邻的边加入集合T中。

（3）在集合T中选择一条权值最小的边，且该边所连接的顶点不在生成树中，将其加入生成树。

（4）将新加入的顶点的所有相邻边加入集合T中。

（5）重复步骤（3）和（4），直至生成树包含所有顶点。

代码实现：

#include <iostream>
#include <cstring>
using namespace std;

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

int G[MAXN][MAXN]; //存储图的邻接矩阵
int dis[MAXN]; //存储当前生成树到每个顶点的最小距离
bool vis[MAXN]; //标记顶点是否已经在生成树中

int prim(int n)
{
    memset(dis, INF, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[1] = 0; //起点为1号顶点
    int res = 0; //存储最小生成树的权值和
    for (int i = 1; i <= n; i++)
    {
        int u = 0;
        for (int j = 1; j <= n; j++)
        {
            if (!vis[j] && (u == 0 || dis[j] < dis[u]))
                u = j;
        }
        vis[u] = true;
        if (i > 1 && dis[u] == INF) //图不连通
            return -1;
        if (i > 1)
            res += dis[u];
        for (int v = 1; v <= n; v++)
        {
            if (!vis[v] && G[u][v] < dis[v])
                dis[v] = G[u][v];
        }
    }
    return res;
}

int main()
{
    int n, m;
    cin >> n >> m;
    memset(G, INF, sizeof(G));
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        G[u][v] = G[v][u] = w; //无向图
    }
    int ans = prim(n);
    if (ans == -1)
        cout << "图不连通" << endl;
    else
        cout << ans << endl;
    return 0;
}

2. Kruskal算法

Kruskal算法也是一种贪心算法，它按照边权从小到大的顺序选择边，如果这条边连接的两个顶点不在同一连通块中，则添加这条边，并将两个连通块合并。重复以上操作，直到所有顶点都在同一连通块中为止。

具体实现流程如下：

（1）将所有边按照权值从小到大排序。

（2）依次选择每条边，如果该边连接的两个顶点不在同一连通块中，则将其加入生成树中，并合并这两个连通块。

（3）重复步骤（2），直到所有顶点都在同一连通块中。

代码实现：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1005;
const int MAXM = 200005;

struct Edge
{
    int u, v, w;
} edges[MAXM];

int father[MAXN]; //并查集数组

bool cmp(const Edge& e1, const Edge& e2)
{
    return e1.w < e2.w;
}

int find(int x)
{
    if (father[x] == x)
        return x;
    return father[x] = find(father[x]);
}

void merge(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx != fy)
        father[fx] = fy;
}

int kruskal(int n, int m)
{
    for (int i = 1; i <= n; i++)
        father[i] = i;
    sort(edges + 1, edges + m + 1, cmp);
    int res = 0, cnt = 0;
    for (int i = 1; i <= m; i++)
    {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        if (find(u) != find(v))
        {
            merge(u, v);
            res += w;
            cnt++;
            if (cnt == n - 1)
                break;
        }
    }
    if (cnt < n - 1) //图不连通
        return -1;
    return res;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    int ans = kruskal(n, m);
    if (ans == -1)
        cout << "图不连通" << endl;
    else
        cout << ans << endl;
    return 0;
}

注：以上代码均为C++实现。