Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:doerfer:start [07.12.2022 12:41] – angelegt Frank Schiebel
+++ faecher:informatik:oberstufe:graphen:doerfer:start [07.12.2022 12:57] (aktuell) – Frank Schiebel
@@ Zeile 13: / Zeile 13: @@
 Die Hauptstraße ist immer befahrbar. Unten ist das Straßennetz abgebildet. Die Hauptstraße führt zu Dorf A ganz links oben.
+{{ :faecher:informatik:oberstufe:graphen:doerfer:berge.drawio.png?600 |}}
+**(A)** Gib für jede andere Straße ihren Zustand an.
+Mit Hilfe des folgenden Algorithmus kann man den Zustand der Straßen automatisch ermitteln:
+  - Setze alle Straßen auf "nicht entscheidbar".
+  - Kennzeichne alle Straßen von einem unerreichbaren Dorf zu einem erreichbaren Dorf als "nicht befahrbar".
+  - Für jede Straße S zwischen zwei erreichbaren Dörfern:
+    - Markiere S als "nicht befahrbar".
+    - Bestimme die Anzahl der Dörfer, die von Dorf A aus über "befahrbare" oder "nicht entscheidbare" Straßen erreichbar sind (inklusive A selbst).
+    - Stimmt die Anzahl mit der Anzahl der Dörfer ohne "SOS" überein, setze S auf "nicht entscheidbar". Andernfalls setze S auf "befahrbar".
+**(B)** Begründe, warum eine Straße zwischen einem erreichbaren und einem nicht erreichbaren Dorf auf jeden Fall auf "nicht befahrbar" gesetzt werden muss.
+**(C)** Erläutere die Breitensuche und wie sie in Schritt 3.b) zur Bestimmung der erreichbaren Dörfer eingesetzt werden kann.
+**(D)** Implementiere die Methode ''bestimmeStrassenzustaende(g: Graph, startknoten: Knoten)'', die den
+Straßenzustand aller Straßen als Status der Kanten im Graphen speichert. Knoten, die Städte mit "SOS" repräsentieren, sind markiert. Sie können davon ausgehen, dass die Methode ''bestimmeAnzahlErreichbare(startknoten: Knoten): int'', die die Anzahl
+der erreichbaren Städte wie in Schritt 3.b) beschrieben bestimmt, schon fertig implementiert ist.
+{{ :faecher:informatik:oberstufe:graphen:doerfer:auswahl_421.png |}}