Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- graphen:start [2023/10/05 20:16] – Martin Pabst
+++ graphen:start [2023/10/13 07:12] (aktuell) – [Warteschlange (Queue)] Martin Pabst
@@ Zeile 38: / Zeile 38: @@
-===== Adjazenzmatrix =====
-<WRAP center round info 80%>
-Die oben verwendete graphische Darstellung ist zwar anschaulich, für algorithmische Verarbeitung aber häufig eher ungünstig. Eine andere Darstellung von Graphen ist ihre **Adjazenzmatrix** (man nennt zwei Knoten, die durch eine Kante verbunden sind, auch **adjazent**). Dabei wird eine Art Tabelle aufgestellt, deren Spalten- und Zeilenanzahl der Anzahl der Knoten entspricht (die im Folgenden verwendeten Zeilen- und Spaltenbeschriftungen sind nicht Teil der Adjazenzmatrix und dienen nur der Veranschaulichung). Die Adjazenzmatrix enthält dann als Eintrag
-  * 0, wenn es keine Kante zwischen dem links stehenden und dem oben stehenden Knoten gibt
-  * 1, wenn es eine Kante zwischen den Knoten gibt und der Graph ungewichtet ist
-  * ansonsten das Kantengewicht
-</WRAP>
-==== Beispiel 2 ====
-(Adjazenzmatrix eines gerichteten Graphen) \\
-{{ :graphen:pasted:20211106-152817.png?200}}
-^ ^ Knoten 1 ^ Knoten 2 ^ Knoten 3 ^
-^ Knoten 1 | 0 | 0 | 1 |
-^ Knoten 2 | 1 | 0 | 0 |
-^ Knoten 3 | 0 | 0 | 0 |
-==== Beispiel 3 ====
-{{ :graphen:pasted:20211106-153459.png?200}}
-^ ^ Knoten 1 ^ Knoten 2 ^ Knoten 3 ^
-^ Knoten 1 | 0 | 22 | 17 |
-^ Knoten 2 | 22 | 0 | 0 |
-^ Knoten 3 | 17 | 0 | 0 |
-Die Adjazenzmatrix eines ungerichteten Graphen ist immer **symmetrisch bzgl. der Diagonale** von links oben nach rechts unten.
-==== Aufgabe 4 ====
-Modellieren Sie den folgenden Graphen als Adjazenzmatrix.
-{{ :graphen:20211107-152623.png?400 |}}
-[[.aufgabe4loesung:start|Lösung]]
-==== Aufgabe 5 ====
-Zeichne eine graphische Darstellung des durch die folgende Adjazenzmatrix gegebenen Graphen:
-^   ^ A ^ B ^ C ^ D ^ E ^
-| A |   | 8 |   | 5 |   |
-| B |   |   | 6 |   |   |
-| C |   | 2 |   | 4 | 1 |
-| D | 5 |   |   |   |   |
-| E |   |   | 4 |   |   |
-[[.aufgabe5loesung:start|Lösung]]
-===== Modellierung von Graphen durch Adjazenzmatrizen =====
-Graphen werden in Java-Programmen oft implementiert, indem man ihre Adjazenzmatrix in einem zweidimensionalen Integer-Array speichert.
-<WRAP center round info 60%>
-**Zweidimensionales int-Array?** \\ \\
-Du erinnerst Dich vielleicht noch an eindimensionale Arrays, z.B.
-<code java>
-int[] zahlen = new int[7];   //Das Array zahlen enthält 7 Elemente: zahlen[0] bis zahlen[6].
-zahlen[0] = 12;              // speichert im ersten Element die Zahl 12
-zahlen[5] = 4;               // speichert im 6. Element die Zahl 4;
-println(zahlen[5]);   // Gibt das 6. Element aus
-</code>
-Falls Du Dein Wissen über Arrays auffrischen möchtest, [[https://learnj.de/doku.php?id=types:arrays:start|schau' Dir die Wiki-Seite aus Jgst. 10 dazu an!]] \\ \\
-Hier zur Wiederholung eine [[.fingeruebungarrays:start|kleine Fingerübung zu eindimensionalen Arrays]] (Umkehrung eines Arrays). \\
-Ein **zweidimensionales** Array speichert "ein Schachbrett voller Zahlen". Die Speicherung von bspw. $4 \times 3$ Zahlen geht so:
-<code>
-int[][] zahlen = new int[4][3];    // Der erste Index geht von 0 bis 3, der zweite von 0 bis 2
-zahlen[2][1] = 10;
-zahlen[0][2] = 14;
-</code>
-Man kann sich vorstellen, dass das Array ''zahlen'' aufgebaut ist wie ein Schachbrett. Der erste Index bezeichnet die Zeile des Feldes, der zweite die Spalte. Nach Ablauf dieses Programms sieht die Belegung des Arrays so aus:
-^**zahlen**^**0**^**1**^**2**^
-^**0**|0|0|14|
-^**1**|0|0|0|
-^**2**|0|10|0|
-^**3**|0|0|0|
-Im Array gespeichert sind natürlich nur die 12 Werte der blauen Zellen. Die fettgedruckten Zeilen- bzw. Spaltenköpfe dienen nur zur Veranschaulichung.
-</WRAP>
-==== Beispiel 4 - Speicherung eines gerichteten Graphen ====
-{{ :graphen:pasted:20211106-171626.png?300}}
-Das folgende Programm speichert den Graphen rechts als Adjazenzmatrix:
-<HTML>
-<div class="java-online" style="height: 350px; width: 60%" data-java-online="{'withBottomPanel': false, 'id': 'Graph1'}">
-<script type="text/plain" title="Graph 1.java">
-int[][] matrix = new int[4][4];
-matrix[0][1] = 1;
-matrix[1][0] = 1;
-matrix[1][2] = 1;
-matrix[2][3] = 1;
-matrix[3][1] = 1;
-for(int i = 0; i < 4; i++) {
-   for(int j = 0; j < 4; j++) {
-      print(matrix[i][j] + " ");
-   }
-   println();
-}
-</script>
-</div>
-</HTML>
-===== Die Klasse Graph =====
-Wir entwickeln eine Klasse ''Graph'', die nützliche Methoden zur Verwaltung und Analyse von Graphen bereitstellt.
-<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>
-<HTML>
-<div class="java-online" style="height: 70vh; width: 100%" data-java-online="{'withBottomPanel': true, 'id': 'Graph2'}">
-<script type="text/plain" title="Graph.java">
-public class Graph {
-   private int[][] adj;
-   public Graph(int anzahlKnoten) {
-      adj = new int[anzahlKnoten][anzahlKnoten];
-   }
-   public void kanteHinzufügen(int von, int nach) {
-      adj[von][nach] = 1;
-   }
-   public boolean istVerbunden(int startknoten, int zielknoten) {
-      return istVerbundenRekursiv(startknoten, zielknoten, new boolean[adj.length]);
-   }
-   private boolean istVerbundenRekursiv(int startknoten, int zielknoten, boolean[] schonBesucht) {
-      schonBesucht[startknoten] = true;
-      println("Besuche Knoten " + startknoten);
-      if(startknoten == zielknoten) {
-         return true;
-      }
-      for(int i = 0; i < adj.length; i++) {
-         if(adj[startknoten][i] != 0 && !schonBesucht[i]) {
-            if(istVerbundenRekursiv(i, zielknoten, schonBesucht)) {
-               return true;
-            }
-         }
-      }
-      return false;
-   }
-}
-</script>
-<script type="text/plain" title="Testprogramm.java">
-Graph g = new Graph(8);
-g.kanteHinzufügen(0, 1);
-g.kanteHinzufügen(1, 0);
-g.kanteHinzufügen(1, 2);
-g.kanteHinzufügen(2, 3);
-g.kanteHinzufügen(3, 4);
-g.kanteHinzufügen(2, 4);
-g.kanteHinzufügen(4, 2);
-g.kanteHinzufügen(3, 5);
-g.kanteHinzufügen(5, 2);
-g.kanteHinzufügen(5, 6);
-g.kanteHinzufügen(1, 6);
-g.kanteHinzufügen(6, 7);
-g.kanteHinzufügen(7, 0);
-println(g.istVerbunden(4, 1));
-</script>
-</div>
-</HTML>
-<WRAP center round todo 80%>
-**Aufgaben:** \\ \\
-  * Erstelle eine Methode ''void adjazenzmatrixAusgaben()'', die die Adjazenzmatrix folgendermaßen auf dem Bildschirm ausgibt:
-<code>
-1 0
-0 1
-1 0
-</code>
-  * Erstelle eine Methode ''istIsoliert(int knoten)'', die genau dann ''true'' zurückgibt, wenn der Knoten isoliert ist (Definition siehe oben).
-</WRAP>
-===== Tiefensuche =====
-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.
-  * 2.) Überprüfe für jeden von ''startknoten'' aus erreichbaren Knoten ''i'', ob ''istVerbundenRekursiv(i, zielknoten) == true'' ist. Falls "ja", gib ''true'' zurück.
-Dieses Vorgehen kann bei zyklischen Graphen zu einer **unendlichen Methodenaufrufkette** führen. Daher muss der Algorithmus **speichern, welche Knoten er schon besucht hat** und diese bei 2.) ausnehmen. Dies geschieht mittels eines Arrays ''boolean[] schonBesucht'', das für jeden Knoten einen booleschen Wert speichert, der angibt, ob der Knoten schon besucht wurde. Dieses Array wird anfangs in der Methode ''istVerbunden'' instanziert und mit ''false''-Werten befüllt. Diese übergibt die Refernz auf dieses Array an die Methode ''istVerbundenRekursiv''. Bei 1.) wird ''schonBesucht[startknoten] = true'' gesetzt und bei 2.) wird eine Referenz auf das Array ''schonBesucht'' bei jedem weiteren Aufruf von ''istVerbundenRekursiv'' weitergereicht. \\ \\ Die fertigen Methoden ''istVerbunden'' und ''istVerbundenRekursiv'' sind im obigen Programm schon eingebaut. Der Graph, der im Hauptprogramm aufgebaut wird, ist rechts dargestellt.
-<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)]]. \\ \\
-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.)]] \\ \\
-Keines der beiden Suchverfahren ist für das allgemeine Problem der Suche in Graphen „besser“ geeignet als das andere.
-</WRAP>
-{{ :graphen:pasted:20211106-220900.png?200}}
-==== Beispiel für Tiefen- und Breitensuche ====
-Überprüft man in diesem Graphen, ob es eine Verbindung von Knoten 1 nach Knoten 5 gibt, so durchläuft die Tiefensuche ihn in der Reihenfolge 1,2,4,3 (Sackgasse), 5, die Breitensuche in der Reihenfolge 1,2,3,4,5. Dabei wurde angenommen, dass immer zuerst der Knoten mit der kleinsten Knotennummer besucht wird.
-<WRAP center round todo 60%>
-**Aufgabe (nicht leicht...):** \\ \\
-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. \\ \\
-[[.istverbundenaufgabe:loesung|Lösung]]
-</WRAP>
-===== Breitensuche =====
-Schreibe die Methode ''istVerbunden'' der Klasse Graph so um, dass sie die Strategie "Breitensuche" nutzt, um herauszufinden, ob vom Startknoten aus der Zielknoten zu erreichen ist.
-  * Du wirst eine Warteschlange brauchen, die int-Werte speichern kann. In der Programmbox unten habe ich schon eine für Dich hinterlegt.
-  * Ergänze dein Programm so, dass es ausgibt, welche Knoten es gerade untersucht und welche es in der Warteschlange ablegt. Vergleiche seine Ausgabe mit dem Graphen links!
-<HTML>
-<img src="/11/lib/exe/fetch.php?w=300&tok=be3f26&media=datenstrukturen:graphen:pasted:20211107-152623.png" style="position: absolute; left: 0px; width: 200px;">
-<div class="java-online" style="height: 70vh; width: 100%" data-java-online="{'withBottomPanel': true, 'id': 'Graph3'}">
-<script type="text/plain" title="Graph.java">
-public class Graph {
-   private int[][] adj;
-   public Graph(int anzahlKnoten) {
-      adj = new int[anzahlKnoten][anzahlKnoten];
-   }
-   public void kanteHinzufügen(int von, int nach) {
-      adj[von][nach] = 1;
-   }
-   public boolean istVerbunden(int startknoten, int zielknoten) {
-      // TODO!
-   }
-}
-</script>
-<script type="text/plain" title="Testprogramm.java">
-Graph g = new Graph(8);
-g.kanteHinzufügen(0, 1);
-g.kanteHinzufügen(1, 0);
-g.kanteHinzufügen(1, 2);
-g.kanteHinzufügen(2, 3);
-g.kanteHinzufügen(3, 4);
-g.kanteHinzufügen(2, 4);
-g.kanteHinzufügen(4, 2);
-g.kanteHinzufügen(3, 5);
-g.kanteHinzufügen(5, 2);
-g.kanteHinzufügen(5, 6);
-g.kanteHinzufügen(1, 6);
-g.kanteHinzufügen(6, 7);
-g.kanteHinzufügen(7, 0);
-println(g.istVerbunden(4, 1));
-</script>
-<script type="text/plain" title="Int-Warteschlange.java">
-class IntWert {
-   int wert;
-   IntWert nächster;
-   public IntWert(int wert, IntWert nächster) {
-      this.wert = wert;
-      this.nächster = nächster;
-   }
-}
-class IntWarteschlange {
-   IntWert erster;
-   public int erstenEntnehmen() {
-      if(erster == null) return -1;
-      IntWert w = erster;
-      erster = erster.nächster;
-      return w.wert;
-   }
-   public void hintenAnfügen(int wert) {
-      if(erster == null) {
-         erster = new IntWert(wert, null);
-      } else {
-         IntWert w = erster;
-         while(w.nächster != null) {
-            w = w.nächster;
-         }
-         w.nächster = new IntWert(wert, null);
-      }
-   }
-   public boolean istLeer() {
-      return erster == null;
-   }
-}
-</script>
-</div>
-</HTML>
-Auf der linken Seite siehst Du eine graphische Darstellung des im Hauptprogramm generierten Testgraphen. \\ \\
-[[.breitensuche:loesung:start|Lösung]]