为什么我的kruscal()建树是错误的？(语言-c++)

Question

为什么我建的最大生成树是错误的？

//kruska找最大生成树(保证所经过权值最大)的最小边
#include<bits/stdc++.h>
using namespace std;
#define N 20100
#define ll long long
struct node
{
    int v,u,w;
}e[N];
struct leaf
{
    int u,v,w; 
}tr[N*2];
int cnt=0,n,m,q;
int h[N],par[N],dis[N];
int dep[N],st[N][20],val[N],vis[N];//lca
bool cmp(node a,node b)//排序的比较都是bool
{
    return a.w>b.w;
}
void add(int u,int v,int w)
{
    cnt++;
    tr[cnt].v=v;
    tr[cnt].w=w;
    tr[cnt].u=h[u];
    h[u]=cnt;
}
void init(int n)
{
    for(int i=1;i<=n;i++)
        par[i]=i;
}
int find(int x)
{
    if(x==par[x])
        return par[x];
    else
    {
        par[x]=find(par[x]);
        return par[x];
    }
}
void kruskal()
{
    sort(e+1,e+m+1,cmp);
    init(n);
    for(int i=1;i<=m;i++)
    {
        int fx=find(e[i].u);
        int fy=find(e[i].v);
        if(fx^fy)
        {
            par[fy]=par[fx];
            add(e[i].u,e[i].v,e[i].w);
            add(e[i].v,e[i].u,e[i].w);
        }
    }
    return;
}
// void dfs(int x,int f)
// {
//     dep[x]=dep[f]+1;
//     for(int i=1;1<<i<=dep[x];i++)
//         st[x][i]=st[st[x][i-1]][i-1];
//     cout<<x<<" "<<f<<"\n";
//     for(int i=h[x];i;i=tr[i].u)//树的边
//     {
//         int v=tr[i].v;
//         if(v!=f && vis[v]==0)
//         {
//             val[v]=tr[i].w;
//             st[v][0]=x;
//             vis[v]=1;
//             dfs(v,x);
//         }
//     }
// }
// int lca(int a,int b)
// {
//     if(find(a)!=find(b))
//         return -1;//两个节点不联通
//     if(dep[a]<dep[b])
//         swap(a,b);
//     while(dep[a]>dep[b])
//     {
//         int k=log2(dep[a]-dep[b]);
//         a=st[a][k];
//     }
//     if(a==b)
//         return a;
//     for(int i=log2(dep[a])+1;i>=0;i--)
//     {
//         if(st[a][i]==st[b][i])
//         {
//             a=st[a][i];
//             b=st[a][i];
//         }
//     }
//     return st[a][0];
// }
// void work(int x,int y)
// {
//     int fa=lca(x,y);
//     if(fa==-1)
//         cout<<-1<<"\n";
//     else
//     {
//         int a,b;
//         a=b=0x3f3f3f3f;
//         for(int i=x;i!=fa;i=st[x][0])
//             a=min(a,val[i]);
//         for(int i=x;i!=fa;i=st[x][0])
//             b=min(b,val[i]);
//         cout<<min(a,b)<<"\n";    
//     }    
    
// }
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>e[i].u>>e[i].v>>e[i].w;
    kruskal();
    for(int i=1;i<=cnt;i++)
    {
        for(int j=h[i];j;j=tr[j].u)
            cout<<i<<" "<<j<<" "<<tr[i].v<<"\n";
        cout<<"\n";
    }
    // cin>>q;
    // for(int i=1;i<=n;i++)
    // {
    //     if(find(i)==i)//i为树根
    //     {
    //         vis[i]=1;
    //         dep[i]=1;
    //         st[i][0]=i;
    //         dfs(i,i);//因为可能有多棵树，所以for循环枚举一遍
    //         cout<<i<<"\n";
    //     }
    // }//初始化！！！
    // for(int i=1;i<=n;i++)
    //     printf("ss %d %d\n",st[i][0],val[i]);
    // cout<<"\n";
    // while(q--)
    // {
    //     int a,b;
    //     cin>>a>>b;
    //     work(a,b);//最小边一定在两点路径到lca上 
    // }
    // return 0;
}/*
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
*/

Answer 1

以下内容由AIGC及阿里嘎多学长共同生成、有用望采纳：

---

在您提供的代码中，我注意到了几个可能的问题，这些问题可能导致您使用 Kruskal 算法构建的最大生成树（MST）不正确：

1. 排序逻辑错误： 您的 cmp 函数是按照权重从大到小排序的，但 Kruskal 算法需要的是最小生成树，即按照权重从小到大排序。您需要修改 cmp 函数，使其能够按照权重从小到大进行排序。

   bool cmp(node a, node b) {
       return a.w < b.w; // 修改为小于号
   }
   

2. 边的添加逻辑： 您的 add 函数似乎是用来构建树的表示，但是在 Kruskal 算法中，通常不需要这样的表示。您只需要添加边到一个集合中，并确保不会形成环即可。

3. 并查集的实现： 您的 find 函数中使用了路径压缩技术，这是好的实践。但是，您的 par 数组的初始化应该在 kruskal 函数内部进行，以确保每次调用 kruskal 时都是从干净的状态开始。

4. 边的权重处理： 您需要确保输入的边权重是正确的，并且在构建树时考虑了这些权重。从代码中看不出这个问题，但您应该检查输入数据是否正确。

5. 验证生成的树： 您的代码中没有包含验证生成的树是否正确的逻辑。通常，可以通过检查生成的边数是否为 n-1 来验证，其中 n 是顶点数。此外，您还可以检查是否有任何两个顶点之间没有路径。

6. 未使用的代码： 您的代码中有一些注释掉的未使用的代码，例如 dfs、lca 和 work 函数。如果您不需要这些功能，应该将它们从代码中移除，以避免混淆。

7. 输出格式： 您的输出格式可能不是检查 MST 是否正确的最佳方式。您可能需要以不同的方式输出或验证结果。

根据上述问题，您可以尝试以下修改：

• 修正 cmp 函数，确保按照权重从小到大排序。
• 移除或修改 add 函数，如果您不需要构建树的特定表示。
• 确保 par 数组在每次调用 kruskal 函数时都正确初始化。
• 检查输入数据，确保权重正确无误。

修改后的 kruskal 函数可能如下所示：

void kruskal() {
    sort(e + 1, e + m + 1, cmp); // 使用修正后的 cmp 函数
    for(int i = 0; i <= n; i++) {
        par[i] = i; // 初始化 par 数组
    }
    for(int i = 1; i <= m; i++) {
        int fx = find(e[i].u);
        int fy = find(e[i].v);
        if(fx != fy) {
            par[fy] = fx; // 合并两棵树
            // 如果需要记录 MST 的边，可以在这里添加逻辑
        }
    }
    // 验证逻辑（如果需要）
}

请注意，这些只是基于您提供的代码片段的建议。您可能需要根据您的具体需求进一步调整代码。