Klausur WS15 A7.b mszt

Bachelor Algorithmen und Datenstrukturen
1

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.

2

Klausur WS15 A7.b mszt
Ich hatte bei der Lösung der Aufgabe Schwierigkeiten, weil sie mir als zu trivial vorkam, weshalb ich dachte, dass ich sie falsch verstanden habe. Die Lösung bestätigt mir aber anscheinend meine Annahme. Würde die Methode bei einem zusammenhängenden Graphen nicht das gleiche wie sammle berechnen? Die Methode macht doch eigentlich nur Sinn für nicht zusammenhängende Graphen, die selbst Teilgraphen besitzen die zusammenhängend sind, oder?

Edit: Dieser Kommentar in der Lösung:

//einfacher waere hier statt den letzten drei zeilen folgendes:
//sammle(am,k,ergebnis.get(k), bk); //!!

ist doch falsch, oder? Man versucht hier auf ein Listenelement zuzugreifen, dass nicht existiert. Weil die Liste ja initial leer ist und nicht mit k leeren Sets gefüllt. Zudem würde man damit ja auch nur auf das k-te Element in der Liste zugreifen, was nicht zwangsweise mit dem zu k korrespondierenden Set übereinstimmen muss.

3

7.c
Hier heißt es:

if (!(vs.contains(i) && vs.contains(j)))

Sollte das hier nicht reichen:

if (!(vs.contains(i))

Ob eine Kante entfernt wird ist nicht abhängig davon, ob das Element am anderen Ende enthalten ist oder nicht. Es reicht schon, dass die erste Komponente nicht enthalten ist. Logisch wertet es auch zum gleichen aus: Wenn i nicht enthalten ist dann löscht er die Kante sowieso unabhängig ob vs.contains(j) true oder false ist. Nicht falsch, aber redundant. Und macht es irgendwie unverständlicher, da man plötzlich noch den Knoten j betrachtet der im späteren Durchlauf ohnehin nochmal betrachtet wird. Das würde nur Sinn machen, wenn man auch die Schleife gleichzeitig bei jedem Durchlauf verkleinert.

Edit:
Das hier:

if (am[i][j]){...}

müsste doch auch überflüssig sein, oder? Ob ich etwas, das ohnehin schon false ist auf false setzte macht keinen unterschied, es sparrt evtl. ein paar Schritte, ist aber nicht notwendig.