Festlänge zwischen zwei Graphenknoten festgelegt

Question

Gibt es einen Algorithmus, der, wenn er zwei Knoten in einem Diagramm gegeben hat, eine Route zwischen ihnen findet, die die angegebene Anzahl von Hopfen nimmt? Jeder Knoten kann mit jedem anderen verbunden werden.

Die Punkte befinden sich im Moment im 2D -Bereich, daher bin ich mir nicht sicher, ob ein Diagramm der beste Ansatz ist.

Answer 1

Wenn Sie Knoten haben, um Routen in Hops zu finden, ist ein Diagramm wahrscheinlich der richtige Ansatz. Ich bin mir nicht sicher, ob ich verstehe, was Sie tun und was die Einschränkungen sind, insbesondere in Bezug auf "Jeder Knoten kann mit jedem anderen verbunden werden", was ein bisschen offen erscheint.

Ignorieren dies jedoch; mit einer gewissen Grafikdarstellung:

Es scheint, als würde man am ersten Knoten beginnen und eine Tiefe erste Suche von dort aus durchführen und eine Suche beenden, wenn (a) die aufgenommenen Hopfen größer sind als Ihre angegebene Nummer oder (b) wir am zweiten Knoten angekommen sind. Dies bestimmt den ersten (nicht nur) Pfad, der die beiden Knoten in (höchstens) so viele Hopfen verbindet.

Wenn es sich genau um den angegebenen Hopfen handeln muss, beenden Sie einen Zweig der Suche, wenn die Hopfen vorbei sind, und beenden Sie mit Erfolg, wenn Sie auch beim zweiten Knoten angekommen sind.

Answer 2

Hast du es versucht Iteratiertes DFS?

Answer 3

Dummer Ansatz: (Datenstruktur ist eine Array von Stapeln). Dies ist im Grunde genommen die Breite zuerst (BFS) bis zur Tiefe n, außer dass Sie die besuchten Knoten nicht von der weiteren Suche ausschließen, wenn Sie zulässig sind (Sie haben nicht geklärt, aber ich gehe davon aus) ausschließt.

1. Drücken Sie den Startknoten auf einen Stapel, der im Array am Index 0 gespeichert ist (Index = Tiefe)

2. Für jede Ebene/Index "l" 0-n:

   Finden Sie für jeden Knoten auf einem Stapel, der auf dem Level "L" gespeichert ist, alle Nachbarn und schieben Sie sie auf einen Stapel, der in Level "L+1" gespeichert ist.

   Wichtig: Wenn Ihre Aufgabe ermöglicht, Pfade zu finden, die Loops enthalten, überprüfen Sie nicht, ob Sie bereits einen von Ihnen hinzugefügten Knoten besucht haben. Wenn es keine Schleifen zulässt, verwenden Sie einen Hash von besuchten Knoten, um keinen Knoten zweimal hinzuzufügen **

3. Halten Sie an, wenn Sie Level "N-1" beenden.

4. Schleifen Sie über alle Knoten, die Sie gerade zum Stack bei Index "N" hinzugefügt haben, und finden Sie Ihren Zielknoten. Wenn gefunden: Erfolg, wenn nicht, kein solcher Weg.

Bitte beachten Sie, dass Sie, wenn durch "jeder Knoten angeschlossen werden kann", ein vollständig verbundenes Diagramm implizieren, es gibt eine mathematische Antwort, bei der nicht tatsächlich Knoten besucht werden

(Die Formel ist jedoch zu lang, um im Text-Eingangsfeld von Stackoverflow zu schreiben)