Лучшая реализация DFS - PullRequest
       5

Лучшая реализация DFS

0 голосов
/ 15 января 2020

Я реализую алгоритм DFS на Python3, мой реальный код:

def util_DFS(G, i, startTime, globalStartTime):
   """
   Util function used in DFS
   :param G: (networkx.DiGraph) Graph on wich will be applied the DFS algorithm
   :param i: Integer representing the vertex from which DFS will be applied
   :param startTime: global variable containing an array recording the time needed to reach each vertex
   :param globalStartTime: global variabl recording the number of nodes visited
   """        
   startTime[i] = globalStartTime
   globalStartTime += 1
   for j in G.neighbors(i):
       if startTime[j] == -1:
           util_DFS(G, j, startTime, globalStartTime)


def DFS(G, i):
   """
   :param G: (networkx.DiGraph) Graph on wich will be applied the DFS algorithm
   :param i: Integer representing the vertex from which DFS will be applied
   """     
   startTime = np.zeros(len(G), dtype=np.int64) - 1
   globalStartTime = 0
   util_DFS(G, i, startTime, globalStartTime)
   return startTime

Код работает нормально и выдает ожидаемые от него результаты, но мне было интересно, есть ли лучший метод для кодирования DFS, метод, который не требует двух функций, как я сделал.

Обратите внимание, что вторая функция DFS это просто оболочка util_DFS. Мне нужна была такая обертка, потому что переменные startTime и globalStartTime должны быть глобальными

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...