Graph Allgemein
Dieser Begriff bezeichnet die Punkte eines Graphen, zwischen denen Verbindungen bestehen können.
Was sind Knoten?
Diese Datenstruktur wird verwendet, um Knoten während der Breitensuche in der richtigen Reihenfolge abzuarbeiten.
Was ist eine Warteschlange / Queue?
Der Dijkstra-Algorithmus berechnet dies in einem gewichteten Graphen.
Was ist der kürzeste Weg?
In Java werden Sammlungen von gleichartigen Werten in dieser Struktur gespeichert.
Was ist ein Array / Feld?
Wenn alle Kanten in beide Richtungen gelten, spricht man von dieser Art von Graph.
Was ist ein ungerichteter Graph?
Der erste Schritt der BFS ist, den Startknoten ____.
Was ist „auf besucht setzen und in die Queue einfügen“?
In der Initialisierung (Programmstart werden alle Distanzen zu den Knoten zunächst auf 9999 (oder noch höhere Werte) gesetzt. Was bedeutet dieser Wert?
Was ist „unendlich“ / „nicht erreichbar“?
Diese Schleife eignet sich, wenn man vorher weiß, wie oft man wiederholen will.
Was ist die for-Schleife?
Eine Adjazenzmatrix mit Einträgen größer 1, die nicht symmetrisch ist, beschreibt einen solchen Graphen.
Was ist ein gewichteter, gerichteter Graph?
Dieser Befehl entfernt das erste Element aus der Warteschlange und liefert es zurück.
Was ist queue.poll()?
Das Array prev (für previous) speichert diese Information über jeden Knoten.
Was ist "den Vorgängerknoten"?
Eine zweidimensionale Matrix wird in Java als ____ deklariert.
Was ist int[][] matrix?
In einem zusammenhängenden ungerichteten Graphen gilt: Zwischen jedem Paar von Knoten existiert ____.
Was ist ein Pfad?
Die Bedingung if (adj[current][i] == 1 && !visited[i])? prüft _____
Existiert eine Verbindung von current zum Knoten i, wobei i noch nicht besucht wurde?
Per Schleife wird in Dijkstra für jeden Knoten nach folgendem anderen Knoten gesucht _______
Was ist der noch unbesuchte Knoten mit der kleinsten bekannten Distanz?
Diese Anweisung prüft eine Bedingung und führt nur dann Code aus, wenn sie wahr ist.
Was ist eine if-Bedingung?
Wenn ein Pfad wieder zum Startknoten zurückführt, ohne Kanten zu wiederholen, enthält der Graph ____.
Was ist ein Zyklus?
Die BFS durchsucht einen Graphen in dieser Reihenfolge.
Was ist Ebene für Ebene / Level-Order / „von innen nach außen“
Dijkstra funktioniert nicht bei dieser Art von Kantengewichten, weil er falsche Ergebnisse liefern kann.
Was sind negative Gewichte?
In der Objektorientierung beschreibt dieses Schlüsselwort die Beziehung zwischen einer Ober- und Unterklasse.
Was ist extends / Vererbung?