3

我正在实现 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()andMAKE-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]不会在图中产生循环，但由于当前实现而被检测为循环。

在我的情况下，是否有任何可行的替代方法来检测周期？或者，如果有人可以解释Kruskal 算法的MAKE-SET、FIND-SET和UNION工作原理，那将有很大帮助。

4

2 回答 2

6

MAKE-SET(v)意味着您正在初始化一个仅由 vertex 组成的集合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的leader指向B的leader，得到的集合和B的rank相同。如果A和B的rank相同，那么我们选择哪个leader都没有关系。无论我们让 A 的领导者指向 B 的领导者，反之亦然，结果集的排名将比 A 的排名大 1。

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

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

于 2015-05-02T04:42:53.100 回答
2

我不会重复联合/查找算法的集合论描述（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;
}

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

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;
}
于 2015-05-02T17:14:14.647 回答