如何检测图的边列表表示中的循环？

Question

我已经将图结构编写为边列表，并且正在尝试为其编写 Kruskal 的 MST 算法。

到目前为止，这是我的代码：

#include <bits/stdc++.h>
using namespace std;
struct _ { ios_base::Init i; _() { cin.sync_with_stdio(0); cin.tie(0); } } _;

//////////////////////////////////////////////////////////////////////////////////
    #define endl '\n'
    #define ll long long
    #define pb push_back
    #define mt make_tuple
    #define in(a) for (auto& i: a)
//////////////////////////////////////////////////////////////////////////////////

#define edge tuple < ll, ll, ll >

bool func (edge a, edge b) { return get<2>(a) < get<2>(b); }

struct graph
{
    ll v;
    vector <edge> edgelist;
    void addedge (edge x) { edgelist.pb(x); }
    ll find (vector <ll> parent, ll i) 
    { return parent[i]==-1 ? i : find (parent, parent[i]); }
    bool cycle()
    {
        vector <ll> parent (v);
        fill (parent.begin(), parent.end(), -1);
        in (edgelist)
        {
            ll x = find (parent, get<0>(i));
            ll y = find (parent, get<1>(i));
            if (x==y) return true;
            else parent[x]=y;
        }
        return false;
    }

    graph mst()
    {
        sort (edgelist.begin(), edgelist.end(), func);
        graph tree;
        in(edgelist)
        {
            graph temp = tree;
            temp.addedge(i);
            if (!temp.cycle()) tree=temp;
        }
        return tree;
    }

};


int main()
{
    graph g;
    cin >> g.v;
    ll e;
    cin >> e;
    for (ll i=1; i<=e; i++)
    {
        ll a, b, w;
        cin >> a >> b >> w;
        g.addedge(mt(a, b, w));
    }
    graph mstree = g.mst();
    in(mstree.edgelist) cout << get<0>(i) << " " << get<1>(i) << " " << get<2>(i) << endl;
    cout << endl;

}

/*
Sample Input
4 5
0 1 10
0 2 6
0 3 5
1 3 15
2 3 4

Sample Output
2 3 4
0 3 5
0 1 10
*/

我的代码需要很长时间才能生成输出。我的实现有什么问题吗？此外，如果我为多个图形循环执行此任务，我的程序会在执行过程中崩溃。

Answer 1

My code takes a very long time to produce the output. Are there any problems in my implementation?

有几个问题：

首先，

ll find (vector <ll> parent, ll i) 
{ return parent[i]==-1 ? i : find (parent, parent[i]); }

你按值传递parent，这意味着复制所有数组。通过引用传递（和非常量，因为您需要对其进行修改，请参阅第 3 点）。

其次，在cycle()中你不需要检查所有条边，你只需要检查主循环中正在考虑的边（在mst()). （并且不要在cycle()中设置parent，你需要在所有mst()中使用相同的数组。）

第三，阅读disjoin-set结构的"enhancements"（连Wikipedia article都有解释），即按秩联合和路径压缩。只有那些你才能从 disjoin-set 中获得预期的性能。

Also, if I loop this task for multiple graphs, my program crashes in the middle of execution.

不可能告诉你不知道如何循环以及你正在使用的多图输入是什么。但是，我强烈怀疑当您按值传递 parent 时，即使是中型图形也会发生堆栈溢出，从而迅速消耗堆栈。

如何检测图的边列表表示中的循环？

How to detect cycle in edge list representation of graph?

c++

graph

minimum-spanning-tree

kruskals-algorithm