删除具有固定边的有向图的循环依赖性

Question

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

删除此图表中的周期的最佳方法是什么？ 遍历应尽可能与DFS一样多，并从给定节点开始。

Answer 1

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

从标有已确认

的所有固定边的图表开始

从起始节点，递归所有已确认的边缘以及尚未确认的边缘。但是，当您即将递归尚未确认的边缘时，首先检查边缘所到达的节点是否有路径，通过跟随确认的边缘，到当前搜索树中的节点（即具有<的节点） em>访问标志集）。这个检查必须通过跟踪所有已确认的边缘递归完成，但这对我来说太慢了，所以我将在这里解决，只是检查节点是否正在访问，或者是否有任何已确认连接的节点正在访问。这将覆盖我的大部分案例，但会在图表中逐渐留下周期。

在上述步骤之后，我使用Tarjan的算法来查找图中剩余的强连通分量（这可以在O（V + E）时间内完成）。在我的情况下，强连接组件的数量将非常小，所以我只是浏览每个强连接组件并删除每个可移动边缘。然后我再次执行此步骤，直到图表中不再有周期。

这很好，速度也快。

Answer 2

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

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

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

对于有向图，它有点复杂。在这种情况下，FIXED边的图的任何组件都应该是树。在类似Dijkstra的算法中，只有这些节点的根应该是要添加到树中的候选者。

Answer 3

问题是低估的，因为您没有指定例如如果图表需要保持连接，或者如果要删除“小”图表。要修复所有周期的非FIXED边数，或者如果确实需要删除全局最小数量的非FIXED边。

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

如果你想要一个简单的贪婪算法去除纯DFS的边缘，你可以使用这样的东西如果图形在你移除一些非FIXED边缘时仍保持连接：

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]