Breitensuche mit Hop-Distanzen in Java - Wie implementieren?

[Andy_93]

Hallo zusammen,

ich bin vor Kurzem zum ersten Mal auf den Begriff "Hop-Distanzen" gestoßen und habe dabei erfahren, dass man diese Hop-Distanzen zusammenbringen kann mit der Breitensuche (BFS), also dass die BFS bei einem ersten beliebigen Knoten beginnt und dabei die Hop-Distanzen zu allen erreichbaren Knoten berechnet.

Zunächst musste ich mal nachlesen, was das Wort "Hop-Distanzen" überhaupt meint. Wenn ich das richtig verstanden habe, bedeutet es: bei der Hopdistanz zwischen zwei Knoten handelt es sich um die kleinste Anzahl von "Sprüngen" von Knoten zu Nachbarknoten, um vom Start- zum Zielknoten zu gelangen.
Erinnert nur mich das an das Thema "kürzeste Wege" bei Graphen, oder geht es noch anderen so?

Was mir noch nicht klar ist, ist wie ich diese Hop-Distanzen als Code schreiben würde (z. B. in Java) und ihn dann mit dem Code der BFS zusammenbringen könnte. Es wäre toll, und ich wäre dankbar, wenn jemand Code dafür liefern könnte - vielleicht angelehnt an folgendes Bsp.: Gegeben ist ein Graph mit folgenden Startknoten (1. Zahl) und Endknoten (2. Zahl) sowie zugehörigem Kantengewicht (3. Zahl):

Startknoten Endknoten Kantengewicht
5 7 3
7 5 3
9 4 8
4 7 2
7 4 2
0 1 1

 

[httpdigest]

Sag doch frei heraus: "Ich habe eine Aufgabe bekommen und komme bei Schritt XYZ nicht weiter. Kann mir wer helfen? Die komplette Aufgabe lautet ganz genau so: <<kompletter und unverfälschter Wortlaut der Aufgabe>>".
Denn aktuell ist leider komplett unklar, was eigentlich das Ziel ist. Jemand soll dir Code für irgendwas mit Hop-Distanzen geben, um was genau zu tun?

 

[mihe7]

Der Zusammenhang zwischen der Breitensuche und der Hop-Distanz ist relativ klar: die Tiefe des Knotens im Suchbaum ist die Hop-Distanz zur Wurzel. Da die Breitensuche alle Knoten einer Ebene zuerst betrachtet, ist die Distanz eines jeden Knotens zur Wurzel minimal. Die Suche kann also enden, sobald der Zielknoten erstmalig erreicht wurde.

 

[Andy_93]

die Tiefe des Knotens im Suchbaum ist die Hop-Distanz zur Wurzel

Vielen Dank für diesen Erläuterung. So wird mir der Zusammenhang schon nachvollziehbarer.
Nur um sicher zu sein: Ist es dann so, dass man zur Berechnung der Hop-Distanz keinen separaten Code bzw. Methode braucht, sondern die Hop-Distanz ganz normal im Rahmen der BFS erkennen kann, d.h. die Breitensuchnummer, die ein Knoten bekommt ist i. d. R. seine Hop-Distanz zur Wurzel?

Jemand soll dir Code für irgendwas mit Hop-Distanzen geben, um was genau zu tun?

Bzgl. httpdigest: Vielleicht habe ich die Schwierigkeit bzw. die Frage unbewusst nicht transparent bzw. verständlich genug formuliert. Dies war jedoch nicht meine Intention. Um es Dir hoffentlich angenehmer zu machen, versuche ich es nochmal: Implementiere die Funktion / Methode BFS, die die Breitensuche beginnend bei einem Startknoten ausführt und dabei die Hop-Distanzen zu allen erreichbaren Knoten berechnet.

 

[mihe7]

Ist es dann so, dass man zur Berechnung der Hop-Distanz keinen separaten Code bzw. Methode braucht, sondern die Hop-Distanz ganz normal im Rahmen der BFS erkennen kann

Genau. Von einem Knoten zu einem anderen gehen ist ein "Hop". Das entspricht der Suche des kürzesten Pfades, wenn alle Kanten das gleiche Kantengewicht (z. B. 1) haben, also praktisch keine Gewichtung existiert.