0
入れ子になったforループのコードの周りに私の頭をラップするのに問題があります。私はWikiのKahnのアルゴリズムに従っています:Kahn's。 outgoingEdgeに各endArray要素(m)の入力エッジがあるかどうかをテストする方法を理解できません。ここでトポロジカルソート(Kahn's algorithm)のトラブル
は、私がこれまで持っているものである:ここでは
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
は私のアルゴリズムを可視化した画像です。グラフは隣接リストの形式です。
ああ、私は言及を忘れてしまった、許可されていない空のキー。 –
@JeffreyPhung空のキーが許されないということはどういう意味ですか?発信エッジがないので、 '3'は隣接リストにはないはずですか? – niemmi
私の隣接リストには3つが含まれていません。あなたのロジックから、例外エラーが発生します。私はそれを自分のやり方でやろうとしました。あなたの方法から、私は再び隣人のための別の隣接リストを作成しなければならないと思いますか? –