Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:eulerzug:start [09.11.2022 22:03] – [Ü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.
+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...
+  - Knoten / Kanten markieren
+  - Bei Knoten eine Zahl eintragen
+  - Knoten einfärben
+  - Alle Knoten der Reihe nach durchgehen
+  - Einen beliebigen Knoten als Startknoten wählen
+  - Zum Nachbarknoten springen
+  - Eine ToDo-Liste noch zu bearbeitender Knoten anlegen
-https://codeberg.org/qg-info-unterricht/zpg-graphentester
+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.
+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**.
+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
+Ende der Liste eingefügt werden.
+++++
+++++ 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:*}}