Weg suchen bei Adjazenzmatrix

[nerdprogrammier]

Hallo liebe Forum-Mitglieder :shock:,

Ich hätte eine Frage bezüglich einer Methode Weg suchen in einem Graphen in Java.
Die Methode Weg suchen (String start, String ende) sucht einen Weg zwischen zwei Knoten in einer Adjazenzmatrix. Könnt ihr mir weiterhelfen?
Ich weiss echt nicht wie ich das Problem angehen soll ;(

Vielen Dank im Vorraus und schöne Grüße,

nerdprogrammier

 

[Gast2]

Beispielsweise per Dijkstra oder A* Algorithmus.

 

[The_S]

Naja, den Graphen hast du ja durch die Matrix abgebildet. Gibt dann Algorithmen wie Sand am Meer, die Wege in einem Graphen von einem Konten zu einem anderen Suchen. Da du nicht mal auf den kürzesten, sondern nur auf irgendeinen Weg angewiesen bist, kannst du das sogar ganz primitiv via Backtracking lösen.

Wähle einen Startknoten, wähle einen zufälligen Nachbarn und von diesem wiederum einen zufälligen Nachbarn, usw. bis du am Zielknoten angekommen bist. Falls du nicht am Zielknoten angekommen bist, gehe einen Schritt zurück und versuche einen anderen Nachbarn, gibt es auch hier keine Wege mehr, gehe noch einen Schritt zurück, ...