检查图是否至少是一种单向连接

Question

有向图被称为“ 在-至少-单向连接的 ”如果，对于每两个节点u和v在图中，有两种从路径u到v或从一个路径v到u（或两者）。
是否有O(m + n)解决此问题的时间复杂度算法？

Answer 1

为了构建总体解决方案，让我们从这个问题的简单得多的版本开始。假设您知道输入图是有向无环图（DAG）。在这种情况下，您将如何解决问题？好吧，如果DAG具有两个不同的源节点，那么它就不会是至少一种单向连接（ALOWC），因为从这些源节点中的一个到另一个源节点之间就不会有路径。如果DAG确实具有单个源节点，则从该节点到DAG中的每个其他节点都有一条路径。这意味着如果图中的所有其他节点对都是ALOWC，则整个图就是ALOWC，我们可以通过删除该源节点并递归查看剩下的图来确定。换句话说，我们的算法如下所示：

while (the graph has more than one node) {
    if (the graph has more than one source node) return false;
    else find and remove a source node;
}

有效实现此算法的一种方法是从找到度数为0的节点开始。从那里，我们可以从图中删除它，并递减每个后继项的度数。然后，我们可以看到剩下的那些继承者，它们的度数为0，然后从那里开始。这是一些伪代码：

/* Compute indegrees. */
for (each node u) {
    u.indegree = 0;
}
for (each edge (u, v) in the graph) {
    v.indegree++;
}

/* Find a node with indegree 0. */
Node source = null;
for (each node u in the graph) {
    if (u.indegree == 0) {
        if (source != null) return false; // Two sources
        source = u;
    }
}

/* Repeatedly remove the source node, update indegrees, and find the
 * next node to process.
 */
while (there is more than one node) {
    /* Simulate removing the source node by decrementing the indegree
     * of each of its children.
     */
    Node next = null;
    for (each edge (source, v)) {
        v.indegree--;
        if (v.indegree == 0) {
            if (next != null) return false; // Two sources discovered
            next = v;
        }
    }

    source = next;
}
return true;

该算法的运行时间为O（m + n）：将时间设置为0需要花费时间O（n），将其初始化为正确值需要花费时间O（m），并且需要花费时间O（m + n）进行循环，因为每个节点最多设置一次为源，每个边缘最多访问一次。

因此，现在我们有一种算法可以解决DAG的这一问题，但是一般图形呢？好消息是，通过查看图的强连接组件和图的缩合，可以将此问题的更一般版本转换为DAG上的问题。（如果您以前没有看过这些概念，我认为您最好的选择是对它们进行很好的解释，因为我认为我无法在此处给出完整的解释）。

关键见解是以下情况：图G是ALOWC当且仅当其冷凝是也 ALOWC。若要了解原因，首先假设缩合为ALOWC，然后选择G中的任意两个节点u和v。如果u和v牢固连接，则存在从u到v的路径，因此它们为ALOWC。另一方面，如果u和v没有牢固地连接，则由于缩合是ALOWC，因此存在从包含u的SCC到包含v的SCC的路径，反之亦然，并且该路径给出了从在原始图形G中从u到v（反之亦然）。

另一方面，如果G为ALOWC，则如果形成它的缩合，则得到的DAG必须为ALOWC，因为给定了DAG中的两个SCC C1和C2，如果我们选择C1中的某个节点u和C2中的某个节点v从G开始，则存在从u到v或从v到u的路径，因此在冷凝中，存在从C1到C2的路径，反之亦然。

因此，这为该问题提供了一种非常干净的O（m + n）时间算法：

1. 使用标准的线性时间算法（例如Tarjan算法或Kosaraju算法）计算图G的凝聚。
2. 将以上算法用于DAG，以检查冷凝是否为ALOWC，然后返回该答案。

该算法的每一步都需要时间O（m + n），因此整体运行时间也是O（m + n）。

希望这可以帮助！