最小生成树(Minimum Spanning Tree)

小蓝 • 2024-11-19 19:00 • 编程

在图论中，最小生成树是一个连通图的生成树中，所有边的权值和最小的生成树。最小生成树常常用来描述一个带权无向连通图的所有节点集合之间的最小连接子树。

一、最小生成树的定义

对于一个无向连通图G=，其中V为节点的集合，E为边的集合，如果G’=是G的一个生成树，则E’是E子集，即E’包含E相同点数的边，并且G’中任意两点都是联通的。那么可以定义一个权重函数w(或者成为边的权值)，使得w(e)表示图G中边e的权重。则可以定义最小生成树为使得所有被包含在生成树中的边权重之和最小的生成树E’。

二、最小生成树的算法

1. Prim算法

Prim算法是一种贪心算法。其核心思想是每次加入一个与当前最小生成树有最短距离的点到生成树中，直到生成树覆盖所有节点。具体实现可以使用优先队列或者堆优化来加快运行时间。时间复杂度为O(E*logV)或O(V^2)。


#include<iostream>
#include<queue>
using namespace std;
const int MAXN = 1010; 
const int INF = 0x3f3f3f3f;
int mapp[MAXN][MAXN];
int lowcost[MAXN];
bool vis[MAXN];
int n, m;
int Prim() {
    int sum = 0;
    memset(lowcost, INF, sizeof(lowcost));
    memset(vis, false, sizeof(vis));
    lowcost[1] = 0;
    for(int i=1; i<=n; i++) {
        int u = 0;
        for(int j = 1; j lowcost[j])) {
                u = j;
            }
        }
        vis[u] = true;
        sum += lowcost[u];
        for(int v = 1; v mapp[u][v]) {
                lowcost[v] = mapp[u][v];
            }
        }
    }
    return sum;
}
int main() {
    while(cin>>n) {
        memset(mapp, INF, sizeof(mapp));
        for(int i = 1; i<=n; i++) {
            for(int j = 1; j>mapp[i][j];
            }
        }
        cout<<Prim()<<endl;
    } 
    return 0;
}

2. Kruskal算法

Kruskal算法是另一种常见的最小生成树算法。与Prim算法不同，Kruskal算法是每次加入一条具有最小权重的边，直到生成树中包含所有节点。为了避免有环情况，每加入一条边之前需要判断其起点和终点是否已经在同一集合中（使用并查集实现）。算法时间复杂度为O(E*logE)或O(E*logV)。


#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN = 1010;
const int INF = 0x3f3f3f3f;
struct Edge {
    int u, v, w;
}edge[MAXN*MAXN];
int pre[MAXN];
int mapp[MAXN][MAXN];
int n, m;
int Find(int x) {
    if(pre[x] == x) return x;
    return pre[x] = Find(pre[x]);
}
bool Union(int x, int y) {
    int fx = Find(x), fy = Find(y);
    if(fx != fy) {
        pre[fx] = fy;
        return true;
    }
    return false;
}
bool cmp(const Edge& e1, const Edge& e2) {
    return e1.w < e2.w;
}
int Kruskal() {
    for(int i = 1; i<=n; i++) {
        pre[i] = i;
    }
    sort(edge+1, edge+m+1, cmp);
    int ans = 0;
    for(int i = 1; i>n) {
        m = 0;
        memset(mapp, INF, sizeof(mapp));
        for(int i = 1; i<=n; i++) {
            for(int j = 1; j>mapp[i][j];
                if(i<j) {
                    edge[++m].u = i;
                    edge[m].v = j;
                    edge[m].w = mapp[i][j];
                }
            }
        }
        cout<<Kruskal()<<endl;
    }
    return 0;
}

三、最小生成树的应用

1.公路规划

在城市规划中，最小生成树可以用来找到连接不同地区的最短路径，以便合理安排公路建设。

2.电缆布线

在电缆布线中，最小生成树可以用来找到在不同建筑物之间连接最短的路径，以减少花费和切实提高电缆性能。

3.网络设计

在计算机网络设计中，最小生成树可以用来找到连接不同计算机的最短路径，以便建设网络的具体拓扑结构。

四、小结

最小生成树是图论中常见且重要的问题。Prim和Kruskal算法是两种解决最小生成树问题的常见算法，通过不同的加边方式和数据结构来实现。在真实场景中，最小生成树应用也很广泛，例如公路规划、电缆布线、网络设计等。读者在具体应用中，可以深入理解和改进算法，以实现更优秀的性能。

原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/159496.html