使用Kruskal算法检测图形中的循环

Question

我正在实现Kruskal算法,这是一种众所周知的方法来查找加权图的最小生成树.但是,我正在调整它以在图表中查找周期.这是Kruskal算法的伪代码:

KRUSKAL(G):
1 A = ?
2 foreach v ? G.V:
3    MAKE-SET(v)
4 foreach (u, v) ordered by weight(u, v), increasing:
5    if FIND-SET(u) ? FIND-SET(v):
6       A = A ? {(u, v)}
7       UNION(u, v)
8 return A

我有一个很难把握FIND-SET()和MAKE-SET()功能,或者它们与并查集的实现.

我当前的代码如下所示:

class edge {
    public:      //for quick access (temp) 
      char leftV;
      char rightV;
      int weight;
};

std::vector<edge> kruskalMST(std::vector<edge> edgeList){
    std::vector<char> set;
    std::vector<edge> result;
    sortList(edgeList);    //sorts according to weight ( passed by reference)
    do{
        if(set.empty()){
            set.push_pack(edgeList[i].leftV);    //also only push them when
            set.push_pack(edgeList[i].rightV);    //they aren't there , will fix
            result.push_back(edgeList[i]);
            ++i;
        }
        else {
            if((setContains(set , edgeList[i].leftV)) && (setContains(set , edgeList[i].rightV)))
                ++i; //skip node 
            else {
                set.push_pack(edgeList[i].leftV);    //also only push them when
                set.push_pack(edgeList[i].rightV);    //they aren't there , will fix
                result.push_back(edgeList[i]);
                ++i;
            }
     } while(i<edgeList.size());
    return result;
}

当两个已经存在的顶点set vector再次出现时,我的代码检测到图形中的循环.在大多数情况下,这似乎有效,直到我遇到这样的情况:

  [a]              [c]
   |                |
   |                |
   |                |
  [b]              [d]

当这些边缘出现在排序顺序,这是因为a,b,c,d已经被推入set vector.加入[a]到[c]不产生图形内的周期,但被检测为周期由于当前的实现.

在我的案例中,有没有可行的替代方法来检测周期？或者,如果有人能够解释如何MAKE-SET,FIND-SET并UNION在Kruskal的算法中工作,那将会有很大帮助.

Answer 1

MAKE-SET(v)表示您正在初始化仅由顶点组成的集合v.最初,每个顶点都在一个集合中.

FIND-SET(u)是一个函数,告诉您顶点属于哪个集合.它必须返回唯一标识该集合的指针或ID号.

UNION(u, v)表示您合并包含u的集合包含v.换句话说,如果u和v在不同的组中,UNION操作将形成含有集的所有成员一组新的FIND-SET(u)和FIND-SET(v).

当我们使用不相交集数据结构实现这些操作时,关键思想是每个集合都由一个领导者表示.每个顶点都有一个指向其集合中某个顶点的指针.集合的领导者是指向自身的顶点.所有其他顶点指向父节点,指针形成以领导者为根的树结构.

要实现FIND-SET(u),您可以跟踪指针,u直到到达设置引导,这是集合中唯一指向自身的顶点.

要实现UNION(u, v),您可以将一个设定点的领导者设为另一个设定点的领导者.

这些操作可以通过秩和路径压缩的联合思想进行优化.

按等级联合意味着您可以跟踪从集合中任何顶点到领导者的最大指针数.这与指针形成的树的高度相同.您可以通过为每个UNION操作执行一定数量的步骤来更新排名,这是集合排名唯一可以更改的时间.假设我们合并集合A和B使得A具有比B更大的等级.我们使B的领导者指向A的领导者.结果集合具有与A相同的等级.如果A具有比B更小的等级. ,我们使A点的领导者成为B的领导者,并且得到的集合具有与B相同的等级.如果A和B具有相同的等级,则我们选择哪个领导者并不重要.无论我们将A点的领导者指向B的领导者还是反之亦然,结果集的排名将比A的排名大一.

路径压缩意味着当我们执行FIND操作时,需要遵循一系列指向集合的领导者的指针,我们使沿途遇到的所有顶点直接指向领导者.这仅增加了当前FIND操作的工作量,并且减少了将来调用的工作量FIND.

如果您通过排名和路径压缩实现union,那么您将拥有一个非常快速的union-find实现.n次操作的时间复杂度为O(nα(n)),其中α是逆Ackermann函数.这个函数增长得如此之慢,如果n是宇宙中原子的数量,则α(n)为5.因此,它实际上是一个常数,优化的不相交集数据结构实际上是联合的线性时间实现 -找.