Adjazenzliste

• Alternative zur Adjazenzmatrix (weniger Platzaufwand)
• Jeder Knoten ist in einer Liste enthalten und enthält selbst eine Liste seiner Nachbarknoten

Implementierungsvarianten

Beispiel an diesem Graph:

graph LR
    0-->1 & 2;
    1-->0;
    2-->1;

Dichte Speicherung

• Durch Felder
• Heißt: Kanten die vom Knoten “Adresse” ausgehen, gehen in der Kantenliste ab Adresse “Wert” los

1. Kante

Adresse	Wert	Bedeutung
0	0	Kanten vom Knoten 0 gehen in der Kantenliste ab Adresse 0 los
1	2	Kanten vom Knoten 1 gehen in der Kantenliste ab Adresse 2 los
2	3	…

Kantenliste

Adresse	Wert	Bedeutung
0	1	Beginn der Kanten von Knoten 0: Nach 1
1	2	Nach 2
2	0	Beginn der Kanten von Knoten 1: Nach 0
3	1	Beginn der Kanten von Knoten 2: Nach 1

• Dicht gespeichert
• Aber: Umorganisationsaufwand der Felder bei hoher Dynamik sehr hoch

Gestreute Speicherung

• Mit Zeigern
• Eine linear verkettete Liste aus allen Kanten die existieren
• An jeder Kante hängt nochmals eine linear verkettete Liste mit Knoten die die Kante zu anderen hat

0 > 1 > 2
v
1 > 0
v
2 > 1

Hybride Speicherung

• Die Knoten werden als Feld angelegt
• Die Werte in den Feldern verweisen auf den Kopf einer linear verketteten Liste

Adresse	Wert
0	> 1 > 2
1	> 0
2	> 1

Implementierung:

class edge {
	int dst;        // Nummer des Endknotens der Kante
	edge *next;     // Zeiger auf nächsten Endknoten
	...
}
 
edge *adj_list[no_nodes];  // Je Knoten: Liste für die Kanten

• Platz:
• Zeit Kantenzugriff: