c - 使用随机收缩算法对无向图进行最小割

Question

我在 Kragers 最小切割算法中看到了一种边缘收缩的实现:

我们使用邻接关系将无向图表示为对称有向图列表表示。

(声明)每个顶点都有一个与相邻的边的双向链表它和指向列表开头和结尾的指针。表示一条边 u,v由两条弧 (u,v) 和 (v,u) 组成。这些弧具有彼此指向的指针。

u的邻接表中出现一条弧(u,v)，并且有一个指向v的指针。

1. 对于 v 的邻接表中的每个 (v,w)，将反向弧 (w, v) 替换为(w，u)。此操作需要 O(d(v))，其中 d(v) 是 v 的次数。
2. 将 v 的弧列表追加到 u 的弧列表中。这需要恒定的时间。
3. 从 V (G) 中删除 v。这需要恒定的时间。

4. 删除u的邻接表中的自环。这需要 O(d(u)+d(v)) 时间。

   我无法理解第一步中替换反向弧(w，v)以及他所说的(声明)是什么意思？我只熟悉 C 语言，所以请仅引用 C 来解释我

Answer 1

为了具体起见，我们有一个类似的结构

struct Arc {
    struct Arc *sym;
    struct Arc *onext;
    int edge;
    int org;
};

。每条无向边都表示为两条弧，每个方向各一条。 edge 成员存储边的 ID。 sym 成员指向同一条边的另一条弧。 org 成员是弧的原点顶点的 ID(因此边位于 ->org 和 ->sym->org 之间.)onext成员指向下一条具有相同原点顶点的弧；这些弧循环地连接在一起。

对于一个非常简单的图表，例如

   4     5
1 --- 2 --- 3

，我们有这样的结构。

struct Arc a12, a21, a23, a32;
a12.sym = &a21;
a12.onext = &a12;
a12.edge = 4;
a12.org = 1;
a21.sym = &a12;
a21.onext = &a23;
a21.edge = 4;
a21.org = 2;
a23.sym = &a32;
a23.onext = &a21;
a23.edge = 5;
a23.org = 2;
a32.sym = &a23;
a32.onext = &a32;
a32.edge = 5;
a32.org = 3;

现在让我们完成这些步骤。

对于v的邻接表上的每个(v,w)，用(w,u)替换反向弧(w,v)。

让struct Arc *a 成为我们正在收缩的边的弧之一。我们有一个像这样的循环

struct Arc *b = a;
do {
    b->org = a->sym->org;
    b = b->onext;
} while (b != a);

遍历a->org的邻接表。对于我们遇到的每个弧，我们必须将原点顶点更新为 a->sym->org。

将 v 的弧列表追加到 u 的弧列表中。

我们必须将涉及 a 和 a->sym 的循环拼接在一起。这是通过像(未经测试!)这样的交换来完成的

struct Arc *temp = a->onext;
a->onext = a->sym->onext;
a->sym->onext = temp;

.

从 V (G) 中删除 v

这超出了我所描述的表示范围。

删除u的邻接表中的自环

我们像以前一样迭代邻接列表，但这一次，我们必须更加小心，因为我们正在改变它。基本循环看起来很相似。

struct Arc *b = a;
/* look for a non-self-loop */
do {
    if (b->sym->org != b->org) {
        a = b;
        goto found;
    }
    b = b->onext;
} while (b != a);
/* everything is a self-loop; time to terminate the algorithm */
return;

found:
do {
    if (b->onext->sym->org == b->onext->org) {
        /* splice out b->onext */
        b->onext = b->onext->onext;
    } else {
        /* go to the next arc */
        b = b->onext;
    }
} while (b != a);

请注意，所有这些代码都未经测试。 a 中留下一条未删除的同源弧。