Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
SozialesNetwerk
Wenn ich mit mir selbst befreundet bin, ist die Distanz dann 1 oder 0?
Weil unsere Tutorin meinte, die Distanz ist 1. Als ich mich mit ein paar anderen unterhalten habe wurde mir gesagt, dass die Distanz 0 ist.
Die Freundschaft zu dir selbst hat Distanz 0.
Ich denke auch, die Distanz, die hier definiert ist, ist so gedacht, dass sie eine Metrik bildet.
ich habe Problem mit Teil e. Wie kann ich Distanz berechnen?
Freundschaft ist wie ein Weg.
A und B sind Freunde. B und C sind Freunde. A und C sind keine Freunde. Z hat außer sich selbst, keine Freunde.
Sei d(x,y) die Distanz zwischen x und y.
d(A,A) = 0 , man ist immer mit sich selbst befreundet. Die Methode gibt für e => 0 true zurück.
d(A,B) = 1; die Methode gibt für e >= 1 true zurück, sonst false,
d(B,C) = 1; die Methode gibt für e >= 1 true zurück, sonst false,
d(A,C) = 2; die Methode gibt für e >= 2 true zurück, sonst false,
d(A,Z) nicht definiert. Z hat keine Freunde. Daraus folgt: Die Methode gibt für alle e false zurück.
[color=limegreen]Man kann auch sagen, wenn A und C einen gemeinsamen Freund haben beträgt die Distanz zwei, da von A nach C zewi „Wege“[color=gray] (A->B, B->C)
[/color]gegenagen werden. Ist ja denke ich logisch.
Du musst im Prinzip also nur den kürzesten möglichen Weg von A nach bspw. G finden. Für jeden gefundenen „Teilweg“ wächst logischerweise auch die Distanz um 1 an.
Auf Papier gebracht sollte das bei einem Schreibtischlauf eine schöne DIagonale in deinem Array geben.
Man könnte da natürlich auch a lá Ghetto-Methode mit try&error rangehen, aber das ist ja nicht Sinn der Sache 
[/color]
Sag mal, musst du deine Beiträge immer Grün machen?
1 Like
Mal abgesehen davon, dass alles grün ist, ist es auch noch falsch.
Es geht keineswegs darum, den kürzesten Weg zu finden. Es ist nur gefragt, ob es einen Weg mit höchstens dieser Distanz gibt.
Wie da ne Diagonale bei rauskommen soll, ist mir schleierhaft.
Try-&Error ist schon der Weg mit dem man das angehen sollte…
Mir fiele spontan auch keine angemessenere Methode ein, um einen beliebigen Graphen auf Zusammenhang zu testen.
Ja geil, dann weiß ich jetzt auch, warum es mir ‘nen overflow geschmissen hat, weil ich wohl die Aufgabenstellung missverstanden habe 
ja ok, aber damit stehe ich komplett bei Null, weil ich absolut keinen Plan mehr habe 
Ich mein’ ja nur, wenn ich wissen will, ob es einen Weg kürzer als e gibt, dann finde ich im Idealfall den kürzesten Weg und überprüfe, ob er kürzer e ist. Oder etwa nicht?
Denn wenn ich angenommen nicht den kürzesten Weg finde, sprich einen anderen, ebenfalls möglichen, habe ich damit zwar weg>e, allerdings gibt es einen kürzeren (den idealen) Weg, welcher
wenn’s dumm läuft eben kürzer als e ist wodurch sich mein Ergebnis verfälscht und das EST nen Anfall bekommt…
Also muss ich ja wohl den kürzesten Weg finden, um der Aufgabe gerecht zu werden.
Und ja, grün ist toll 
Ich frage mich da nur, wie du mittels rekursion verhinderst, dass du im Kreis läuft, wenn du den kürzesten Weg suchst oO
(nicht, dass sich da nicht auch etwas machen ließe, doch glaube ich, machst du dir da das Leben nur komplizierter als nötig…)
Na gut, mal angenommen, es ist egal, einen möglichen kürzeren Weg “zu übersehen”
wie zum henker messe ich dann die Distanz?
In der Regel kann man bei solchen Fällen in einem boolean-Array speichern, welche Knoten bereits besucht sind. Ist ein Knoten bereits besucht, so wird beim erneuten Besuchen die Methode nicht wieder aufgerufen, ansonsten schon.
Die Distanz kann man messen, indem man der rekursiven Methode einen Parameter übergibt, der zu Beginn 0 ist. Dieser wird bei einem neuen Aufruf um 1 erhöht.
Ok, danke!
Könnte ich theoretisch auch e für jeden Schritt um 1 verkleinern und wenn ich 0 erreiche bevor ich einen Weg gefunden habe habe false zurückgeben?
Klar, warum nicht?
Macht euch das Leben doch nicht so kompliziert.
Wenn man das so macht:
dann läuft man halt mal im Kreis, aber nie endlos. Man findet in diesem Rekursionsfall dann halt keinen Weg (->false), aber ein anderer Fall findet dann schon einen, wenn es denn einen gibt.