4

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

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

4

3 回答 3

3

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

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

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

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

于 2009-06-17T10:12:30.930 回答
0

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

如果图不需要保持连接，只需遍历所有边并删除所有非 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]
于 2009-06-19T05:23:29.507 回答
0

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

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

从一个起始节点，递归所有已确认的边以及尚未确认的边。但是当你要递归一个尚未确认的边时，首先检查边去的节点是否有一条路径，通过跟随确认的边，到当前搜索树中的一个节点（即一个访问的节点标志集）。必须通过跟踪所有已确认的边递归地完成此检查，但这对我来说太慢了，所以我将在这里解决，只是检查节点是否正在访问，或者它确认连接到的任何节点是否正在访问。这将涵盖我的大部分情况，但偶尔会在图表中留下周期。

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

这工作正常并且足够快。

于 2009-06-24T13:53:17.857 回答