Informatik 11

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Zuletzt angesehen: • ki • navigationmenu • stellenwertsysteme
graphen:tiefensuche:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Nächste Überarbeitung		Vorhergehende Überarbeitung
graphen:tiefensuche:start [2023/10/11 07:11] – angelegt Martin Pabstgraphen:tiefensuche:start [2023/10/13 07:11] (aktuell) – Martin Pabst
Zeile 1: Zeile 1:
 ===== Tiefensuche (für interessierte Schüler/innen) ===== ===== Tiefensuche (für interessierte Schüler/innen) =====
 +<WRAP center round info 60%>
 +Die Behandlung der Tiefensuche ist **im Lehrplan leider nicht vorgesehen**. Weil dieser Algorithmus sich sehr gut eignet, um einen Einblick in die Programmierung mithilfe von rekursiven Methodenaufrufen zu bekommen, finden interessierte Schüler/innen hier eine Einführung zum Selbststudium. Falls Sie Fragen dazu haben, stehe ich gerne zur Verfügung!
 +</WRAP>
 +
 +{{ youtube>PMMc4VsIacU?large }}
 +
 Wir wollen eine Methode ''istVerbundenRekursiv(int startknoten, int zielknoten)'' schreiben, die genau dann ''true'' zurückliefert, wenn es einen Pfad vom Startknoten zum Zielknoten gibt. Wir gehen nach folgender Strategie vor: Wir wollen eine Methode ''istVerbundenRekursiv(int startknoten, int zielknoten)'' schreiben, die genau dann ''true'' zurückliefert, wenn es einen Pfad vom Startknoten zum Zielknoten gibt. Wir gehen nach folgender Strategie vor:
   * 1.) Überprüfe, ob ''startknoten == zielknoten''. Falls "ja", gib ''true'' zurück.   * 1.) Überprüfe, ob ''startknoten == zielknoten''. Falls "ja", gib ''true'' zurück.
Zeile 6: Zeile 12:
  
 <WRAP center round info 80%> <WRAP center round info 80%>
-Die Methode folgt einem **uninformierten** Suchverfahren (uninformiert bedeutet hier, dass dem Verfahren über die Einträge der Adjazenzmatrix hinaus keine weiteren Informationen zur Verfügung stehen) mit dem Namen **Tiefensuche** (engl. depth-first search, DFS). "Bei der Tiefensuche wird zunächst jeder Pfad vollständig in die Tiefe beschritten, bevor abzweigende Pfade beschritten werden." (siehe [[https://de.wikipedia.org/wiki/Tiefensuche|den entsprechenden Artikel in Wikipedia, der auch eine schöne Animation dazu zeigt)]]. \\ \\  +Die beschriebene Methode nennt man **Tiefensuche** (engl. depth-first search, DFS). "Bei der Tiefensuche wird zunächst jeder Pfad vollständig in die Tiefe beschritten, bevor abzweigende Pfade beschritten werden." (siehe [[https://de.wikipedia.org/wiki/Tiefensuche|den entsprechenden Artikel in Wikipedia, der auch eine schöne Animation dazu zeigt)]]. \\ \\  
-Ein zweites uninformiertes Suchverfahren wäre die **Breitensuche** (engl. breadth-first search, BFS). Bei dieser werden "zunächst alle Knoten beschritten, die vom Ausgangsknoten direkt erreichbar sind. Erst danach werden Folgeknoten beschritten." (siehe [[https://de.wikipedia.org/wiki/Breitensuche|den entsprechenden Artikel in Wikipedia, und die sehr anschauliche Animation dort.)]] \\ \\ +Ein zweites Suchverfahren wäre die **Breitensuche** (engl. breadth-first search, BFS). Bei dieser werden "zunächst alle Knoten beschritten, die vom Ausgangsknoten direkt erreichbar sind. Erst danach werden Folgeknoten beschritten." (siehe [[https://de.wikipedia.org/wiki/Breitensuche|den entsprechenden Artikel in Wikipedia, und die sehr anschauliche Animation dort.)]] \\ \\ 
 Keines der beiden Suchverfahren ist für das allgemeine Problem der Suche in Graphen „besser“ geeignet als das andere. Keines der beiden Suchverfahren ist für das allgemeine Problem der Suche in Graphen „besser“ geeignet als das andere.
 </WRAP> </WRAP>
  
-{{ :graphen:pasted:20211106-220900.png?200}} 
  
  
-Wir entwickeln eine Klasse ''Graph'', die nützliche Methoden zur Verwaltung und Analyse von Graphen bereitstellt.+<WRAP center round tip 50%>
 {{ :graphen:20211107-152623.png?200|}} {{ :graphen:20211107-152623.png?200|}}
- +Den im Testprogramm unten generierten Graphen siehst Du in graphischer Darstellung im Bild rechts. So kannst Du das Programm schrittweise ausführen und gleichzeitig den Programmverlauf am Graphen mitverfolgen.
-<WRAP center round tip 80%> +
-Den im Testprogramm unten generierten Graphen siehst Du in graphischer Darstellung links neben dem Programmkasten. So kannst Du das Programm schrittweise ausführen und gleichzeitig den Programmverlauf am Graphen mitverfolgen.+
 </WRAP> </WRAP>
  
Zeile 83: Zeile 86:
 </HTML> </HTML>
  
-<WRAP center round todo 80%> +<WRAP center round todo 60%> 
-**Aufgaben:** \\ \\  +**Aufgabe (nicht leicht...):** \\ \\  
-  * Erstelle eine Methode ''void adjazenzmatrixAusgaben()'', die die Adjazenzmatrix folgendermaßen auf dem Bildschirm ausgibt: +Erweitere das Programm so, dass die Methoden ''istVerbunden'' in dem Fall, dass sie einen Pfad gefunden hat, diesen in der Form 7->0->1->2->3->4 ausgibt. \\ \\  
-<code> +[[.istverbundenaufgabe:loesung|Lösung]]
-0 1 0 +
-1 0 1 +
-0 1 0 +
-</code> +
-  * Erstelle eine Methode ''istIsoliert(int knoten)'', die genau dann ''true'' zurückgibt, wenn der Knoten isoliert ist (Definition siehe oben). +
 </WRAP> </WRAP>
 +
 +
  
graphen/tiefensuche/start.1697008265.txt.gz · Zuletzt geändert: 2023/10/11 07:11 von Martin Pabst
Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki