Я реализую алгоритм 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
должны быть глобальными