Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- graphen:start [2023/10/12 10:12] – [Warteschlange (Queue)] 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%>
-{{ :graphen:20211107-152623.png?200|}}
-Den im Testprogramm unten generierten Graphen siehst Du in graphischer Darstellung im Bild rechts.
-</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 vonIndex, int nachIndex) {
-      adj[vonIndex][nachIndex] = 1;
-   }
-   public boolean istDirektVerbunden(int vonIndex, int nachIndex) {
-      return adj[vonIndex][nachIndex] > 0;
-   }
-}
-</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.istDirektVerbunden(4, 1));
-println(g.istDirektVerbunden(2, 4));
-</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 (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 [[.tiefensuche:start|hier eine Einführung zum Selbststudium]]. Falls Sie Fragen dazu haben, stehe ich gerne zur Verfügung!
-</WRAP>
-===== Warteschlange (Queue) =====
-<WRAP center round info 60%>
-Für die Breitensuche brauchen wir eine neue Datenstruktur, die **Warteschlange** (engl.: Queue).
-{{ :graphen:pasted:20231012-120214.png?400 }}
-In einer Warteschlange können beliebig viele Elemente nacheinander abgelegt werden. Sie besitzt eine Methode ''addLast'' um Elemente am hinteren Ende der Warteschlange anzufügen und eine Methode ''removeFirst'' um Elemente am vorderen Ende zu entnehmen. \\ \\
-In der Programmiersprache Java gibt es mehrere Klassen, die die Aufgaben einer Warteschlange erfüllen können, daher sind die Methoden der Warteschlange im Interface ''Queue'' definiert, das von mehreren Klassen implementiert wird, insbesondere von der Klasse ''LinkedList<T>'', die wir im Folgenden verwenden. Dabei ist ''T'' die Klasse der Objekte, die in der ''LinkedList'' gespeichert werden können. Wollen wir beispielsweise Zeichenketten in der ''LinkedList'' speichern, so gehen wir folgendermaßen vor:
-{{ :graphen:pasted:20231012-121243.png?500 }}
-</WRAP>