Каков наиболее эффективный способ написания рекурсивного метода, которому нужен доступ к переменной в Python? - PullRequest
Новая
       23

Каков наиболее эффективный способ написания рекурсивного метода, которому нужен доступ к переменной в Python?

4 голосов
/ 16 октября 2019

Я довольно новичок в 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}")
                for x in range(self.size):
                    if self.adjlist[v][x] == 1:
                        # print(f"x{x}")
                        stk.append(x)

    # recursive dfs style 1 with 2 methods
    def rdfs1(self, start=0):
        self.discovered = [False for _ in range(self.size)]
        self.rdfs1util()
        print("end")
        del(self.discovered)

    def rdfs1util(self, v=0):
        self.discovered[v] = True
        print(f"Discovered: {v}")
        for x in range(self.size):
            if self.adjlist[v][x] == 1:
                if not self.discovered[x]:
                    self.rdfs1util(x)

    # recursive dfs style 2
    def rdfs2(self, start=0):
        discovered = [False for _ in range(self.size)]

        def rdfsi(v):
            discovered[v] = True
            print(f"Discovered: {v}")
            for x in range(self.size):
                if self.adjlist[v][x] == 1:
                    if not discovered[x]:
                        rdfsi(x)
        rdfsi(start)
        print("end")

    # recursive dfs style 3
    def rdfs3(self, discovered, start=0):
        discovered[start] = True
        print(f"Discovered: {start}")
        for x in range(self.size):
            if self.adjlist[start][x] == 1:
                if not discovered[x]:
                    self.rdfs3(discovered, x)

    def bfs(self):
        pass

    def spf(self, vid):
        pass

    def view(self):
        for i in range(self.size):
            x = [j for j in range(self.size) if self.adjlist[i][j] > 0]
            if x is not None:
                print(str(i)+" : "+" ".join(map(str, x)))


######################
v = 8
e = [(0, 5), (5, 3),
     (0, 1), (1, 2), (6, 2), (0, 3), (2, 6), (3, 5), (3, 6), (4, 7)]
graph1 = Graph(v, e)
graph1.view()

print("iterative dfs:")
graph1.idfs()
print("__")
print("recursive dfs1:")
graph1.rdfs1()
print("__")
print("recursive dfs2:")
graph1.rdfs2()
print("__")
print("recursive dfs3:")
visits = [False for _ in range(v)]
graph1.rdfs3(visits)
...