33DAI：批量导入三三文档

2026-05-20T18:24:06Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 18:24的版本
第86行：		第86行：
	[[Category:图论]]		[[Category:图论]]
	[[Category:三三文档]]		[[Category:三三文档]]

33DAI：导入1个版本

2026-05-20T18:12:23Z

导入1个版本

←上一版本	2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

新页面

== 最小生成树（MST） ==

在一张带权无向连通图中，生成树是包含所有 <math>n</math> 个顶点且只有 <math>n - 1</math> 条边的连通子图。'''权值和最小的生成树'''即为最小生成树。

== Kruskal 算法 ==

对边按权值排序，用并查集维护连通性，从小到大依次加入不构成环的边。

=== 模板 ===

<syntaxhighlight lang="cpp">
struct Edge
{
int u, v, w;
bool operator<(const Edge& that) const
{
return w < that.w;
}
};

// 并查集部分见并查集页面
int fa[MAXN];

int find(int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int kruskal(vector<Edge>& edges, int n)
{
sort(edges.begin(), edges.end());
for (int i = 1; i <= n; i++) fa[i] = i;

int mst = 0, cnt = 0;
for (auto [u, v, w] : edges)
{
int fu = find(u), fv = find(v);
if (fu != fv)
{
fa[fu] = fv;
mst += w;
cnt++;
if (cnt == n - 1) break;
}
}
return mst; // 若 cnt < n - 1 则图不连通
}
</syntaxhighlight>

时间复杂度：<math>O(m\log m)</math>（排序），适合稀疏图。

== Prim 算法 ==

从任意点出发，每次选择与当前生成树距离最近的点加入。

=== 模板 ===

<syntaxhighlight lang="cpp">
int prim(vector<pair<int, int>> g[], int n)
{
vector<bool> vis(n + 1, false);
vector<int> dis(n + 1, 0x3f3f3f3f);
dis[1] = 0;
int mst = 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;
if (dis[u] == 0x3f3f3f3f) return -1; // 不连通
vis[u] = true;
mst += dis[u];
for (auto [v, w] : g[u])
if (!vis[v])
dis[v] = min(dis[v], w);
}
return mst;
}
</syntaxhighlight>

时间复杂度：<math>O(n^2)</math>，适合稠密图。可用优先队列优化至 <math>O(m\log n)</math>。

[[Category:图论]]
[[Category:三三文档]]

11-图论/02-最小生成树 - 版本历史

33DAI：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档