使用 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) 是一个告诉你顶点属于哪个集合的函数。它必须 return 一个唯一标识集合的指针或 ID 号。

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

当我们使用 disjoint-set data structure 实现这些操作时，关键思想是每个集合都由一个领导者表示。每个顶点都有一个指向其集合中某个顶点的指针。集合的领导者是指向自身的顶点。所有其他顶点都指向一个父节点，并且指针形成一个以领导者为根的树结构。

要实现 FIND-SET(u)，您需要遵循从 u 开始的指针，直到到达集合领导者，这是集合中唯一指向自身的顶点。

要实现 UNION(u, v)，您将一个集合的领导者指向另一集合的领导者。

这些操作可以通过按等级联合和路径压缩的思想进行优化。

按等级合并意味着您跟踪从集合中的任何顶点到领导者的最大指针数。这与指针形成的树的高度相同。您可以通过对每个 UNION 操作执行恒定数量的步骤来更新排名，这是集合排名唯一可以更改的时间。假设我们正在合并集合 A 和 B，使得 A 的秩大于 B。我们使 B 的领导者指向 A 的领导者。结果集与 A 具有相同的秩。如果 A 的秩小于 B ，我们让A的leader指向B的leader，结果集和B有相同的rank。如果A和B有相同的rank，我们选择哪个leader都没有关系。无论我们让 A 的领导者指向 B 的领导者还是相反，结果集的等级都会比 A 的等级大 1。

路径压缩意味着当我们执行 FIND 操作时，这需要遵循一系列指向集合领导者的指针，我们使我们遇到的所有顶点都直接指向领导者.这只会将当前 FIND 操作的工作量增加一个常数因子，并减少以后调用 FIND.

的工作量

如果您通过等级和路径压缩实现并集，您将拥有一个极快的并集查找实现。 n 操作的时间复杂度是 O(n α(n))，其中 α 是反阿克曼函数。这个函数增长如此缓慢以至于如果 n 是宇宙中的原子数，α(n) 就是 5。因此，它实际上是一个常量，优化的不相交集数据结构实际上是联合查找的线性时间实现。

Answer 2

我不会重复 union/find 算法的集合论描述（Kruskal 只是它的一个特例），而是使用更简单的方法（在此基础上，您可以按等级应用并集和路径压缩。)

为简单起见，我假设每个顶点都有一个唯一的整数 ID，范围从 0 到 order - 1（例如，顶点 ID 可以用作数组的索引。）

天真的算法如此简单，代码自己会说话：

int find(int v, int cc[]) {
  while (cc[v] >= 0)
    v = cc[v];
  return v;
}

bool edge_union(int v0, int v1, int cc[]) {
  int r0 = find(v0, cc);
  int r1 = find(v1, cc);
  if (r0 != r1) {
    cc[r1] = r0;
    return true;
  }
  return false;
}

cc 数组到处都用 -1 初始化（当然它的大小反映了图形顺序。）

然后可以通过在 find 函数的 while 循环中堆叠遇到的顶点来完成路径压缩，然后为所有顶点设置相同的表示。

int find2(int v, int cc[]) {
  std::deque<int> stack;
  while (cc[v] >= 0) {
    stack.push_back(v);
    v = cc[v];
  }
  for (auto i : stack) {
    cc[i] = v;
  }
  return v;
}

对于rank并集，我们简单地使用数组的负值，值越小，rank越大。这是代码：

bool edge_union2(int v0, int v1, int cc[]) {
  int r0 = find(v0, cc);
  int r1 = find(v1, cc);
  if (r0 == r1)
    return false;
  if (cc[r0] < cc[r1])
    cc[r1] = r0;
  else {
    if (cc[r1] < cc[r0])
      cc[r0] = r1;
    else {
      cc[r1] = r0;
      cc[r0] -= 1;
    }
  }
  return true;
}

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

Detect cycle in a graph using Kruskal's algorithm

c++

algorithm

disjoint-sets

graph-algorithm

union-find