Route in Grafik mit spezifischer Länge von einem Punkt

Question

Ich habe eine Methode "Verbindung (int n)", die mir alle Zellen Nummer, die Beziehung mit der Zellennummer "n" haben jetzt will ich eine Methode, die mir alle Routen gibt mit einer bestimmten Länge "myLength", die von der Zellennummer "start" und nur in einer Richtung (wie es üblich ist) ich meine, wir sind nicht erlaubt, einige Zellen mehr als einmal zu übergeben Vielen Dank im Voraus für Ihre Hilfe PS Ich kann Kartenwerkzeuge, Diagrammwerkzeuge, ... mit grundlegenden Werkzeugen nicht benutzen bitte

Answer 1

Sie suchen nach BFS.

Modell Ihr Problem als ein graphG = (V,E) so dass V = {1,...,n} [alle möglichen Werte] und E = { (u,v) | connection(u) returns v } [es eine Verbindung zwischen u und v mit Ihrer connection() Methode]

Neben dem Standard BFS, müssen Sie Fügen Sie eine weitere Stoppbedingung hinzu, wenn Sie die begrenzte Länge erreicht haben.

EDIT:
Beachten Sie, dass diese Lösung voraus, dass Sie suchen einen Weg up-to Länge und nicht genau Länge.
BFS funktioniert hier nicht für das Zählerbeispiel eines clique, wenn Sie genau der Länge wollen.

Um alle Ecken zu erhalten, die einen einfachen Weg von genau Länge haben - Sie werden wahrscheinlich eine DFS benötigen, die Schleifen vermeidet [kann durch die Aufrechterhaltung einer set erfolgen, die bei jeder Iteration geändert wird], aber jede Ecke mehr erkunden kann dann Einmal.