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

Question

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

在这个图中，最好的方法是什么来移除循环呢？ 遍历应该尽量使用深度优先搜索，并从给定节点开始。

- pete

---

不清楚您是想要一个包含所有固定边的最小生成树，还是具有所有固定边的最大DAG。 - user44242

如果只使用固定的边，则我所拥有的图中不包含任何循环。我想要的结果正是你执行DFS搜索并删除反向边时得到的结果。但我的一些边是固定的，不能被删除，因此当一个固定边是反向边时，我希望返回递归调用堆栈并删除第一个可移除的边。这是可以实现的，但复杂度太高，对于我的一些典型情况来说速度会太慢。 - pete

Answer 1

你可以使用Dijkstra算法：从仅包含固定边的图开始。然后应用一种适应性算法，从你已经拥有的图开始：

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

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

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

- Martijn

Answer 2

问题并没有充分说明，因为您没有指定例如图形是否需要保持连接，或者是否要删除“少量”非固定边以打破所有循环，或者是否真正需要全局最小数量的非固定边被删除。

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

如果您想要一个简单的贪婪算法来删除边缘，那么可以使用纯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]

- Antti Huima

Answer 3

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

从所有固定边标记为“已确认”的图开始。

从起始节点开始，递归遍历所有已确认的边以及尚未确认的边。但是，在递归下一个尚未确认的边之前，首先检查该边所连接到的节点是否具有路径，通过跟随已确认的边，到达当前搜索树中的节点（即设置了“访问”标志的节点）。必须通过递归跟随所有已确认的边来进行此检查，但这对我来说太慢了，因此我将在此处停留，仅检查节点是否正在访问或其任何已确认连接到的节点是否正在访问。这将涵盖大多数情况，但偶尔会在图中留下循环。

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

这很好用，速度也足够快。

- pete