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.
Übungsblatt 12
Hallo Leute habe eine Frage bzgl. der ersten Aufgabe.
Ich bekomme 2x
A = B cost: 1
B = E cost: 2
E = C cost: 3
D = C cost: 1
im Testfall, was in sofern meiner Meinung nach richtig ist.
Kriege aber im EST einen Fehler im public test
Kann es sein dass ich etwas in der Aufgabenstellung falsch verstanden habe?
Oder kann es sein dass im public Test schon die Laufzeit mit überprüft wird?
Habe zwar PQ verwendet, aber bin mir noch unsicher ob es nicht optimaler ginge.
MfG Shinai
Wenn ich mich nicht irre, ist die Priority Queue eine FIFO-Struktur, wenn es zu einem bestimmten Schritt des Algorithmus von Prim mehr als eine nicht besuchte erreichbare Kante mit dem minimalen gleichen Gewicht gibt. Deswegen würde ich sagen, dass die Lösung
AB, cost 1
AE, cost 2
EC, cost 3
CD, cost 1
korrekt ist, wenn man Kanten nach alphabetischer Ordnung einfügt.
Ich füge PQ A hinzu
danach B
beide haben den selben Wert
wenn ich dann getSmallestNode() mache
bekomme ich B
In sofern kann es keine FIFO Struktur sein, oder?
Die [m]compareTo()[/m]-Methode der inneren Klasse Element liefert bei gleichen Elementen die Differenz der Hashwerte zurück. Ist also keine FIFO-Queue bei Gleichheit, die Reihenfolge ist dann von den hashwerten abhängig und mehr oder weniger zufällig.
Wichtig ist bei der Aufgabe also nur, dass ein minimaler Spannbaum rausfällt. Dein Spannbaum ist eine mögliche Lösung.
Hmm wieso kriege ich dann “Error in given test case” in EST?
Hast du vielleicht bei der b) nicht beachtet, dass der Graph ungerichtet sein muss, also dass wenn der Knoten A eine Kante nach B kennt, B auch eine nach A kennen muss? Beim Output der main wird das übersprungen, deswegen sieht man es da nicht.
Dafür sorgt doch schon die Methode addEdge() von Node
Wird da eine Edge zu dem einen Knoten hinzugefügt, dann wird gleichzeitig auch eine zum Anderen erstellt.
Hab mal alle Edges ausgeben lassen:
Edge from: A to: B
Edge from: A to: B
Edge from: B to: E
Edge from: B to: E
Edge from: E to: C
Edge from: E to: C
Edge from: D to: C
Edge from: D to: C
Es gibt also wirklich 2 Kanten.
(ist immer doppelt weil bei der Methode addEdge() die selbe Kante genommen wird statt die Inverse:
A->B, B->A)
In sofern müsste meine b) schon stimmen…
hier ist nochmal meine komplette Ausgabe falls es hilft:
Edges of the minimal spanning tree:
A = B cost: 1
B = E cost: 2
E = C cost: 3
D = C cost: 1
Sum of costs of the spanning tree: 7
Edges of the minimal spanning tree sub graph:
A = B cost: 1
B = E cost: 2
E = C cost: 3
D = C cost: 1
Sum of costs of the spanning tree: 7
Achja und die andere Einzelaufgabe kann man auch noch nicht hochladen.
Könnte das mal wer fixxen? 
servus Leute ih muss ja mal wieder sagen das Übungsblatt ist naja hust so gut wie unsere deutsche Nationalmannschaft gestern Fussball gespielt hat:
Laut den Vorlesungs-/Übungsfolien sind () gerichtete Graphen, im Aufgaben Text steht aber das es ein ungerichteter Graph sein soll:
Gegeben sei der folgende ungerichtete aber gewichtete Graph G = (V; E) in Mengendarstellung mit Kantenmenge E = f (C; 63;B), (G; 30; F), (A; 27;B), (G; 18;D), (C; 18;A), (Z; 15;H), (K; 12;H), (F; 12;E), (D; 12;E), (Z; 9;K), (C; 9;G), (B; 9;E), (K; 6; F), (H; 6;D) g, dabeistellt (vi; dji ; vj) eine ungerichtete Kante zwischen den Knoten vi und vj mit Kantengewicht dji dar.
Was stimmt nun?
Für die Teilaufgaben a) bis d) ist der Graph als ungerichtet zu betrachten.
Für die Teilaufgabe e) ist ein Teilgraph davon als _gerichtet zu betrachten.
Edith möchte noch warnen: Lernt keine Schreibweisen auswendig, da nicht jeder auf dieser weiten Welt immer die gleiche Schreibweise verwendet:
ungerichtete vs. doppelt gerichtete Kanten (a, b)
oder
ungerichtete Kante {v,w}
während
die Vorlesung in der „Mengenschreibweise“ [m][v,w][/m] verwendet
done
Ich weiss ja nicht welche der Abgaben Deine ist.
Aber auf Grund einer Abgabe deren Ausgabe korrekt war, obwohl die Datenstruktur kaputt war (das wird vom echten Test erkannt),
gibt es nun eine weitere Ausgabe im gegebenen Test und einen klaren Hinweis auf den Fehler in der Aufgabenstellung.
Danke, habs nun hinbekommen
Abend Leute,
bei der 12.2 ist das eher so gemeint (A, B), (A, B, G), (B, G) etc… oder (A, B, G), (C, D, E, F…).
Habs nach der 2ten Variante gemacht also nur die größtmöglichen und bekomm n Error in given Testcases.
Teste deine Implementierung am besten auch für andere Graphen. Was gibt außerdem deine Methode bei graph = null sowie beim leeren Graphen (graph.size() = 0) aus und hast du irgendwelche Elemente aus dem Graphen gelöscht?
Nee ich glaub ich habe den Fehler, ich betrachte aktuell nämlich einzelne knoten ohne weitere Verbinungen nicht. Ich glaube wenn ich das behebe müsste alles ok sein
Bei graph ==null —> IllegalArgumentException und fur graph.size ()==0 gibts eine neue Liste mit 0 Elementen
Sodele nochmal fuer mich zum Verstaendnis.
In Aufgabe 12.2, sollen die laengsten Strecken als extra Liste ausgeben werden.
also aus:
[A = B cost: 0] : A
[A = B cost: 0, B = G cost: 0] : B
[D = C cost: 0, C = E cost: 0, C = F cost: 0] : C
[D = C cost: 0, D = E cost: 0, D = F cost: 0] : D
[D = E cost: 0, C = E cost: 0, E = F cost: 0] : E
[D = F cost: 0, C = F cost: 0, E = F cost: 0] : F
[B = G cost: 0] : G
mach:
a-b-g
d-c-e-f
h
richtig?
Greets
„Laengste Strecke“ klingt bisschen falsch. Es muss keinen (Knoten disjunkten) Pfad durch eine Komponente geben, der alle Knoten der Komponente besucht.
Das stimmt trotzdem.
Blatt 12 scheint das letzte zu sein oder?