Informatik Datenstrukturen – Graphen und Adjazenzdarstellungen
Karteikarten zum Thema „Informatik“ · 16 Karten · von atrio. Beispiele: Was ist ein Graph in der Informatik? · Worin unterscheiden sich gerichtete und ungeri…
Karten
16 KartenWas ist ein Graph in der Informatik?
Rückseite
Ein Graph besteht aus einer Menge Knoten (Vertices) und Kanten (Edges), die Paare von Knoten verbinden – gerichtet oder ungerichtet.
Worin unterscheiden sich gerichtete und ungerichtete Graphen?
Rückseite
Bei gerichteten Graphen haben Kanten eine Richtung (Bögen), bei ungerichteten Graphen verbinden Kanten Knoten symmetrisch ohne Richtung.
Wie ist eine Adjazenzmatrix definiert?
Rückseite
Eine n×n-Matrix A mit A[i][j] = 1 (oder Kantengewicht), falls Kante von Knoten i nach j existiert, sonst 0.
Wie ist eine Adjazenzliste definiert?
Rückseite
Ein Array oder Dictionary, das jedem Knoten eine Liste seiner Nachbarknoten zuordnet – nur existierende Kanten werden gespeichert.
Wie hoch ist die Speicherkomplexität einer Adjazenzmatrix?
Rückseite
Θ(|V|²) – quadratisch in der Knotenzahl, unabhängig von der tatsächlichen Kantenanzahl.
Wie hoch ist die Speicherkomplexität einer Adjazenzliste?
Rückseite
Θ(|V| + |E|) – linear in Knoten plus Kanten, speichereffizient bei dünnen Graphen.
Wann ist eine Adjazenzmatrix der Adjazenzliste vorzuziehen?
Rückseite
Bei dichten Graphen (|E| ≈ |V|²), schneller Kantenzugriff O(1) und einfache Matrixoperationen nötig sind.
Wann ist eine Adjazenzliste der Adjazenzmatrix vorzuziehen?
Rückseite
Bei dünnen Graphen (|E| ≪ |V|²), geringer Speicherbedarf und effiziente Nachbarknoten-Iteration O(Grad) erforderlich sind.
Wie findest du alle Kantennachbarn eines Knotens in der Adjazenzmatrix?
Rückseite
Gesamte Zeile des Knotens scannen – O(|V|) Zeit, da alle |V| Spalten geprüft werden müssen.
Wie findest du alle Kantennachbarn eines Knotens in der Adjazenzliste?
Rückseite
Direkter Zugriff auf die Nachbarsliste des Knotens – O(Grad(v)) Zeit, proportional zur Anzahl echter Nachbarn.
Wie funktioniert Tiefensuche (DFS) auf Graphen?
Rückseite
Rekursiv oder mit Stack: starte bei Knoten, besuche unbesuchte Nachbarn tiefgehend vor Rücksprung –マークt besuchte Knoten zur Zyklusvermeidung.
Wie funktioniert Breitensuche (BFS) auf Graphen?
Rückseite
Mit Queue: starte bei Knoten, besuche alle Nachbarn Ebene für Ebene – liefert kürzeste Pfade in ungewichteten Graphen.
Welche Voraussetzung muss für Dijkstra-Algorithmus erfüllt sein?
Rückseite
Alle Kantengewichte müssen nicht-negativ sein – negative Gewichte führen zu falschen Ergebnissen.
Wozu dient topologische Sortierung bei gerichteten Graphen?
Rückseite
Erzeugt lineare Reihenfolge der Knoten, sodass für jede Kante (u,v) Knoten u vor v erscheint – nur in DAGs möglich.
Wie erkennst du einen Zyklus in einem ungerichteten Graphen per DFS?
Rückseite
Bei DFS: wenn du einen bereits besuchten Knoten triffst, der nicht der direkte Elternknoten ist, liegt ein Zyklus vor.
Wie werden Kanten-Gewichte in Adjazenzmatrix und -liste gespeichert?
Rückseite
Matrix: Gewichte statt 1/0 in Zellen; Liste: Tupel (Nachbar, Gewicht) in Nachbarslisten – beide unterstützen gewichtete Algorithmen wie Dijkstra.