ACM算法集锦：Kruskal与Prim算法详解

需积分: 3 167 浏览量更新于2024-07-24 收藏 206KB DOC 举报

"ACM算法集锦"是一份包含多种实用算法的文档，旨在帮助读者深入理解和应用算法来优化程序设计。文档的核心部分介绍了两种经典的图论算法：Kruskal's Minimal Spanning Tree (最小生成树) 和 Prim's Algorithm (Prim算法)。 **Kruskal's Minimal Spanning Tree (Kruskal算法)**： Kruskal算法是一种用于寻找无向加权图中最小生成树的贪心算法。在提供的代码中，首先定义了一个`edg`结构体，包含了边的起点`u`、终点`v`及其权重`w`。`operator<`函数实现了按照边的权重进行排序。`uni`函数是一个并查集数据结构，用于合并具有相同根节点的集合，以便在每次选择边时检查是否形成环路。`main`函数中，输入图的边信息，对所有边按权重升序排序，然后通过`uni`函数不断添加边到最小生成树中，直到形成一棵包含所有节点的树，并输出最小生成树的总权重。 **Prim's Algorithm (Prim算法)**： Prim算法是另一种求解最小生成树问题的方法，适用于稠密图。它从一个初始顶点开始，逐步加入与当前树相连的边，直至覆盖所有顶点。在这个代码片段中，使用了`set`数组来表示图的邻接矩阵，并通过`str`数组存储顶点名称。`make_`函数未在提供的内容中给出，可能是用于构建或初始化邻接矩阵的部分。Prim算法的关键在于维护一个优先队列（通常用堆实现），不断选取当前树中的最短边，直到遍历完所有顶点。通过学习和实践这两种算法，读者可以提升对图论的理解，以及如何运用贪心策略解决实际问题的能力。理解这些算法不仅有助于在ACM竞赛中取得好成绩，也有助于日常编程中优化网络连接、路由选择等场景。同时，这份文档强调了认真阅读和实践的重要性，相信通过不断探索，读者能够从中获得丰富的收获。

ACM 算法资料集锦 2009 年 12 月 10 日星期四

memset(mk , 0xff , sizeof(mk)) ;

memset(cx , 0xff , sizeof(cx)) ;

memset(cy , 0xff , sizeof(cy)) ;

for (i = 0 ; i < nx ; i++){

pred[i] = -1 ;

for (open[cur = tail = 0] = i ; cur <= tail && cx[i] == -

1 ; cur++){

for (u = open[cur] , v = 0 ; v < ny && cx[i] == -1 ; v ++)

if (g[u][v] && mk[v] != i)

{

mk[v] = i ; open[++tail] = cy[v] ; if (open[tail] >= 0) {

pred[open[tail]] = u ; continue ; }

for (d = u , e = v ; d != -1 ; t = cx[d] , cx[d] = e , cy[e]

= d , e = t , d = pred[d]) ;

}

if (cx[i] != -1) res++ ;

}

return res ;

}

int path(int u){

for (int v = 0 ; v < ny ; v++)

if (g[u][v] && !mk[v]){

mk[v] = 1 ;

if (cy[v] == -1 || path(cy[v])) {

cx[u] = v ;

cy[v] = u ;

return 1 ;

}

} return 0 ;

}

//少适用 O(n^3)

int MaxMatchDFS()

{

int res(0) ;

memset(cx , 0xff , sizeof(cx)) ;

memset(cy , 0xff , sizeof(cy)) ;

for (int i = 0 ; i < nx ; i++)

if (cx[i] == -1){

memset(mk , 0 , sizeof(mk));

res += path(i) ;

}

return res ;

}

最大权匹配,KM 算法

//此 KM 算法，坐标从 1 开始，记住

#include <iostream>

#include <vector>

#include <math.h>

using namespace std;

#define M 110

int n; // X 的大小

int lx[M], ly[M]; // 标号

bool sx[M], sy[M]; // 是否被搜索过

int match[M]; // Y(i) 与 X(match [i]) 匹配

// 从 X(u) 寻找增广道路，找到则返回 true

bool path(int u,int weight[M][M]) {

sx [u] = true;

for (int v = 0; v < n; v ++)

if (!sy [v] && lx[u] + ly [v] == weight [u] [v]) {

sy [v] = true;

if (match [v] == -1 || path(match [v],weight)) {

match [v] = u;

return true;

}

return false;

}

// 参数 Msum 为 true ，返回最大权匹配，否则最小权匹配

int km(bool Msum,int weight[M][M]) {

int i, j;

if (!Msum) {

for (i = 0; i < n; i ++)

for (j = 0; j < n; j ++)

weight [i] [j] = -weight [i] [j];

}

// 初始化标号

for (i = 0; i < n; i ++) {

lx [i] = -0x1FFFFFFF;

ly [i] = 0;

for (j = 0; j < n; j ++)

if (lx [i] < weight [i] [j])

lx [i] = weight [i] [j];

}

memset(match, -1, sizeof (match));

for (int u = 0; u < n; u ++)

while (1) {

memset(sx, 0, sizeof (sx));

memset(sy, 0, sizeof (sy));

if (path(u,weight))

剩余26页未读，继续阅读

Hi,Johnson

粉丝: 2
资源: 4

ACM算法集锦：Kruskal与Prim算法详解

ACM算法集锦.7z

ACM算法模板集锦.zip

ACM算法集锦：最小生成树与Prim算法实现

ACM算法集锦：Prim与Kruskal实现

ACM算法集锦：数论与图论经典解法

ACM算法集锦：深入探讨与实践应用

ACM算法集锦：贪心、图论与竞赛实用代码

ACM 算法集--常用ACM算法

ACM算法

ACM 算法ACM 算法

最新资源