Grundaufbau?

[quodlibet]

Hallo zusammen,
ich brauche unbedingt Hilfe bei einer Aufgabe. Bei der ich einfach nicht richtig weiß, wie ich die Datenstruktur passend aufbauen soll.

Es geht um ein Straßennetz mit mehrern Kreuzungen die einfach Integer als Bezeichnung tragen. Von manchen Kreuzungen führen Wege zu der nächsten. Diese Wege gehen dabei immer nur in eine Richtung also es kann geschehen, dass ein Weg von A nach B geht aber nicht von B nach A. Jetzt soll ich ein Programm schreiben, dass mit den Weg von I nach J sucht oder feststellt, dass er nicht existiert. Der Weg soll dann also z.B. so ausgegeben werden: 3 5 18 45 9.
Folgende Bedingungen sind daran gestellt: Das ganze soll ueber eine Tiefensuche ablaufen. Dazu soll ein Feld visited verwendet werden, das angibt welche Kreuzungen bereits besucht wurden und einen Stack visit der noch zu besuchenden Kreuzungen.

Also das Straßennetz habe ich jetzt als int[][] gespeichert. int[j] = 1 wenn ein Weg von i nach j existiert. Jetzt bin ich mir nicht ganz klar darueber ob ich eine Klasse Kreuzung erzeugen muss, aber ich denke schon. Aber wie soll ich diese Kreuzungen dann in einem Stack ordnen, wo ich doch nur auf das letzte Element zugreifen kann. Ab diesem Punkt bin ich jetzt total überfordert.
Und für jeden Tipp bin ich dankbar.

Grüße,
quodlibet

 

[SlaterB]

Wenn du das int[][] benutzt, sind die Kreuzungen ja letztlich nur die Zahlen 1..n, da brauchst du keine Extraklasse, Integer reicht.

In diesem Fall müsstest du für die besuchten Knoten eine Liste führen.
Nur mit eigener Klasse kannst du ein Feld visited direkt einer Kreuzung zuordnen.
Mit eigener Klasse könnte dann auch das Array weg und in jedem Objekt die verbunden Knoten selber aufgeführt werden.

Das Vorgehen:
Du beginnst mit einem Stack, in dem nur I (z.B. 4) drin ist.

Jeder Schritt sieht gleich aus:
Du nimmst das oberste Element aus dem Stack,
fügst es in die Liste der besuchten Kreuzungen ein bzw. setzt visited auf true,
und bestimmst die verbundenen Kreuzungen (z.B. 5, 7, 2).

Ist J darunter bist du fertig, ansonsten die neuen Kreuzungen in den Stack einfügen, aber nur wenn nicht bereits besucht.


Fertig -> wieder von vorne anfangen. Wahrscheinlich mit Kreuzung 5 vom Stack 5, 7, 2.

In jeder Runde wird so mindestens eine Kreuzung komplett abgearbeitet, ist ein Standardalgorithmus.


------

Hmm, wenn man von 5 auch wieder zu 2 kommt, würde man 2 zweimal im Stack haben.
Das ist nicht schön, wahrscheinlich sollte man die Kreuzungen direkt beim Einfügen in den Stack auf 'visited' setzen.
Also solche Details noch beachten, hab wahrscheinlich schon zuviel verraten, selber bauen macht schlau

 

[Anmeldeboykottierer]

Hi,
in deinem (für mich etwas durcheinander geratenem) Beitrag stecken ja ein paar Fragen, mal sehen.
Also erstmal die Datenstruktur, für die du dich entschieden hast dürfte man als Adjazenzmatrix bezeichnen. Es gäbe hier Alternativen (z.B. eine Adjazenzliste), da findest du schnell die Vor- und Nachteile und sicherlich auch ein paar der bekannten Suchalgorithmen.

Was die suche durch Tiefensuch angeht, so solltest du kurz überlegen was Tiefensuch bedeutet.
Deine Adjanzenmatrix könntest du (ausgehend von deinem Startknoten) auch als Baum betrachten. Dann hast du ja Kreuzungen, die du erreichen kannst. Diese kannst du also in einem Schritt erreichen. Die haben wiederum Kinder (Kreuzungen, die sie erreichen können usw.).
Tiefensuche (da greift der Name ganz unspektakulär vorweg), geht hier erst in die Tiefe. Sagen wir also du beginnst bei 1 und hast die Kinder 2 und 3, die du direkt erreichen kannst.
2 hat die Kinder 4 und 5, 3 hat die Kinder 5, 6 und 7. Mehr Kreuzugen die verbunden sind gibt es nicht, du suchst den Weg von 1 nach 7.

Von 1 aus wählst du eine erreichbare Kreuzung. Hier fangen wir mit der zwei an, ist nicht die gesuchte Kreuzung, also nimmst du ein Kind von 2, hier also 4. 4 ist auch nicht gesucht, 4 hat aber auch keine Kinder. Dann musst du also zurück springen.
Hier kommt dann der Sinn eines Stacks ins Spiel. Auf einem Stack kannst du immer den besuchten Knoten ablegen, der sieht dann so aus : (1) -> (1,2) -> (1,2,4). Aktuell wäre also die Kreuzung 4, hier kommst du nicht weiter, also entfernst du 4 vom Stack und siehe da, du hast (1,2) also liegt jetzt die Kreuzung ganz oben, von der aus du 4 erreicht hast.
Das ganze ist dann ein sogenannter Back-tracking Algorithmus.

Oh, entschuldige, ich sehe gerade du sollst die noch zu besuchenden ablegen, na ja, selbes prinzip. Du gehst in die Tiefe, überleg dir hier was passiert, wenn du jetzt immer die Kinder ablegst und dort beim obersten Element weitermachst.
Du beginnst mit der 1, legst die erreichbaren Kreuzungen auf den Stack (2,3). Hier nimmst du jetzt das oberste Element und legst die Kinder auf den Stack, entfernst den betrachten Knoten (2,5,6,7) jetzt würdest du bei 7 (also in der Tiefe) weiter machen.

Ja, das ist auch schon alles. Obwohl es damit die Lösung einer Aufgabe ist (was in Foren nie gerne gesehen ist), hoffe ich dass du das so auch verstehst. Spätestens wenn du eine Klausur schreibst oder es mal Anwenden musst (Stacks findet man immer wieder) wirst du halt das Wissen brauchen. Deswegen ruhig nachfragen, wenn noch was unklar ist.

Gruß Der Anmeldeboykottierer

 

[quodlibet]

Ja ich muss zugeben mein Beitrag war in der Tat sehr verwirrt aber genauso sah es in meinem Kopf aus. Ich habe durchaus eine Ahnung gehabt was Backtracking, Bäume und Tiefensuche ist. Aber bei Bäumen war das ja irgendwie mit einfärben für besucht, unbesucht und noch nicht komplett verarbeitet und da kam es mir dann irgendwie in den Sinn ich bräuchte eine Klasse Kreuzungen und das ging dann wohl nicht mehr aus meinen Kopf.

Ich danke dir, jetzt ist alles wieder klar geordnet und der Rest dürfte kein Problem sein.