3

我是一名新程序员，正在学习斯坦福大学的 edX 算法课程。

其中一项编程任务是使用 Kosaraju 算法在具有约 1,000,000 个顶点的图上找到强连通分量。我的实现是从教科书的伪代码到 Python 的最基本的翻译，它在较小的图上运行良好，所以我认为它是正确的。

Python 的默认递归限制为 1000，它达到了限制。

我试过sys.setrecursionlimit(1000000)了，但这并没有帮助，而是我得到“进程完成，退出代码 -1073741571”，这是一个堆栈溢出。

我发现这两个页面用于增加堆栈大小限制，但不确定如何使用它们中的任何一个：设置堆栈大小、ulimit 命令。

另一个相关的信息是 Python 没有优化尾递归，但我不确定它是否适用于我的代码。

G = {}
for i in range(1, 875715):
    G[i] = [0]
for l in open('SCC.txt'):
    items = list(map(int, l.split()))
    G[items[0]].append(items[1])

Grev = {}
for i in range(1, 875715):
    Grev[i] = [0]
for l in open('SCC.txt'):
    items = list(map(int, l.split()))
    Grev[items[1]].append(items[0])

def TopoSort(G):
    for v in G:
        if G[v][0] == 0:
            DFStopo(G, v)

def DFStopo(G, s):
    G[s][0] = 1
    global orderedVertexList
    for v in G[s][1:]:
        if G[v][0] == 0:
            DFStopo(G, v)
    orderedVertexList.insert(0, s)

def Kosaraju(G, Grev):
    TopoSort(Grev)
    global numSCC
    for v in orderedVertexList:
        if G[v][0] == 0:
            numSCC = numSCC + 1
            DFSSCC(G, v)

def DFSSCC(G, s):
    G[s][0] = 1
    global SCC
    SCC.append(numSCC)
    for v in G[s][1:]:
        if G[v][0] == 0:
            DFSSCC(G, v)

numSCC = 0
orderedVertexList = []
SCC = []

Kosaraju(copy.deepcopy(G), copy.deepcopy(Grev))
4

0 回答 0