小编opt*_*mum的帖子

我对 Python 还很陌生，想实现一些图算法只是为了练习。所以我以迭代和递归的方式实现了深度优先搜索，它们工作得很好。但是在我在网上找到的示例中，我看到了递归 DFS 的不同方法，这些方法似乎具有不同的内存使用情况。问题是总体上哪个更好。

我认为它们具有相同的时间复杂度，但我不知道如何衡量内存使用情况。其中之一应该符合python编程约定。

from collections import deque


class Graph:

    def __init__(self, n, vlist, directed=False):
        self.size = n
        self.adjlist = [[0 for _ in range(n)] for __ in range(n)]
        for x in vlist:
            self.adjlist[x[0]][x[1]] = 1
        if not directed:
            for x in vlist:
                self.adjlist[x[1]][x[0]] = 1

    # iterative DFS
    def idfs(self, start=0):
        discovered = [False for _ in range(self.size)]
        stk = deque()
        stk.append(start)
        while len(stk) > 0:
            v = stk.pop()
            if not discovered[v]:
                discovered[v] = True
                print(f"Discovered: {v}") …