Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:eulerzug:start [09.11.2022 22:05] – [Überprüfung des Zusammenhangs] Frank Schiebel
+++ faecher:informatik:oberstufe:graphen:zpg:eulerzug:start [14.11.2022 19:14] (aktuell) – [Einführung in den Graphentester] Frank Schiebel
@@ Zeile 1: / Zeile 1: @@
-====== Einführung in den Graphentester ======
@@ Zeile 44: / Zeile 43: @@
 {{:aufgabe.png?nolink  |}}
 === (A1) ===
-Finde eine algorithmische Vorgehensweise, wie der Frosch herausfinden kann, ob der Graph zusammenhängend ist. Um dieses Ziel zu errreichen, hat der Frosch die folgenden Werkzeuge und Fähigkeiten zur Verfügung.
+Finde eine algorithmische Vorgehensweise, wie der Frosch herausfinden kann, ob der Graph zusammenhängend ist. Um dieses Ziel zu erreichen, hat der Frosch die folgenden Werkzeuge und Fähigkeiten zur Verfügung:
 Der Frosch kann...
@@ Zeile 56: / Zeile 55: @@
-Lade dir den [[https://codeberg.org/qg-info-unterricht/zpg-graphentester|Graphentester herunter]] und versuche einen Algorithmus zu finden.
+Lade dir den [[https://codeberg.org/qg-info-unterricht/zpg-graphentester|Graphentester herunter]] und versuche im Experimentiermodus einen Algorithmus zu finden, der herausfindet, ob ein gegebener Graph zusammenhängend ist oder nicht.
-++++ Hilfestellung 1:
+Notiere den Algorithmus als Text oder in Pseudocode.
+++++ Hilfestellung 1 |
+Man startet bei einem beliebigen Knoten. Diesem gibt man die Nummer 1 und **markiert** ihn als
+fertig bearbeitet (''Markieren'' & ''Besuchen'').
+Alle seine Nachbarknoten fügt man einer ToDo-Liste hinzu und kennzeichnet
+sie mit ''Besuchen'', um auszudrücken, dass sie der ToDo-Liste schon hinzugefügt, aber noch nicht
+fertig bearbeitet ("besucht") sind.
+Dann nimmt man den nächsten Knoten aus der ToDo-Liste, nummeriert ihn und markiert ihn als
+fertig bearbeitet. Alle seine **nicht** als **besucht** oder **fertig** bearbeitet gekennzeichneten Nachbarn
+fügt man der ToDo-Liste hinzu und kennzeichnet sie als **besucht**.
-Man startet bei einem beliebigen Knoten. Diesem gibt man die Nummer 1 und markiert ihn als
-fertig bearbeitet. Alle seine Nachbarknoten fügt man einer ToDo-Liste hinzu und kennzeichnet
-sie als besucht, um auszudrücken, dass sie der ToDo-Liste schon hinzugefügt, aber noch nicht
-fertig bearbeitet sind.
-Dann nimmt man den ersten Knoten aus der ToDo-Liste, nummeriert ihn und markiert ihn als
-fertig bearbeitet. Alle seine nicht als besucht oder fertig bearbeitet gekennzeichneten Nachbarn
-fügt man der ToDo-Liste hinzu und kennzeichnet sie als besucht.
 Diese Schritte werden so lange wiederholt, bis die ToDo-Liste leer ist.
 Entspricht die Nummer des zuletzt nummerierten Knotens der Anzahl der Knoten im Graph, ist
 der Graph zusammenhängend. Ist sie kleiner, hat man nicht alle Knoten erreicht und der Graph
 besteht aus mehreren Zusammenhangskomponenten.
 Varianten:
 Beim Einfügen in die ToDo-Liste können neue Knoten entweder am Anfang der Liste oder am
@@ Zeile 78: / Zeile 85: @@
+++++ Hilfestellung 2 |
+== Pseudocode des Algorithmus, um den Zusammenhang zu testen ==
+Der hier beschriebene Algorithmus bestimmt die Anzahl der vom Startknoten aus erreichbaren
+Knoten und vergleicht sie mit der Gesamtzahl der Knoten.
+<code>
+Zusammenhang des Graphen:
+Markiere den Startknoten als besucht
+Erzeuge eine leere ToDo-Liste und füge den Startknoten hinzu
+Setze nr auf 0
+Wiederhole solange die ToDo-Liste nicht leer ist
+  Erhöhe nr um 1
+  Nimm den ersten Knoten aus der ToDo-Liste heraus
+  Markiere ihn und gib ihm die Nummer nr
+  Wiederhole für jeden seiner Nachbarn
+    Falls der Nachbarknoten noch nicht besucht ist
+      Kennzeichne ihn als "besucht"
+      Füge ihn am Ende der ToDo-Liste hinzu
+    Ende-Falls
+  Ende-Wiederhole
+Ende-Wiederhole
+Falls nr = Anzahl der Knoten im Graph
+  Der Graph ist zusammenhängend
+Sonst
+  Es gibt mehrere Zusammenhangskomponenten
+Ende-Falls
+</code>
+Variante: Statt am Ende der ToDo-Liste können die Nachbarn auch am Anfang der ToDo-Liste
+eingefügt werden.
+++++
+==== Dateien ====
+{{simplefilelist>:faecher:informatik:oberstufe:graphen:zpg:eulerzug:*}}