Topologische Sortieren python
Codiert ich eine Lösung für die DFS nicht-rekursive, aber ich kann es nicht ändern, so dass eine topologische Sortierung:
def dfs(graph,start):
path = []
stack = [start]
while stack != []:
v = stack.pop()
if v not in path: path.append(v)
for w in reversed(graph[v]):
if w not in path and not w in stack:
stack.append(w)
return path
Irgendwelche Ideen wie es zu ändern?
Mit der rekursiven version kann ich einfach die Sortierung:
def dfs_rec(graph,start,path):
path = path + [start]
for edge in graph[start]:
if edge not in path:
path = dfs_rec(graph, edge,path)
print start
return path
Eingang:
>>> graph = {
1: [2, 3],
2: [4, 5, 6],
3: [4,6],
4: [5,6],
5: [6],
6: []
}
>>> dfs_rec(graph,1,[])
6
5
4
2
3
1
[1, 2, 4, 5, 6, 3]
>>> dfs(graph,1)
[1, 2, 4, 5, 6, 3]
>>> graph = {
1: [3],
3: [5,6],
5: [4],
4: [7],
7: [],
6: []
}
>>> print dfs_rec(graph,1,[])
7
4
5
6
3
1
[1, 3, 5, 4, 7, 6]
>>> print dfs(graph,1)
[1, 3, 5, 4, 7, 6]
so, ich brauchen, um diese Bestellung in der nicht-rekursiven auch.
Nicht-rekursive Lösung:
Ich denke, dass dies auch die Lösung sein könnte, kenn mich, wenn ich falsch bin.
def dfs(graph,start):
path = []
stack = [start]
label = len(graph)
result = {}
while stack != []:
#this for loop could be done in other ways also
for element in stack:
if element not in result:
result[element] = label
label = label - 1
v = stack.pop()
if v not in path: path.append(v)
for w in reversed(graph[v]):
if w not in path and not w in stack:
stack.append(w)
result = {v:k for k, v in result.items()}
return path,result
Eingang:
graph = { 1: [3], 3:[5,6] , 5:[4] , 4:[7], 7:[],6:[]}
print dfs(graph,1)
Ausgabe:
([1, 3, 5, 4, 7, 6], {1: 7, 2: 4, 3: 5, 4: 6, 5: 3, 6: 1})
1
/
3
/\
5 6
/
4
/
7
- Könnten Sie uns ein Beispiel geben von input?
- Was ist hier das problem? In beiden Fällen ist der Rückgabewert von
dfs_rec
entspricht derdfs
. Welche Ergebnisse wollen Sie stattdessen? - Ja, das Ergebnis entspricht, aber in dfs_rec, wenn die Rekursion endet, es gibt mir die (print start) die topologische Sortierung des Graphen, also ich will jetzt eine topologische Sortierung der nicht-rekursiven Funktion dfs (), aber ich konnte nicht gelingen, es zu tun.
- Sie wollen also beide Funktionen zurück
[7, 4, 5, 6, 3, 1]
im zweiten Fall? - [6, 5, 4, 2, 3, 1] und [7, 4, 5, 6, 3, 1] für die dfs(graph,1) die nicht-rekursive Funktion. Wie Sie sehen können ich habe bereits für die erste Funktion dfs_rec.
- Es sei denn, dies ist eine Akademische übung das Rad nicht neu erfinden, NetworkX, es ist genial
- Ja, es ist Akademische übung, natürlich würde ich wahrscheinlich etwas verwenden, ist bereits codiert.
Du musst angemeldet sein, um einen Kommentar abzugeben.
FWIW, hier ist etwas code, den ich arbeitete für eine nicht-rekursive topologische Sortierung.