Проблема: мне нужно реализовать топологический поиск, используя следующий код поиска в глубину.
Примечание. Исходный код взят из здесь, и это задача, приведенная в конце главы.
Я буду честен. На уровне кодирования я чувствую себя довольно потерянным. Я добавил комментарии к строкам, чтобы показать, что, по моему мнению, делает каждая строка. Хотя я новичок в поиске в глубину, я понимаю, как они работают на функциональном уровне (в отличие от моих ограниченных знаний об их реализации). Я попытался добавить начальные вершины и время окончания в список, чтобы впоследствии отсортировать их, но у меня возникли проблемы с возвратом этого списка. Чтобы потом можно было отсортировать вершины в порядке убывания времени завершения.
Обратите внимание, что хотя в некоторых решениях используется стек, в этом коде явно не указано использование стека. Скорее, стек подразумевается в рекурсивном вызове dfsvisit.
from pythonds.graphs import Graph
# Definitions
# discovery time == iterations it took for the program to find the vertex and turn it gray
# finish time == iterations it took for the program to turn the vertex black
# pred == predecessor indicator
class DFSGraph(Graph):
def __init__(self):
super().__init__()
self.time = 0 # self has an attribute 'time' (counter) that initiates at 0
def dfs(self):
for aVertex in self:
aVertex.setColor('white')
aVertex.setPred(-1)
for aVertex in self:
if aVertex.getColor() == 'white':
self.dfsvisit(aVertex)
def print_graph(self):
for key in sorted(list(self.vertices.keys())):
print(key + str(self.vertices[key].neighbors + " " + str(self.vertices[key].dis)))
def dfsvisit(self,startVertex): # Initiate the visit vunction of the current object (self) at the starting vertex (startVertex)
finish_times = [] # Instantiate the a list to keep finish times for each node
startVertex.setColor('gray') # Set the color of the starting vertex to 'gray' (discovered)
self.time += 1 # Increment the timer
startVertex.setDiscovery(self.time) # Assign the discovery time to the current vertex (startVertex)
for nextVertex in startVertex.getConnections(): # Begin cycling through the connected vertices (nextVertex) of startVertex
if nextVertex.getColor() == 'white': # If a vertex (nextVertex) with the attribute color of white is found, then do the following:
nextVertex.setPred(startVertex) # Set the predecessor indicator of the next vertex as the current vertex (ie if B is white and connected to A, set B's predecessor as A)
self.dfsvisit(nextVertex) # Recursively calls itself with the next vertex until the color of the next vertex is no longer white (i.e. all have been explored)
startVertex.setColor('black') # Set the current vertice's color to black (explored)
self.time += 1 # Increment the timec counter
startVertex.setFinish(self.time) # Assign the finish time to the current vertex (startVertex)
finish_time = [startVertex, startVertex.setFinish(self.time)] # append vertex and finish times to finish_time list
return finish_time # return the finish_time list
Извините за мои длинные комментарии. Надеясь понять, как реализовать топологический поиск внутри этого кода.
Topological sorting
является побочным эффектомDepth-first search
. Вам не нужно ничего специально реализовывать для достижения сортировки или реальной сортировки. Данные сортируются в момент их вставки в график. Код, который вы показали, реализует подход обхода, когда посещенные узлы помечаются, а не сохраняются в стеке. Взгляните на сравнение. - person cassandrad   schedule 02.09.2019Graph
API, который вы расширяете, поэтому я не могу напрямую помочь вам с вашим кодом. Но я написал предыдущий ответ о том, как можно преобразовать поиск в глубину в топологическую сортировку, что может быть актуально здесь. - person Blckknght   schedule 03.09.2019