消除对具有固定边的有向图的循环依赖

Question

我有一个有向循环图。 有些边缘是固定的，可能无法删除。 其他边缘可以被移除以打破循环。

删除该图中的循环的最佳方法是什么？ 遍历应尽可能采用 DFS，并从给定节点开始。

Answer 1

您可以做的是使用 Dijkstra 算法：从仅包含固定边的图开始。 然后从已有的图开始应用算法的改编：

1. 从起始节点开始，以及起始节点组件中的所有固定边。 假设这是一棵树。
2. 添加最接近树的节点。
3. 还要在刚刚添加的节点的组件中添加任何固定边。
4. 如果所有节点都在树中，则结束。 否则，转到步骤 4。

当然，这假设仅由 FIXED 边组成的图不包含循环。 如果是，则没有解决方案（即没有边的子图，但包含所有 FIXED 边）。

对于有向图，情况要复杂一些。 在这种情况下，固定边图的任何组成部分都应该是一棵树。 在类似 Dijkstra 的算法中，只有这些节点的根才应该是添加到树中的候选者。

Answer 2

这个问题被低估了，因为您没有指定例如图形是否需要保持连接，或者您是否想删除“少量”非固定边以打破所有循环，或者您是否确实需要全局最小数量的要删除的非固定边缘。

如果图不需要保持连通，只需遍历所有边并移除所有非FIXED边即可。 这将删除您可以在不删除固定边的情况下删除的所有循环。

如果您想要一个简单的贪心算法来删除纯 DFS 的边，则可以使用类似的方法，如果当您删除一些非固定边时图仍然保持连接：

proc recurse(vertex n, vertex_set ns)
  if (n appers_in ns) // it is a cycle
    return BREAK_CYCLE
  else for (e in list_outgoing_edges_from(n))
    np = e.destination
    result = recurse(np, add_to_set(ns, np))
    if (result == BREAK_CYCLE)
      if (e.FIXED)
        return BREAK_CYCLE
      else
        [remove e from the graph]
        return RETRY
      else if (result == RETRY)
        return recurse(n, ns)
    return FINISHED

if (recurse (your_initial_node, empty_vertex_set()))
  [graph contains a cycle through only FIXED edges]
else
  [the reachable component from initial_node has no longer cycles]

Answer 3

我使用以下算法来解决我的问题：

从标记为已确认的所有固定边的图形开始，

从起始节点开始，递归遍历所有已确认的边以及尚未确认的边。 但是，当您要向下递归尚未确认的边时，首先检查该边所前往的节点是否具有路径（通过遵循已确认的边）到当前搜索树中的节点（即带有 < em>访问标志集）。 此检查必须通过跟踪所有已确认的边来递归地完成，但这对我来说太慢了，因此我将在这里解决仅检查节点是否正在访问或者确认连接到的任何节点是否正在访问。 这将涵盖我的大部分情况，但偶尔会在图中留下循环。

在上述步骤之后，我使用 Tarjan 算法来查找图中留下的强连通分量（这可以在 O(V + E) 时间内完成）。 在我的情况下，强连接组件的数量非常小，因此我只需遍历每个强连接组件并分别删除一个可移动边缘。 然后我再次执行此步骤，直到图中不再有循环为止。

这工作正常并且足够快。