Je n'arrive pas à contourner mon code dans la boucle imbriquée. Je suis l'algorithme de Kahn ici sur le wiki: Kahn's. Je ne comprends pas comment tester si outgoingEdge a des bords entrants pour chaque élément endArray (m).Problème de tri topologique (algorithme de Kahn)
Voici ce que j'ai jusqu'à présent:
def topOrdering(self, graph):
retList = []
candidates = set()
left = []
right = []
for key in graph:
left.append(key)
right.append(graph[key])
flattenedRight = [val for sublist in right for val in sublist]
for element in left:
if element not in flattenedRight:
#set of all nodes with no incoming edges
candidates.add(element)
candidates = sorted(candidates)
while len(candidates) != 0:
a = candidates.pop(0)
retList.append(a)
endArray = graph[a]
for outGoingEdge in endArray:
if outGoingEdge not in flattenedRight:
candidates.append(outGoingEdge)
#flattenedRight.remove(outGoingEdge)
del outGoingEdge
if not graph:
return "the input graph is not a DAG"
else:
return retList
Voici une image à visualiser mon algorithme. Le graphique est sous la forme d'une liste d'adjacence.
Ah, j'oublié de mentionner, pas de clés vides autorisés. –
@JeffreyPhung Que voulez-vous dire pas de clés vides autorisées? '3' ne devrait pas être dans la liste d'adjacence car il n'y a pas de bords sortants? – niemmi
Ma liste d'adjacence donnée n'en a pas 3 inclus. Donc, de votre logique, il y aura une erreur d'exception, ce qui est la raison pour laquelle j'ai essayé de le faire à ma façon. De votre chemin, je suppose que je devrais alors créer une autre liste d'adjacence pour chaque voisin à nouveau? –