Lesson_3 Graph Algorithms Flashcards
Was ist ein Graph?
Ein Graph besteht aus einer Menge von Knoten (Vertices) und einer Menge von Kanten (Edges), die Paare von Knoten verbinden.
Was ist der Unterschied zwischen gerichteten und ungerichteten Graphen?
In gerichteten Graphen haben die Kanten eine Richtung, in der sie verlaufen. In ungerichteten Graphen gibt es keine Richtung, die Kanten** verbinden Knoten in beide Richtungen**.
Was ist der Unterschied zwischen einer Adjazenzmatrix und einer Adjazenzliste?
Eine Adjazenzmatrix ist eine quadratische Matrix, die die Verbindungen zwischen Knoten darstellt, während eine Adjazenzliste für jeden Knoten die Nachbarknoten in einer Liste speichert.
Wie funktioniert der Dijkstra-Algorithmus?
Der Dijkstra-Algorithmus berechnet die kürzesten Wegevon einem Startknoten zu allen anderen Knoten in einem Graphen mit nicht-negativen Gewichten.
Was ist die Breitensuche (BFS)?
Die Breitensuche ist eine Traversierungstechnik, die einen Graphen Schicht für Schicht durchläuft, indem sie alle Knoten einer Ebene besucht, bevor sie zu tiefer liegenden Ebenen übergeht.
Was ist die Tiefensuche (DFS)?
Die Tiefensuche ist eine Traversierungsmethode, die von einem Startknoten ausgehend so tief wie möglich in den Graphen vordringt, bevor sie zurückkehrt und unbesuchte Knoten besucht.
Was ist ein Minimaler Spannbaum (MST)?
Ein Minimaler Spannbaum ist ein Teilgraph, der alle Knoten eines Graphen verbindet und die Summe der Kantengewichte minimiert.
Wie funktioniert der Kruskal-Algorithmus?
Der Kruskal-Algorithmus ist ein Greedy-Algorithmus zur Berechnung des minimalen Spannbaums, der die Kanten in aufsteigender Reihenfolge ihres Gewichts auswählt und nur solche Kanten hinzufügt, die keinen Zyklus bilden.
Wie funktioniert der Prim-Algorithmus?
Der Prim-Algorithmus ist ein Greedy-Algorithmus, der einen minimalen Spannbaum bildet, indem er von einem Startknoten ausgehend iterativ die Kante mit dem kleinsten Gewicht wählt, die einen unbesuchten Knoten verbindet.
Wie funktioniert der Floyd-Warshall Algorithmus?
Der Floyd-Warshall Algorithmus ist ein dynamischer Programmieralgorithmus zur Berechnung der kürzesten Wege zwischen allen Knotenpaaren eines Graphen.
Was ist der Bellman-Ford Algorithmus?
Der Bellman-Ford Algorithmus berechnet die kürzesten Wege von einem Startknoten zu allen anderen Knoten, funktioniert auch bei negativen Kantengewichten und erkennt Zyklen mit negativen Gewichtssummen.
Wie funktioniert der Dijkstra-Algorithmus?
Der Dijkstra-Algorithmus findet den kürzesten Weg von einem Startknoten zu allen anderen Knoten in einem gewichteten Graphen. Er beginnt beim Startknoten und markiert alle Knoten mit einer vorläufigen Distanz, die zu Beginn unendlich ist, außer für den Startknoten, der eine Distanz von 0 hat. Dann wählt er den Knoten mit der kleinsten vorläufigen Distanz aus, aktualisiert die Distanzen zu den Nachbarknoten und wiederholt den Vorgang, bis alle Knoten endgültige Distanzen erhalten haben oder das Ziel erreicht ist. Dabei werden immer die kürzesten bekannten Wege bevorzugt.
Was ist der Hauptunterschied zwischen dem Dijkstra-Algorithmus und dem Minimalen Spannbaum (MST)?
Der Hauptunterschied liegt im Ziel der Algorithmen: Der Dijkstra-Algorithmus berechnet den kürzesten Weg von einem Startknoten zu allen anderen Knoten in einem gewichteten Graphen, während der Minimale Spannbaum (MST) alle Knoten des Graphen so verbindet, dass die Gesamtsumme der Kantengewichte minimal ist. Dijkstra konzentriert sich auf kürzeste Pfade, während der MST die kosteneffizienteste Verbindung aller Knoten ohne Zyklen sucht.
Was ist der PageRank-Algorithmus und wie funktioniert er?
Der PageRank-Algorithmus wurde von den Google-Gründern entwickelt, um die Relevanz von Webseiten in einem Netzwerk zu bewerten. Er basiert auf der Idee, dass eine Webseite umso wichtiger ist, je mehr andere relevante Seiten auf sie verlinken. Der Algorithmus verteilt einen Wert (den “PageRank”) auf alle Webseiten und berechnet diesen iterativ, indem er die Anzahl und Qualität der eingehenden Links berücksichtigt. Ein Link von einer hoch bewerteten Seite hat mehr Einfluss als ein Link von einer weniger wichtigen Seite. PageRank kann so verwendet werden, um Suchergebnisse nach Relevanz zu sortieren.
