Graphen 13

Question 1

Erläutern Sie die Definition von ungerichteten und gerichteten Graphen

Answer 1

Gerichtete Graphen haben Kanten mit einer Richtung während ungerichtete Graphen Kanten ohne eine bestimmte Richtung haben

Question 2

Erläutern Sie Definition von Vorgänger und Nachfolger in einem gerichteten Graphen

Answer 2

Nachfolger eines Knotens sind Knoten, die über eine ausgehende Kante erreicht werden
Vorgänger eines Knotens sind knoten die Quelle einer eingehenden Kante sind

Question 3

Erläutern Sie den Eingangs und Ausgangsgrad in einem gerichteten Graphen

Answer 3

Ausgangsgrad ist die Anzahl der ausgehenden Kanten. Eingangsgrad ist die Anzahl der eingehenden Kanten

Question 4

Erklären und Implementieren Sie einen Graphen mit einer Adjazenzmatrix

Answer 4

Verbindung zwischen den Knoten eines Graphen mithilfe einer zweidimensionalen Matrix

Question 5

Erklären und Implementieren Sie einen Graphen mit Adjazenlisten

Answer 5

Verbindungen zwischen den Knoten eines Graphen wird durch Liste von Adjazenzlisten dargestellt

Question 6

Erklären und wenden Sie die unterschiedlichen Fehlerbehandlungsmethoden an

Answer 6

Globale Variable, Spezieller Rückgabewert, Exception

Question 7

Erklären und Implementieren Sie die Breitensuche

Answer 7

Alle Knoten werden schichtweise durchlaufen, erst startknoten dann jeweils die nachbarknoten usw

Question 8

Erklären und Implementieren Sie die Tiefensuche

Answer 8

Geht einen Pfad so tief wie möglich entlang

Question 9

Erklären und Implementieren Sie die Berechnung der kürzesten Wege

Answer 9

Dijkstra Algorithmus: Schichtweise, jedoch ist die Länge des Pfades relevant
Bellman Ford Algorithmus: Distanzen werden Iterativ aktualisiert