运行 大图上的 DFS

Question

我试图在实现 Kosaraju 算法的大图中找到强连通分量。它需要 运行 在图形上反向执行 DFS，然后向前。如果您对此图的边列表感兴趣，请参见此处：https://dl.dropboxusercontent.com/u/28024296/SCC.txt.tar.gz

我无法在 Python 中递归实现它，它超出了它的递归限制，如果我增加它们就会崩溃。我正在尝试通过迭代来实现。

下面是我的代码，用于 1. 将图形反向加载到字典中，以及 2. 运行 从 n -> 1 的每个节点迭代其上的 DFS。

此代码 运行 非常适合小样本图，但 运行 不适用于这个大图。我知道它效率低下，但有任何关于如何使其工作的提示吗？

def reverseFileLoader():

    graph = collections.defaultdict(lambda: {'g': [], 's': False, 't': None, 'u': None })
    for line in open('/home/edd91/Documents/SCC.txt'):
        k, v = map(int, line.split())
        graph[v]['g'].append(k)

    return graph

def DFS(graph, i):
    global t
    global source
    stack = []
    seen = []
    seen.append(i)
    stack.append(i)

    while stack:
        s = stack[-1]
        j = len(graph[s]['g']) - 1
        h = 0
        while (j >= 0):
            if graph[s]['g'][j] not in seen and graph[graph[s]['g'][j]]['t'] == None:
                seen.append(graph[s]['g'][j])
                stack.append(graph[s]['g'][j])
                h += 1
            j -= 1

        if h == 0:
            if graph[s]['t'] == None:
                t += 1
                graph[s]['u'] = source
                graph[s]['t'] = t 
            stack.pop()

def DFSLoop(graph):
    global t
    t = 0
    global source
    source = None
    i = len(graph)
    while (i >= 1):
        print "running for " + str(i)
        source = i
        DFS(graph, i)
        i -= 1

Answer 1

Kosaraju 的算法可能要求检查元素是否已被看到是 O(1) 操作。但是您看到的数据结构具有 O(n) 时间成员资格测试。将 seen 从列表转换为集合使代码在我的系统上执行几秒钟（在删除占用大部分剩余执行时间的打印之后）。

为了完整起见，您需要进行的更改是

• 将seen = []更改为seen = set()
• 将每个 seen.append(...) 更改为 seen.add(...)。