如何从有向图中分离出循环依赖和有序依赖？

Question

我在写一个游戏，在游戏中构建电路，比如深圳IO。

为了弄清楚电路的作用，我想把电路的定向图分离成有序依赖和循环依赖，同时对有序依赖进行拓扑排序。

这是我的代码（我是用Python写的算法，只做原型）。

def tick(self):
# Toposort, and remove all circularly dependent elements
STATE_ALIVE = 0
STATE_DEAD = 1
STATE_UNDEAD = 2
states = defaultdict(lambda: STATE_ALIVE)  # Map ids to states
normals = []  # Normal ordered dependencies
circulars = []  # Things that depend on themselves

# Path: all the nodes followed to get to this node
def visit(node_id):
    if states[node_id] == STATE_UNDEAD:
        # It's a circular one!
        circulars.append(node_id)
        return
    if states[node_id] == STATE_DEAD:
        # we've processed this one already
        return
    # Mark this as undead
    states[node_id] = STATE_UNDEAD
    # visit each dependency of this node
    for dep in self.dependencies[node_id]:
        visit(dep)
    states[node_id] = STATE_DEAD
    if node_id not in circulars:
        normals.append(node_id)

# First pass
for node_id in range(len(self.nodes)):
    visit(node_id)

这个 几乎 工作。但是，深度嵌套的依赖关系没有得到正确的处理。我的测试集是这样的。

0: {0},
1: {0, 3},
2: {0, 4},
3: {1, 4},
4: {2, 3},
5: {0},
6: {3},
7: {8, 9},
8: {},
9: {}

我的代码无法排序 2 妥妥的。这是因为，当它到了访问 2 从外循环，它的依赖性 0 和 4 都是通过对 visit. 所以，它在试图处理时，会立即返回。4因此，从来没有看到 4 取决于 2，使得循环依赖关系。

有什么算法可以把有向图中的循环依赖和有序依赖分开？

Answer 1

你要找的算法是 "强连接分量"，请见 紧密相连的组件