Suchen Sie nach einem guten Ansatz, um eine Breathth-First Traversal zwischen zwei Knoten zu verfolgen, ohne etwas über den Graphen zu wissen. Versus Depth-First (wo Sie den Pfad wegwerfen können, wenn er nicht herauskommt), haben Sie möglicherweise einige "offene" Möglichkeiten während des Traversierens.C# Graph Traversal - Tracking-Pfad zwischen zwei beliebigen Knoten
Der naive Ansatz besteht darin, einen Baum mit dem Quellknoten als Root und all seinen Verbindungen als Kind zu erstellen. Je nachdem, wie viel Platz Sie haben, müssen Sie möglicherweise Zyklen ausschließen. Sie können dies mit einer Bitmap tun, bei der jedes Bit einem bestimmten Knoten im Diagramm entspricht. Wenn Sie den Zielknoten erreichen, können Sie den übergeordneten Links zurück zum Stamm folgen und das ist Ihr Pfad. Da Sie zuerst gehen, sind Sie versichert, dass es ein kürzester Weg ist, selbst wenn Sie Zyklen nicht beseitigen.
Für eine Breitensuche müssen Sie mindestens zwei Dinge speichern. Einer ist der Satz von bereits besuchten Knoten und der andere ist der Satz von Knoten, die direkt von den besuchten Knoten erreichbar sind, aber nicht selbst besucht werden. Dann verschiebst du die Zustände von letzterem auf ersteren und fügst ihm neu erreichbare Zustände hinzu. Wenn Sie einen Pfad vom Stamm zu einem oder mehreren Knoten benötigen, müssen Sie auch einen übergeordneten Knoten für jeden Knoten (außer dem Stamm) in den oben genannten Sätzen speichern.
Normalerweise wird die Vereinigung der Menge der besuchten Knoten und der Menge der nicht besuchten Kindknoten (d. H. Die Menge der gesehenen Knoten) in einer Hash-Tabelle gespeichert. Dies soll in der Lage sein, schnell zu bestimmen, ob ein "neuer" Zustand vorher gesehen wurde oder nicht, und ihn zu ignorieren, wenn dies der Fall ist. Wenn Sie eine wirklich große Anzahl von Zuständen haben, benötigen Sie möglicherweise ein Bit-Array (wie von Joseph Bui (57509) erwähnt), aber wenn Ihre Zustände (direkt oder indirekt) als Indizes für dieses Array verwendet werden können, müssen Sie einen Hash verwenden Funktionen, um Zustände zu Indizes zuzuordnen.In letzterem Fall könnten Sie bestimmte Zustände vollständig ignorieren, da sie auf den gleichen Index wie ein anderer (und sichtbarer) Knoten abgebildet sind, also sollten Sie vorsichtig damit sein, auch um einen Pfad zu erhalten Sie müssen immer noch die übergeordnete Information speichern, die die Verwendung des Bit-Arrays ziemlich negiert.
Die Gruppe der nicht besuchten, aber gesehenen Knoten kann als Warteschlange gespeichert werden. (Bit-Arrays sind für diesen Satz nicht nützlich, da der Array wird meistens leer sein und das Finden des nächsten gesetzten Bits ist relativ teuer.)
Ich habe gerade eine Lösung over here eingereicht, die auch für diese Frage gilt.
Grundsätzlich habe ich nur eine einzige Liste (ein Stapel wirklich) der besuchten Knoten. Fügen Sie der Liste einen Knoten hinzu, bevor Sie eine Lösung rekursiv oder speichern. Entfernen Sie immer direkt aus der Liste.
Wenn Sie .NET 3.5 verwenden, sollten Sie die Option Hashset verwenden, um zu verhindern, dass doppelte Knoten erweitert werden. Dies geschieht, wenn in Ihrem Diagramm Zyklen vorhanden sind. Wenn Sie Kenntnisse über den Inhalt des Diagramms haben, ziehen Sie in Erwägung, A* search zu implementieren, um die Anzahl der Knoten zu reduzieren, die erweitert werden. Viel Glück und ich hoffe, es klappt für dich.
Wenn Sie immer noch ein Fan von Treeware sind, gibt es viele ausgezeichnete Bücher zum Thema Graphen und Graphen Suche wie Künstliche Intelligenz: Ein moderner Ansatz von Peter Norvig und Stuart Russell.
Die Links in meiner Antwort erscheinen, einen Fehler zu haben sind sie Hashset: http://msdn.com/en-us/library/bb359438.aspx und A * Suche: http://en.wikipedia.org/wiki/A*_search_algorithm