Graphen Flashcards
Wann ist eine Eulertour in einem Graphen möglich?
Wenn maximal zwei Knoten eines Graphen einen ungeraden Grad haben.
Was sind Vor- und Nachteile einer Graphenmodellierung mit Adjazenzlisten?
+ Sie belegen nur soviel Speicherplatz wie nötig
- Beim Suchen muss man ggf. erst eine lange Kartenliste durchlaufen
+ Der Graph kann dynamisch ergänzt werden
Was sind Vor- und Nachteile einer Graphenmodellierung mit Adjazenzmatrizen?
+ Es lässt sich schnell prüfen, ob eine Kante vorhanden ist
- Sie benötigen immer gleich viel und vergleichsweise viel Speicherplatz
- Der Graph kann nicht dynamisch erweitert werden
Wann bietet sich eine Adjazenzliste an?
Bei dünnen Graphen mit wenigen Kanten
Wann bietet sich eine Adjazenzmatrix an?
Bei dichten Graphen mit vielen Kanten
Wie läuft die Tiefensuche in einem Graphen ab?
- werden alle Markierungen aufgehoben, als
- wird der besuchte Knoten markiert und als
- wird der ganze Vorgang mit allen Nachbarknoten wiederholt, falls diese nicht markiert sind
Wie läuft die Breitensuche in einem Graphen ab?
- werden alle Markierungen aufgehoben, als
- wird der besuchte Knoten markiert, als
- wird der besuchte Knoten in eine Liste s eingefügt, als
- wird solange s nicht leer ist der vorderste Knoten aus s genommen und dessen, falls sie noch nicht markiert sind, Nachbarknoten markiert und an s angehangen
Wann lohnt sich eine Tiefensuche in einem Graphen?
Wenn der zu findende Knoten weit von dem Startknoten entfernt zu erwarten ist.
Wann lohnt sich eine Breitensuche in einem Graphen?
Wenn der zu findende Knoten nah an dem Startknoten zu erwarten ist.
Wie läuft die Suche nach einem Weg von einem zu einem anderen Knoten ab, mithilfe der Tiefensuche und des Backtrackings ab?
private boolean sucheWeg(Vertex start, Vertex ziel, List pWeg)
{
//Vertices überschreiben, Startknoten der Wegliste hinzufügen und markieren, Wegliste Access geben
Vertex s = g.getVertex(start.getID());
Vertex z = g.getVertex(ziel.getID());
pWeg.append(s);
s.setMark(true);
pWeg.toFirst();
//Überprüfen, ob der Zielknoten schon gefunden wurde
if(!s.getID().equals(z.getID())){
//Falls nicht: Nachbarn des Startknoten in eine Nachabrliste packen und dieser Access geben List n = g.getNeighbours(s); n.toFirst();
//Jeden Nachbarn aus der Liste abklappern und ab dort mit der Methode weitersuchen, falls derjenige nicht markiert ist
while(n.hasAccess()){
if(!n.getContent().isMarked()){
return sucheWeg(n.getContent(), z, pWeg);
}
n.next();
}
//Backtracke, nachdem alle Nachabarn durchsucht wurden
pWeg.toLast();
pWeg.remove();
return false;
}
//Füge den Weg der globalen Wegliste hinzu und breche den Vorgang this.weg.concat(pWeg); return true; }
Was ist die Grundidee vom Dijkstra-Algorithmus?
Man verfolgt immer den kürzesten Weg zum nächsten Knotenpunkt und geht dann von dort aus weiter.
Wie läuft der Dijkstra-Algorithmus ab?
- werden alle Knoten in eine Liste eingefügt, als
- wird allen Knoten, außer dem Startknoten, der Wert unendlich zugewiesen, als
- erhält der Startknoten den Wert 0, als
- wird der Knoten K mit der geringsten Entfernung vom Startknoten aus der Liste entfernt, als
- werden die Nachbarknoten betrachtet und dessen Entfernungen zu der von dem derzeit besuchten Knoten K Entfernung zum Startpunkt addiert. Falls diese Summe kleiner als die bisherige Entfernung ist, wird diese als neue Entfernung dessen Nachbarknoten gesetzt und als
- wird das ganze bei Schritt 4 wiederholt, bis der Zielknoten entfernt werden soll
Was ist ein gerichteter Graph?
Die Richtung der Kanten ist vorgegeben.
Wenn man in beide Richtungen gehen möchte, sind zwei Kanten nötig.
Was ist ein ungerrichteter Graph
Die Richtung der Kanten ist nicht vorgegeben, man kann also auf eine Kante in beide Richtungen gehen. Den einzelnen Kanten werden Gewichte zugeschrieben.
Wann ist ein ungerichteter Graph zusammenhängend?
Wenn jeder Knoten erreichbar ist, sonst gibt es einzelne Knotengruppen
