algorithm - 这个总汇算法仅适用于 dags 吗？

Question

我发现了这种用于检查图中是否存在总汇的有向图算法。 https://www.geeksforgeeks.org/determine-whether-universal-sink-exists-directed-graph/

我的问题是：这对非 dag 有向图有效吗？
因为如果存在 v1、v2 之间的循环，那么我们可能会错过识别这个 1 并错误地将 v2 视为源接收器（或者我在这里遗漏了什么）？

Answer 1

该算法将正常工作。您缺少其他is_sink方法。

def is_sink(self, i):
    for j in range(self.vertices):

        # if any element in the row i is 1, it means
        # that there is an edge emanating from the
        # vertex, which means it cannot be a sink
        if self.adjacency_matrix[i][j] == 1:
            return False

        # if any element other than i in the column
        # i is 0, it means that there is no edge from
        # that vertex to the vertex we are testing
        # and hence it cannot be a sink
        if self.adjacency_matrix[j][i] == 0 and j != i:
            return False

    # if none of the checks fails, return true
    return True

之后j == vertices，我们进行此检查以确保在包含该顶点的图中确实不存在环i。