Darstellung von Graphen

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Die Darstellung ist kein Implementierungsdetail

Ein Graph ist ein abstraktes Objekt: eine Menge von Knoten und Kanten, mehr nicht. Ein Computer kann kein abstraktes Objekt speichern. Er speichert Bytes, und die Wahl, welche Bytes es sind, entscheidet, noch bevor Sie eine einzige Zeile Algorithmus schreiben, wozu Ihr Programm fähig ist.

Diese Behauptung ist leicht aufgestellt und leicht unterschätzt, hier also ihre schärfste Fassung. Die Breitensuche läuft auf einer Adjazenzliste in O(n + m) Zeit und auf einer Adjazenzmatrix in O(n2) Zeit. Derselbe Algorithmus, derselbe Graph, dieselbe Ausgabe. Nur die Speicherung unterscheidet sich. Bei einem Graphen mit einer Million Knoten und fünfzig Millionen Kanten ist das der Unterschied zwischen etwa 51 Millionen Operationen und etwa einer Billion: ein Faktor von rund 19,600. Kein noch so gutes Tuning konstanter Faktoren holt das wieder herein. Die Darstellung war die ganze Zeit über die asymptotische Komplexität des Algorithmus.

Der Grund ist offensichtlich, sobald man ihn sieht. Beide Varianten von BFS tun an jedem Knoten dasselbe: Sie zählen seine Nachbarn auf. Eine Adjazenzliste beantwortet „Wer sind die Nachbarn von v?“ in einer Zeit, die proportional zu ihrer Anzahl ist. Eine Adjazenzmatrix beantwortet sie, indem sie eine ganze Zeile der Länge ndurchsucht, die größtenteils aus Nullen besteht. Über alle Knoten summiert kostet die Liste 2m und die Matrix n2. Genau diese Beobachtung war die Grundlage, auf der Hopcroft und Tarjan Anfang der 1970er-Jahre ihre linearzeitigen Graphenalgorithmen aufbauten, und deshalb wurde die Adjazenzliste seither in jeder Algorithmenvorlesung zum Standard.

Doch die Adjazenzliste ist nicht immer die Antwort, und sie als automatischen Standard zu behandeln, ist ein eigener Fehler. Fragen Sie, ob zwei gegebene Knoten benachbart sind, und die Matrix antwortet mit einem einzigen Speicherzugriff, während die Liste eine Nachbarfolge durchsucht. Multiplizieren Sie den Graphen mit sich selbst, und die Matrix liefert Ihnen die Anzahl der Kantenfolgen gratis. Speichern Sie einen wirklich dichten Graphen, und die Matrix braucht weniger Speicher, nicht mehr. Rechnen Sie auf einer GPU, und keine der beiden Strukturen ist das, was Sie wollen.

Die ehrliche Formulierung lautet also nicht „welche Darstellung ist die beste“, sondern welche Frage werden Sie am häufigsten stellen, und wie groß ist der Graph. Dieser Artikel arbeitet die sieben Darstellungen durch, die in der Praxis zählen, leitet die Kosten jeder Operation auf jeder her und endet mit einem Entscheidungsverfahren. Jede Zahl über den Beispielgraphen unten wurde per Skript berechnet statt behauptet, und die Rechnung ist wiedergegeben, damit Sie sie nachprüfen können.

2. Das durchgehende Beispiel

Ein kleiner gewichteter Graph trägt den ganzen Artikel. Er ist bewusst klein genug, um ihn in jeder Darstellung vollständig auszuschreiben, und bewusst unregelmäßig genug, damit die Darstellungen wirklich verschieden aussehen.

V = {0, 1, 2, 3, 4, 5}

E = { {0,1}:4   {0,2}:3   {1,2}:2   {1,3}:5   {2,4}:7   {3,4}:1   {3,5}:6 }

n = 6      m = 7      Gradsumme = 14 = 2m
Grade      0:2   1:3   2:3   3:3   4:2   5:1

Zwei Tatsachen darüber werden immer wieder auftauchen. Seine Nachbarmengen, in sortierter Reihenfolge geschrieben, sind

0 → 1, 2
1 → 0, 2, 3
2 → 0, 1, 4
3 → 1, 4, 5
4 → 2, 3
5 → 3

und seine Dichte beträgt 7 / 15 = 46.7%, denn ein einfacher Graph mit 6 Knoten lässt höchstens C(6,2) = 15 Kanten zu. Das ist für reale Verhältnisse sehr dicht, was eine nützliche Korrektur ist: Spielzeuggraphen in Lehrbüchern sind fast immer dicht, und die Intuitionen über Darstellungen, die sie vermitteln, sind für Produktionsdaten fast immer falsch. Wir korrigieren das in Abschnitt 6.

3. Die Kantenliste

Die einfachste Darstellung besteht darin, die Kanten aufzuschreiben und aufzuhören.

edges = [ (0,1,4), (0,2,3), (1,2,2), (1,3,5), (2,4,7), (3,4,1), (3,5,6) ]

Ein Array aus m Tripeln. Der Speicherbedarf ist Θ(n + m) , wenn Sie zusätzlich eine Knotenanzahl führen, und Θ(m) , wenn die Knotenmenge implizit in den Kanten steckt. Nichts wird vorberechnet, nichts wird indiziert.

Die Folge ist, dass fast jede Abfrage ein vollständiger Durchlauf ist. „Sind 1 und 4 benachbart?“ erfordert, alle sieben Kanten durchzugehen. „Was sind die Nachbarn von 3?“ erfordert, alle sieben Kanten durchzugehen. Beides ist O(m), was katastrophal ist, wenn Sie es in einer Schleife über die Knoten tun, denn daraus wird O(nm).

Und dennoch ist die Kantenliste keine naive Wahl, denn drei wichtige Situationen wollen genau diese Form:

• Algorithmen, die über Kanten statt über Knoten iterieren. Der Kruskal-Algorithmus sortiert alle Kanten nach Gewicht und betrachtet sie der Reihe nach; er fragt nie nach einer Nachbarliste. Bellman-Ford relaxiert jede Kante n - 1 Mal; wieder reine Kanteniteration. Für diese ist die Kantenliste nicht bloß ausreichend, sondern optimal, denn jede andere Darstellung müsste erst wieder in Kantenreihenfolge ausgebreitet werden.
• Austausch und Speicherung. Jedes Graphdateiformat auf der Festplatte ist eine Kantenliste, denn sie ist die einzige Darstellung, die reihenfolgeunabhängig, nur anhängend und trivial zu parsen ist. Wenn Sie einen Datensatz von SNAP oder aus den DIMACS-Sammlungen herunterladen, bekommen Sie eine Kantenliste, und Ihr erster Schritt ist, sie umzuwandeln.
• Streaming. Wenn der Graph überhaupt nicht in den Speicher passt, ist eine Kantenliste das, was ankommt, eine Kante nach der anderen, und das Semi-Streaming-Berechnungsmodell beruht auf der Annahme, dass Sie nur das bekommen.

Die praktische Regel lautet: Eine Kantenliste ist ein Transportformat und ein Iterationsformat , kein Abfrageformat. Reale Systeme lesen eine Kantenliste und bauen sofort etwas Indiziertes daraus. Diese Umwandlung ist das Thema von Abschnitt 7, und sie ist billiger, als man denkt: Ein Counting Sort über die Knotenkennungen erledigt sie in O(n + m).

4. Die Adjazenzmatrix

Nummerieren Sie die Knoten von 0 bis n - 1 und bauen Sie die n × n Matrix A , in der A[u][v] = 1 gilt, wenn {u, v} eine Kante ist, und 0 andernfalls. Für das durchgehende Beispiel:

      0  1  2  3  4  5        Zeilensumme
  0 [ 0  1  1  0  0  0 ]         2
  1 [ 1  0  1  1  0  0 ]         3
  2 [ 1  1  0  0  1  0 ]         3
  3 [ 0  1  0  0  1  1 ]         3
  4 [ 0  0  1  1  0  0 ]         2
  5 [ 0  0  0  1  0  0 ]         1

36 Zellen, 14 davon von null verschieden

Drei strukturelle Eigenschaften ergeben sich unmittelbar, und jede davon ist beim Debuggen eine brauchbare Prüfung.

• Die Matrix eines ungerichteten Graphen ist symmetrisch. A[u][v] = A[v][u] gilt immer, also ist die Hälfte des Speichers redundant. Gerichtete Graphen geben diese Symmetrie auf, und genau das macht die Richtung in der Algebra sichtbar.
• Die Zeilensummen sind die Grade: 2, 3, 3, 3, 2, 1, passend zur Liste in Abschnitt 2. Die Gesamtzahl der Einsen beträgt 2m = 14, da jede Kante zwei Zellen beisteuert.
• Die Diagonale ist null bei einem einfachen Graphen, denn ein von null verschiedener Diagonaleintrag ist eine Schleife.

Was Sie gewinnen, ist Adjazenz in konstanter Zeit. Die Frage, ob 1 und 4 benachbart sind, ist ein einziger Array-Zugriff, A[1][4], unabhängig vom Grad. Keine andere Darstellung in diesem Artikel schafft das ohne Hashing. Was Sie bezahlen, ist Θ(n2) Speicher, unabhängig davon, wie viele Kanten existieren, und Θ(n) Zeit, um die Nachbarn eines Knotens aufzuzählen, unabhängig davon, wie wenige es sind.

Diese letzten Kosten sind die, die wehtun. Knoten 5 hat einen einzigen Nachbarn, doch Zeile 5 zu lesen, um das herauszufinden, berührt sechs Zellen. Skalieren Sie das auf eine Million Knoten, und die Nachbarn eines Knotens vom Grad eins zu finden, berührt eine Million Zellen. Das O(n2) bei der Matrix-BFS ist genau dieser Effekt, aufsummiert.

Die Verfeinerung durch Bitpacking. Ist der Graph ungewichtet, braucht jede Zelle ein Bit, nicht ein Byte und schon gar keine 32-Bit-Ganzzahl. Zeilen in Maschinenwörter zu packen, senkt den Speicherbedarf gegenüber einer Byte-Matrix um den Faktor 8 und gegenüber einer Int-Matrix um 32, und es bewirkt etwas Interessanteres: Sie können damit 64 Nachbarn pro Instruktion verarbeiten. Das Schneiden zweier Nachbarschaften, die innerste Schleife beim Zählen von Dreiecken und bei vielen Clique-Algorithmen, wird zu einem wortweisen AND über n/64 Wörter statt zu einer Schleife über n Einträge. Wir kommen in Abschnitt 11darauf zurück, denn das ist der Hauptgrund, warum dichte Darstellungen überleben.

5. Die Adjazenzliste

Speichern Sie für jeden Knoten eine Folge seiner Nachbarn.

adj[0] = [ (1,4), (2,3) ]
adj[1] = [ (0,4), (2,2), (3,5) ]
adj[2] = [ (0,3), (1,2), (4,7) ]
adj[3] = [ (1,5), (4,1), (5,6) ]
adj[4] = [ (2,7), (3,1) ]
adj[5] = [ (3,6) ]

Der Speicherbedarf ist Θ(n + m): ein Platz pro Knoten plus 2m = 14 Nachbareinträge bei einem ungerichteten Graphen oder m bei einem gerichteten. Die Nachbarn von v aufzuzählen kostet Θ(deg(v)), was optimal ist, denn man kann k Dinge nicht in weniger als k Zeit auflisten.

Das ist die Darstellung, die linearzeitige Graphenalgorithmen möglich macht, und ihre Durchsetzung hat eine genaue Geschichte. Tarjans Arbeit zur Tiefensuche von 1972 und die begleitenden Algorithmen von Hopcroft und Tarjan aus dem Jahr 1973 sagen ausdrücklich, dass die O(n + m) Schranken von der Speicherung als Adjazenzliste abhängen; dieselben Verfahren auf einer Matrix sind O(n2). Das Lehrbuch von Aho, Hopcroft und Ullman aus dem Jahr 1974 machte die Liste dann zur Standarddarstellung, und seither ist sie in Traversierungs -Code der Standard.

Der Preis ist, dass der Adjazenztest nicht mehr konstant ist. Um „sind 1 und 4 benachbart?“ zu beantworten, durchsuchen Sie adj[1], drei Einträge, und finden nichts. Allgemein ist das O(deg(u))oder O(min(deg(u), deg(v))) , wenn Sie sorgfältig genug sind, die kürzere Liste zu durchsuchen. In einem Graphen mit wenigen Knoten sehr hohen Grades, und genau so sieht jeder soziale Graph und jeder Webgraph aus, kann dieses Minimum immer noch bei Millionen liegen.

Die Frage der Nachbarreihenfolge. Nichts in der Definition sagt, dass die Nachbarfolgen sortiert sein müssen, und der meiste Code belässt sie in Einfügereihenfolge. Sie zu sortieren kostet einmalig O(m log m) und bringt zwei Dinge: binär durchsuchbare Adjazenz in O(log deg(u))und Schnittbildung von Nachbarschaften in linearer Zeit per Merge, worauf schnelle Implementierungen zum Zählen von Dreiecken beruhen. Wenn Sie Nachbarschaften überhaupt schneiden, sortieren Sie.

Die Implementierungsfalle. Das Lehrbuchbild einer Adjazenzliste ist ein Array verketteter Listen, und das Lehrbuchbild ist auf moderner Hardware ein schlechter Rat. Eine verkettete Liste dereferenziert pro Nachbar einen Zeiger, und jede Dereferenzierung ist ein potenzieller Cache-Miss in der Größenordnung von hundert Takten. Ein vector<vector<int>> ist besser, da die Nachbarn jedes Knotens zusammenhängend liegen, doch es verstreut immer noch n getrennt allozierte Blöcke über den Heap und zahlt pro Knoten einen Allokations-Header. Die Lösung steht in Abschnitt 7.

Varianten auf Hash-Basis. Ersetzt man jede Nachbarfolge durch ein Hash-Set, erhält man erwartete O(1) beim Adjazenztest und behält Θ(n + m) Speicher, was nach dem Besten aus beiden Welten aussieht. In der Praxis ist die Konstante unfreundlich: Ein Hash-Set kostet ein Mehrfaches des Speichers eines gepackten Integer-Arrays, zerstört die Lokalität beim Iterieren und macht den Nachbardurchlauf, also genau die Operation, die Sie am häufigsten ausführen, spürbar langsamer. Verwenden Sie es, wenn Adjazenzabfragen die Traversierung wirklich dominieren, und messen Sie, statt zu vermuten.

6. Was „dünn besetzt“ wirklich bedeutet

Alles bisher hängt an einem Wort. Ein Graph ist dünn besetzt , wenn m nahe bei n liegt, und dicht , wenn m nahe bei n2liegt, und die praktische Trennlinie ist die Dichte

Dichte = m / C(n,2) = 2m / (n(n-1))

also der Anteil der möglichen Kanten, die tatsächlich existieren. Das durchgehende Beispiel liegt bei 7/15 = 46,7 %, was enorm dicht ist. Reale Graphen sind nicht so. Ein soziales Netzwerk mit einer Million Nutzern und fünfzig Millionen Freundschaften, im Schnitt 100 Freunde pro Person, hat die Dichte 1.0 × 10-4: ein Hundertstel eines Prozents. Straßennetze sind noch extremer, mit einem Durchschnittsgrad unter 3, weil Kreuzungen nur begrenzt viele Straßen haben. Der Webgraph, Zitationsgraphen, Protein-Interaktionsnetzwerke und Abhängigkeitsgraphen liegen alle im selben Bereich.

Hier ist, was das kostet, berechnet für genau diesen Graphen mit einer Million Knoten:

Die Matrix ist rund 300-mal größer als die dünn besetzten Strukturen, selbst wenn sie auf einzelne Bits heruntergepackt ist, und sie passt in den Speicher keiner gewöhnlichen Maschine. Das ist keine Randpräferenz. Es ist der Unterschied zwischen einem Programm, das läuft, und einem, das nicht starten kann.

Die Schwelle lohnt es, genau zu kennen. Eine bitgepackte Matrix kostet n2/8 Bytes; eine dünn besetzte Struktur, die pro gerichtetem Bogen ein 4-Byte-Ziel speichert, kostet etwa 8m Bytes. Die Matrix gewinnt, wenn n2/8 < 8mgilt, also wenn m > n2/64, was einer Dichte von ungefähr 3,1 %entspricht. Darüber verwenden Sie eine Matrix, darunter nicht. Fast jeder Graph, dem Sie außerhalb kleiner kombinatorischer Suchprobleme begegnen, liegt drei Größenordnungen darunter.

Der vollständige Vergleich Operation für Operation, wobei d für den Grad des beteiligten Knotens steht:

Die Tabelle in im Wesentlichen dieser Form ist die Standarddarstellung, sie geht auf Aho, Hopcroft und Ullman zurück und ist im Graphenkapitel von Cormen, Leiserson, Rivest und Stein wiedergegeben. Lesen Sie sie als Aussage darüber, welche Frage Sie stellen, nicht darüber, welche Zeile die beste ist. Die einzige Zelle, in der die Matrix einzigartig stark ist, ist der Adjazenztest, und die einzigen Zellen, in denen die Kantenliste stark ist, sind die Iteration über ganze Kanten und das Anhängen. Alles andere gehört den dünn besetzten indizierten Strukturen.

7. Compressed Sparse Row

Die Darstellung, die produktiver Graphencode tatsächlich verwendet, ist nicht die Adjazenzliste als Array von Vektoren. Es ist Compressed Sparse Row, unverändert aus der Linearen Algebra dünn besetzter Matrizen übernommen, wo sie seit Gustavsons Arbeiten in den frühen 1970er-Jahren Standard ist und bei Duff, Erisman und Reid als das kanonische Speicherschema für dünn besetzte Matrizen dokumentiert ist. In der Graphenwelt nennt man sie manchmal die Forward-Star -Darstellung oder schlicht eine flachgeklopfte Adjazenzliste.

Die Idee besteht darin, alle Nachbarfolgen zu einem einzigen Array zu verketten und in einem zweiten Array festzuhalten, wo der Abschnitt jedes Knotens beginnt.

offsets = [ 0, 2, 5, 8, 11, 13, 14 ]                       Länge n + 1 = 7
targets = [ 1, 2, 0, 2, 3, 0, 1, 4, 1, 4, 5, 2, 3, 3 ]     Länge 2m  = 14
weights = [ 4, 3, 4, 2, 5, 3, 2, 7, 5, 1, 6, 7, 1, 6 ]     Länge 2m  = 14

Die Nachbarn von Knoten v sind targets[offsets[v] .. offsets[v+1] - 1]. Für Knoten 2 sind das die Positionen 5 bis 7, was die Nachbarn [0, 1, 4] mit den Gewichten [3, 2, 7]ergibt, und das entspricht genau adj[2] . Der Grad ergibt sich nebenbei als offsets[v+1] - offsets[v]und liefert 2, 3, 3, 3, 2, 1 zurück, ohne das Zielarray überhaupt anzufassen.

Asymptotisch ist das mit einer Adjazenzliste identisch. In der Praxis ist es deutlich schneller, aus vier Gründen, die nichts mit Big-O zu tun haben:

• Lokalität. Die Nachbarn eines Knotens belegen aufeinanderfolgende Bytes, das Durchlaufen strömt also durch Cache-Zeilen, statt Zeigern nachzujagen. Der Hardware-Prefetcher erkennt das Zugriffsmuster und bleibt ihm voraus.
• Keine Allokation pro Knoten. Zwei Allokationen ersetzen n + 1 davon. Im Beispiel mit einer Million Knoten entfallen damit rund 38 MiB an Headern und, wichtiger noch, eine Million Gelegenheiten dafür, dass die Nachbarblöcke verstreut liegen.
• Trivial serialisierbar. Die gesamte Struktur besteht aus zwei Integer-Arrays, sie lässt sich also von der Festplatte per Memory Mapping einbinden, über ein Netzwerk senden oder ohne Zeigerkorrekturen an eine GPU übergeben.
• Indexkompression. Da targets Knotenkennungen enthält, braucht ein Graph mit weniger als 2³² Knoten nur 4 Bytes pro Eintrag, und einer mit weniger als 2¹⁶ nur 2. Das Offset-Array braucht allerdings 64-Bit-Einträge, sobald 2m den Wert 2³¹überschreitet, was bei Milliarden von Kanten ein realer und häufig gemachter Fehler ist.

CSR aus einer Kantenliste zu bauen, kostet O(n + m) und erfordert kein Sortieren. Zählen Sie in einem Durchlauf den Grad jedes Knotens, bilden Sie die Präfixsumme der Zähler in offsets, und platzieren Sie dann in einem zweiten Durchlauf jede Kante mit einem laufenden Cursor pro Knoten an ihrem Platz. Das ist ein Counting Sort nach dem Quellknoten, und es ist der übliche Einleseweg in jeder ernsthaften Graphenbibliothek.

Der Preis ist Starrheit. Eine einzige Kante einzufügen, verschiebt jeden nachfolgenden Eintrag in targets, die Struktur ist also faktisch unveränderlich: Sie bauen sie in Θ(n + m) neu auf, statt sie zu aktualisieren. Das ist ein guter Handel, wenn der Graph einmal geladen und dann vielfach abgefragt wird, was auf die meisten Analyse-Workloads zutrifft, und ein schlechter, wenn sich der Graph ständig ändert. Abschnitt 12 behandelt den zweiten Fall.

8. Die Inzidenzmatrix

Die dritte klassische Matrix indiziert Knoten gegen Kanten statt gegen Knoten. Beschriften Sie die sieben Kanten mit e1 bis e7 in der Reihenfolge ihrer Auflistung und setzen Sie B[v][e] = 1 , wenn v ein Endknoten von eist:

       e1 e2 e3 e4 e5 e6 e7
   0 [  1  1  0  0  0  0  0 ]
   1 [  1  0  1  1  0  0  0 ]
   2 [  0  1  1  0  1  0  0 ]
   3 [  0  0  0  1  0  1  1 ]
   4 [  0  0  0  0  1  1  0 ]
   5 [  0  0  0  0  0  0  1 ]

Spaltensummen alle 2      Zeilensummen 2,3,3,3,2,1 = Grade

Die Form ist n × m, der Speicherbedarf also Θ(nm), was für jeden Graphen mit mehr Kanten als Knoten schlechter ist als die Adjazenzmatrix. Niemand speichert einen Graphen so, um damit zu rechnen. Die Inzidenzmatrix verdient ihren Platz aus einem anderen Grund: Sie ist die Brücke zwischen Graphentheorie und Linearer Algebra.

Zwei Identitäten machen das deutlich. Für die obige vorzeichenlose Matrix gilt B BT = A + D, wobei D die Diagonalmatrix der Grade ist. Setzt man die Zahlen des durchgehenden Beispiels ein, bestätigt sich das exakt. Wenn Sie stattdessen jede Kante beliebig orientieren und an ihren Anfangsknoten -1 sowie an ihren Endknoten +1 schreiben, erfüllt die vorzeichenbehaftete Inzidenzmatrix Bs die Gleichung

B_s B_s^T  =  D - A  =  L,   die Laplace-Matrix

unabhängig davon, welche Orientierung Sie gewählt haben. Diese Identität ist der Grund, warum die Laplace-Matrix positiv semidefinit ist, und sie ist der Einstieg in die spektrale Graphentheorie. Diestel führt diese Linie weiter und definiert mit der Inzidenzmatrix den Zyklenraum und den Schnittraum eines Graphen, zwei Vektorräume über dem Körper mit zwei Elementen, deren Dimensionen m - n + c und n - c für einen Graphen mit c Komponenten betragen. Die Inzidenzmatrix ist außerdem der natürliche Rahmen für Flussprobleme: Die Nebenbedingungsmatrix eines linearen Programms für Netzwerkflüsse ist die vorzeichenbehaftete Inzidenzmatrix, und ihre totale Unimodularität ist es, die garantiert, dass das lineare Programm ganzzahlige Optimallösungen hat.

Noch eine Anmerkung. Die Inzidenzmatrix kommt mit Multigraphen eleganter zurecht als die Adjazenzmatrix, denn parallele Kanten sind einfach verschiedene Spalten statt einer Anzahl, die in eine Zelle gequetscht wird. Hypergraphen, bei denen eine Kante mehr als zwei Knoten verbinden darf, haben überhaupt keine sinnvolle Adjazenzmatrix, aber eine völlig natürliche Inzidenzmatrix mit Spaltensummen größer als zwei. Wenn Sie je über gewöhnliche Graphen hinaus verallgemeinern müssen, ist das die Darstellung, die sich verallgemeinern lässt.

9. Richtung, Gewicht, Vielfachheit und Schleifen

Alles bisher setzte einen einfachen ungerichteten Graphen voraus. Vier übliche Abweichungen ändern, was jede Darstellung leisten muss, und genau dort häufen sich Implementierungsfehler.

Richtung. In einem gerichteten Graphen ist die Adjazenzmatrix nicht mehr symmetrisch, und A[u][v] = 1 bedeutet nur einen Bogen von u nach v . Die Adjazenzliste speichert jeden Bogen einmal statt zweimal, die Nachbararrays enthalten also m Einträge statt 2m. Diese Halbierung ist die mit Abstand häufigste Ursache für Speicherschätzungen, die um den Faktor zwei danebenliegen.

Die eigentliche Komplikation ist, dass ein gerichteter Graph zwei Nachbarschaften hat. adj[v] liefert die Nachfolger; Vorgänger erfordern entweder das Durchsuchen der gesamten Struktur oder das Speichern einer zweiten Kopie mit allen Bögen umgedreht. Die Lineare Algebra dünn besetzter Matrizen nennt diese zweite Kopie Compressed Sparse Column, und jeder Algorithmus, der rückwärts läuft, einschließlich der Rückwärtserreichbarkeit, Kosarajus Verfahren für starke Zusammenhangskomponenten und dem rückwärts laufenden Dijkstra in der bidirektionalen Suche, braucht sie. Rechnen Sie mit zwei Strukturen, nicht mit einer.

Gewicht. Gewichte können direkt in den Matrixzellen stehen und die 1 ersetzen. Die Feinheit besteht darin, was aus einer Nicht-Kante wird: 0 ist ein legitimes Gewicht, eine 0 -Zelle ist also mehrdeutig. Üblich ist es, für fehlende Kanten ∞ zu speichern, wenn es um kürzeste Wege geht, genau das setzt Floyd-Warshall beim Start voraus, und 0 in Flusskontexten, wo ein Bogen mit Kapazität null und ein fehlender Bogen wirklich dasselbe sind. Entscheiden Sie sich bewusst für eines. In dünn besetzten Strukturen kommt das Gewicht in ein paralleles Array, das genauso indiziert ist wie targets, wie in der CSR-Auflistung oben, was beide im Gleichschritt hält und die Lokalität bewahrt. Paare stattdessen verschränkt zu speichern, ist ebenfalls in Ordnung und manchmal besser; Gewichte in einer separaten, nach Kanten geschlüsselten Hash-Map zu speichern, ist fast immer schlechter.

Vielfachheit. Parallele Kanten brechen die Grundannahme der Adjazenzmatrix, da eine Zelle einen Wert enthält. Die übliche Abhilfe besteht darin, die Vielfachheit als ganzzahlige Anzahl zu speichern, was bei Zählproblemen funktioniert, aber Daten pro Kante wie unterschiedliche Gewichte oder Kennungen verwirft. Adjazenzlisten nehmen Mehrfachkanten klaglos hin: Derselbe Nachbar taucht einfach mehr als einmal auf. Wenn Sie auf einem Multigraphen Attribute pro Kante brauchen, speichern Sie Kanten kennungen in den Nachbararrays und halten die Attribute in einer separaten, nach diesen Kennungen indizierten Kantentabelle, so machen es die meisten Graphdatenbanken.

Schleifen. Eine Schleife an v setzt einen von null verschiedenen Wert auf die Diagonale. Die Konvention, über die viele stolpern, ist, dass eine Schleife in einem ungerichteten Graphen 2 zum Grad von vbeiträgt, weshalb die übliche ungerichtete Adjazenzmatrix für eine einzelne Schleife A[v][v] = 2 speichert, damit die Identität Zeilensumme gleich Grad erhalten bleibt. Viel Code speichert stattdessen 1 und meldet dann stillschweigend falsche Grade. In einer Adjazenzliste wird dieselbe Frage dazu, ob v in seiner eigenen Nachbarfolge einmal oder zweimal auftaucht, und die ehrliche Antwort lautet: Sie müssen es entscheiden und dokumentieren, denn beide Konventionen existieren in der Literatur.

10. Algebraische Darstellungen

Sobald ein Graph eine Matrix ist, bedeuten Matrixoperationen etwas. Das ist keine Kuriosität, sondern die Grundlage eines ganzen Stils der Graphenberechnung.

Potenzen der Adjazenzmatrix zählen Kantenfolgen. Der Eintrag Ak[u][v] ist genau die Anzahl der Kantenfolgen der Länge k von u nach v, was per Induktion aus der Definition der Matrixmultiplikation folgt. Für das durchgehende Beispiel:

A^2 =  [ 2  1  1  1  1  0 ]
       [ 1  3  1  0  2  1 ]
       [ 1  1  3  2  0  0 ]
       [ 1  0  2  3  0  0 ]
       [ 1  2  0  0  2  1 ]
       [ 0  1  0  0  1  1 ]

Man liest ab: A2[1][4] = 2. Es gibt zwei Kantenfolgen der Länge 2 von 1 nach 4, nämlich 1→2→4 und 1→3→4. Prüfen Sie es am Bild nach. Die Diagonale A2[v][v] lautet 2, 3, 3, 3, 2, 1, also wieder die Gradfolge, denn eine Kantenfolge der Länge 2 von v zu sich selbst ist ein Schritt zu einem Nachbarn und zurück. Eine Potenz weiter gilt trace(A3) = 6, und die Division durch 6 ergibt ein Dreieck, was eine vollständige Suche als {0, 1, 2}bestätigt. Die Division durch 6 zählt die drei Startpunkte und die zwei Richtungen jedes Dreiecks heraus.

Die Laplace-Matrix. Definieren Sie L = D - A:

L =  [  2 -1 -1  0  0  0 ]
     [ -1  3 -1 -1  0  0 ]
     [ -1 -1  3  0 -1  0 ]
     [  0 -1  0  3 -1 -1 ]
     [  0  0 -1 -1  2  0 ]
     [  0  0  0 -1  0  1 ]

Jede Zeile summiert sich zu null, der Einsvektor liegt also im Kern und L ist singulär. Kirchhoffs Matrix-Baum-Satz besagt, dass das Streichen einer beliebigen Zeile und der zugehörigen Spalte und das Bilden der Determinante die Spannbäumedes Graphen zählt. Alle sechs Kofaktoren der obigen Matrix sind gleich 11, und wenn man alle C(7,5) = 21 Teilmengen aus fünf Kanten aufzählt und jede auf Kreisfreiheit prüft, findet man genau 11 Spannbäume. Der Satz ist keine Näherung, sondern eine Identität, und er verwandelt ein Zählproblem, das exponentiell aussieht, in eine einzige Determinante.

Die Eigenwerte der Laplace-Matrix tragen mehr Information. Die Vielfachheit des Eigenwerts 0 ist die Anzahl der Zusammenhangskomponenten. Der zweitkleinste Eigenwert, Fiedlers algebraische Konnektivität, misst, wie schwer der Graph zu zerlegen ist, und das Vorzeichenmuster seines Eigenvektors liefert eine brauchbare Zweiteilung des Graphen. Das ist die Maschinerie hinter dem spektralen Clustering und hinter einem großen Teil von Chungs spektraler Graphentheorie.

Graphen als Lineare Algebra über Halbringen. Die tiefste Fassung dieser Idee ist, dass viele Graphenalgorithmen Matrixoperationen sind , sobald man die Arithmetik austauscht. Ersetzen Sie (+, ×) durch (min, +) , und die Matrixmultiplikation wird zur Relaxation für kürzeste Wege, also ist An-1 über dem Min-Plus-Halbring die Matrix der kürzesten Wege zwischen allen Paaren. Ersetzen Sie sie durch (OR, AND) , und sie wird zur Erreichbarkeit. Die Breitensuche von einer Quelle aus ist die wiederholte Multiplikation eines dünn besetzten Frontvektors mit der Adjazenzmatrix über dem booleschen Halbring. Kepner und Gilbert legen das systematisch dar, und es ist die Spezifikation, die der GraphBLAS-Standard umsetzt. Der Nutzen ist praktisch: Einen Algorithmus als Produkte dünn besetzter Matrizen mit Vektoren auszudrücken, lässt ihn Jahrzehnte optimierter paralleler Linearer Algebra erben, und genau so sind viele GPU-Graphen-Frameworks gebaut.

11. Wann die Matrix gewinnt

Nach Abschnitt 6läge der Schluss nahe, Adjazenzmatrizen seien ein Lehrmittel. Sind sie nicht, und es lohnt sich, genau zu benennen, in welchen vier Situationen die Matrix die richtige Antwort ist.

Kleines n. Ist n einige Hundert, so sind n2 einige Zehntausend Zellen, und das Speicherargument verpufft. Floyd-Warshall berechnet die kürzesten Wege zwischen allen Paaren auf einer Matrix in Θ(n3) Zeit und Θ(n2) Speicher, mit einer dreizeiligen inneren Schleife und nahezu perfektem Cache-Verhalten; für n im Hunderterbereich schlägt das regelmäßig n Dijkstra-Läufe auf einer dünn besetzten Struktur, trotz der schlechteren Asymptotik. Wettbewerbsprogrammierung und Operations Research sind voll von diesem Bereich.

Wirklich dichte Graphen. Oberhalb der zuvor berechneten Dichteschwelle von rund 3,1 % ist die Matrix nicht nur schneller, sondern auch kleiner. Komplementgraphen, Ähnlichkeitsgraphen mit großzügigem Schwellenwert und Bedingungsgraphen aus Planungsproblemen landen regelmäßig hier.

Bitset-Parallelität. Das ist das stärkste Argument. Packt man jede Matrixzeile in Maschinenwörter, werden Mengenoperationen auf Nachbarschaften wortparallel. Die transitive Hülle nach der Methode der Vier Russen, 1970 von Arlazarov, Dinic, Kronrod und Faradzev eingeführt, berechnet Erreichbarkeit in O(n3 / log n) , indem sie Ergebnisse für Bitblöcke vorberechnet; derselbe Trick mit gewöhnlichen 64-Bit-Wörtern bringt einen sehr großen Gewinn beim konstanten Faktor mit fast keinem Code. Das Zählen von Dreiecken, die Suche nach maximalen Cliquen per Branch and Bound und boolesche Matrixprodukte stützen sich alle darauf. Eine dünn besetzte Struktur kann schlicht keine 64 Adjazenztests in einer Instruktion ausführen.

Zugang zu schneller Matrixmultiplikation. Manche Graphenprobleme lassen sich auf Matrixmultiplikation zurückführen und erben deren Exponenten. Seidels Algorithmus berechnet die kürzesten Wege zwischen allen Paaren in einem ungewichteten ungerichteten Graphen in O(nω log n) Zeit durch wiederholtes Quadrieren der Adjazenzmatrix, wobei ω der Exponent der Matrixmultiplikation ist. Alman und Vassilevska Williams drückten ω im Jahr 2021 unter 2,3729, und spätere Verfeinerungen haben ihn noch etwas weiter gesenkt. Diese Schranken sind weitgehend theoretisch, denn die Algorithmen, die sie erreichen, haben Konstanten, die sie unpraktikabel machen, doch die Zurückführung ist real, und es gibt sie nur, weil der Graph eine Matrix ist.

12. Graphen, die sich ändern

Jede Struktur oben wurde so beschrieben, als wäre der Graph fest. Viele sind es nicht, und die Aktualisierungskosten sind eine Dimension, die die übliche Vergleichstabelle unterbewertet.

Die klaren Fälle sind die Extreme. Eine Adjazenzmatrix unterstützt sowohl Einfügen als auch Löschen in O(1), denn beides ist ein einziger Zellschreibvorgang; ihr Problem war nie die Aktualisierungsgeschwindigkeit. Eine Kantenliste hängt in O(1) an, löscht aber in O(m), weil sie die Kante erst finden muss. CSR kann weder das eine noch das andere: Jede strukturelle Änderung baut das Ganze in Θ(n + m)neu auf.

Adjazenzlisten liegen dazwischen und belohnen ein wenig Sorgfalt. Einen Nachbarn an ein dynamisches Array anzuhängen, ist O(1) amortisiert. Das Löschen kostet O(deg(u)) , um den Eintrag zu finden, aber nur O(1) , um ihn zu entfernen, sobald er gefunden ist, sofern Sie das letzte Element in die Lücke tauschen, statt alles nachzuschieben. Wenn Sie in einem ungerichteten Graphen auch die Gegenkopie löschen müssen, speichern Sie zu jedem Eintrag die Position seines Zwillings, damit auch die zweite Löschung O(1) ist, und genau das tut die klassische arrayb­asierte Kantendarstellung mit gepaarten Indizes.

Drei Muster decken die meisten realen Anforderungen ab:

• Sammeln und neu aufbauen. Sammeln Sie Aktualisierungen in einem kleinen Nebenpuffer, beantworten Sie Abfragen gegen CSR plus Puffer und bauen Sie CSR neu auf, wenn der Puffer eine Schwelle überschreitet. Ein Neuaufbau kostet Θ(n + m), ihn über Θ(m) Aktualisierungen zu verteilen, ergibt also O(1) pro Aktualisierung, sobald m mindestens nist, was praktisch jeden realen Graphen abdeckt. So machen es die meisten Analysesysteme, und das genügt in der Regel.
• Grabsteine setzen. Markieren Sie gelöschte Einträge, statt sie zu entfernen, und verdichten Sie regelmäßig. Das Entfernen des Eintrags wird zu O(1) , sobald er gefunden ist, und kein anderer Eintrag bewegt sich, sodass Indizes in die Nachbararrays gültig bleiben. Den Eintrag zu finden, bleibt O(deg(u)) , sofern Sie nicht bereits einen Verweis darauf halten, und jeder spätere Durchlauf muss tote Einträge überspringen.
• Wirklich dynamische Strukturen. Wenn sich Aktualisierungen und Zusammenhangsabfragen abwechseln und beide schnell sein müssen, hat die Literatur zu Datenstrukturen Antworten. Link-Cut-Bäume und Euler-Tour-Bäume verwalten einen sich ändernden Wald in logarithmischer Zeit pro Operation, und die allgemeine dynamische Zusammenhangsverwaltung auf beliebigen Graphen baut darauf auf, mit O(log2 n) amortisiert pro Aktualisierung. Diese sind erheblich verwickelter als alles bisher Genannte, und Sie sollten erst dann dazu greifen, wenn Sie das Muster Sammeln und Neuaufbauen gemessen und für unzureichend befunden haben.

Eine Warnung, die speziell die Hardware betrifft. Eine Struktur, die in der asymptotischen Tabelle schnell ist, kann in der Praxis langsam sein, weil Aktualisierungen sie fragmentieren. Eine Adjazenzliste, die durch eine Million einzelner Einfügungen gewachsen ist, hat ihre Nachbarblöcke in Allokationsreihenfolge über den Heap verstreut, und eine spätere Traversierung bezahlt diese Streuung an jedem Knoten. Sie regelmäßig zu CSR neu aufzubauen, lohnt sich oft allein deshalb, um die Lokalität wiederherzustellen, auch wenn sich keine asymptotische Schranke ändert.

13. Implizite Graphen: gar nichts speichern

Es gibt noch eine Darstellung, und es ist diejenige, deren Existenz man vergisst: den Graphen gar nicht zu speichern.

Ein impliziter oder prozeduraler Graph ist durch eine Funktion definiert. Statt einer Datenstruktur liefern Sie eine Nachfolgerroutine, die zu einem gegebenen Knoten seine Nachbarn bei Bedarf erzeugt. Nichts wird materialisiert, bevor es besucht wird.

Das ist keine Randtechnik. So funktioniert im Grunde jede Zustandsraumsuche:

• Zustandsräume von Rätseln und Spielen. Der Graph der Konfigurationen des Zauberwürfels hat etwa 4,3 × 10¹⁹ Knoten. Ihn zu speichern, ist keine Frage des technischen Aufwands: Ein Bit pro Zustand sind bereits mehr als fünf Exabyte, und die Bögen, bei achtzehn pro Zustand, kämen auf über sechs Zettabyte. Seine Nachfolgerfunktion, eine der achtzehn Flächendrehungen anwenden, ist ein Dutzend Zeilen Code. Suchalgorithmen arbeiten darauf völlig problemlos.
• Planung und Modellprüfung. Der erreichbare Zustandsgraph eines nebenläufigen Programms wird erzeugt, indem man Übergänge ausführt. Explizite Modellprüfer speichern nur die Menge der besuchten Zustände, nie die Kanten.
• Geometrische und Gittergraphen. Ein Gitter zur Wegsuche hat eine offensichtliche Nachfolgerfunktion: vier oder acht Versätze mit einer Bereichs- und Hindernisprüfung. Eine Adjazenzliste für ein Gitter mit 4096 mal 4096 Feldern und Bewegung in acht Richtungen enthält 134 Millionen Einträge, von denen jeden einzelnen eine zweizeilige Funktion exakt reproduziert. Das ist unmittelbar wichtig für A* auf Gittern.

Die Konsequenzen sollte man klar aussprechen. Der Speicherbedarf sinkt von Θ(n + m) für den Graphen auf Θ(|visited|) für die Suche, und genau das macht die Technik überhaupt erst tragfähig. Im Gegenzug verlieren Sie alles, was den Blick auf den ganzen Graphen erfordert: Sie können keine Kanten zählen, keine Gradverteilung berechnen und keinen Algorithmus ausführen, der über alle Knoten iteriert. Sie können auch nicht billig nach Vorgängern fragen, sofern Sie dafür nicht eine zweite Funktion schreiben, und das Neuerzeugen einer Nachbarschaft kostet jedes Mal Rechenzeit statt eines Speicherzugriffs, was für eine häufig wieder besuchte Region die teurere Variante sein kann.

Die implizite Darstellung ist auch das, was die Familie der speicherbeschränkten Suchverfahren erlaubt. Iterative Deepening A* behält nur den aktuellen Pfad statt einer offenen Liste und tauscht wiederholtes Neuerzeugen gegen linearen Speicher, und das ist nur deshalb sinnvoll, weil das Neuerzeugen überhaupt möglich ist.

14. Komprimierte und succinct-Darstellungen

Im Web-Maßstab ist selbst CSR zu groß, und zwei getrennte Forschungslinien greifen das an.

Struktur ausnutzen. Das WebGraph-Framework von Boldi und Vigna ist hier die Standardreferenz. Es beobachtet, dass Seiten derselben Website nahezu identische Mengen ausgehender Links haben, wenn man Webseiten nach URL ordnet, und dass ihre Ziellisten numerisch nah beieinanderliegen. Kodiert man jede Liste als Verweis auf eine ähnliche frühere Liste plus eine kleine Korrektur und kodiert dann die verbleibenden Ziele mit einem Code variabler Länge als Abstände, kommt der Webgraph auf wenige Bits pro Link herunter, eine Größenordnung besser als rohe 32-Bit-Kennungen. Die Technik hängt vollständig von einer guten Knotenordnung ab, und das ist die allgemeine Lehre: Kompression auf Graphen ist überwiegend ein Umbenennungsproblem. Blandford, Blelloch und Kash bewiesen ein ergänzendes Ergebnis für separierbare Graphen, wozu planare Graphen und die meisten Netze gehören: Eine auf Separatoren beruhende Ordnung liefert Darstellungen mit O(n)Bits, die eine Adjazenzabfrage weiterhin in konstanter Zeit beantworten.

Succinct-Datenstrukturen. Eine andere Tradition verlangt Darstellungen, deren Größe sich dem informationstheoretischen Minimum nähert und die Abfragen trotzdem ohne Dekomprimierung beantworten. Jacobsons Arbeit von 1989 führte die Primitiven rank und select ein, die das möglich machen, und Munro und Raman erweiterten das auf Bäume und andere Strukturen. Ein gewurzelter Baum mit n Knoten braucht etwa 2n Bits statt der n Zeiger, die eine naive Kodierung verbraucht, und die Navigation läuft weiterhin in konstanter Zeit. Für einen Graphen ist das allgemeine Problem schwerer, aber die Sichtweise ist die richtige: Die Anzahl der verschiedenen beschrifteten Graphen mit n Knoten und m Kanten liefert eine untere Schranke von etwa m log(n2/m) Bits, und wie nahe eine Darstellung daran herankommt, ist ein sinnvolles Maß, um sie zu beurteilen.

Zu keiner der beiden Linien sollte man standardmäßig greifen. Beide kosten Abfragezeit, beide kosten Implementierungsaufwand, und beide lohnen sich nur, wenn der Graph wirklich nicht hineinpasst. Der praktische Zwischenschritt, den die meisten zuerst versuchen sollten, besteht schlicht darin, die Knoten neu zu nummerieren , sodass Nachbarn nahe beieinanderliegende Kennungen haben. Das allein verbessert das Cache-Verhalten bei gewöhnlichem CSR messbar, und es kostet eine Breitensuche.

15. Ein Entscheidungsverfahren

Alles Obige zu etwas verdichtet, das an der Tastatur brauchbar ist:

1. Können Sie Nachbarn aus einer Regel erzeugen? Wenn der Graph ein Zustandsraum, ein Gitter oder sonst etwas prozedural Definiertes ist, verwenden Sie eine implizite Darstellung und speichern Sie nur, was Sie besuchen.
2. Ist der Graph dicht, oder ist n klein? Oberhalb von etwa 3 % Dichte oder unterhalb von rund tausend Knoten verwenden Sie eine bitgepackte Adjazenzmatrix. Sie erhalten Adjazenz in konstanter Zeit und wortparallele Mengenoperationen, und oberhalb der Dichteschwelle zudem weniger Speicherverbrauch. Unterhalb davon, bei kleinem n, ist die Matrix die größere Struktur, und es spielt schlicht keine Rolle.
3. Durchläuft Ihr Algorithmus nur Kanten? Kruskal, Bellman-Ford und alles Streaming wollen eine Kantenliste. Bauen Sie keinen Index, den Sie nie abfragen werden.
4. Ändert sich der Graph nach dem Laden? Wenn nicht, bauen Sie CSR. Ändert er sich selten, bauen Sie CSR mit einem Aktualisierungspuffer und bauen ihn regelmäßig neu auf. Ändert er sich ständig, verwenden Sie Adjazenzlisten aus dynamischen Arrays mit Löschen per swap-and-pop.

Wenden Sie dann zwei Korrekturen an. Ist der Graph gerichtet und brauchen Sie Vorgänger, bauen Sie auch die umgekehrte Struktur und bezahlen Sie die zweite Kopie. Dominiert der Adjazenztest Ihre Arbeitslast wirklich statt der Nachbariteration, sortieren Sie die Nachbararrays für die Binärsuche, bevor Sie zu Hash-Sets greifen.

16. Häufige Fehler

• Annehmen, die Adjazenzliste sei immer richtig. Sie ist der richtige Standard, keine universelle Antwort. Auf einem dichten Graphen mit 500 Knoten ist eine Adjazenzmatrix kleiner, einfacher und schneller.
• Für einen Algorithmus, der auf einer Matrix läuft, O(n + m) angeben. Traversierung auf einer Adjazenzmatrix ist Θ(n2). Die Schranke gehört zur Darstellung, nicht zum Pseudocode.
• Den Faktor zwei vergessen. Ein ungerichteter Graph speichert in jeder Adjazenzstruktur 2m Einträge, denn jede Kante taucht in den Listen beider Endknoten auf. Ein Array auf m zu dimensionieren, ist ein Pufferüberlauf, kein Performanceproblem.
• Ein 32-Bit-Offset-Array verwenden. CSR-Offsets indizieren in ein Array der Länge 2m. Jenseits von etwa zwei Milliarden gerichteten Bögen läuft das still über und beschädigt jede Nachbarabfrage. Die Ziele dürfen 32-bittig bleiben, solange n unter vier Milliarden liegt; die Offsets nicht.
• Für eine fehlende gewichtete Kante null speichern. Null ist ein gültiges Gewicht. Verwenden Sie einen Platzhalter von ∞, speichern Sie das Vorhandensein getrennt, oder verwenden Sie eine dünn besetzte Struktur, in der Abwesenheit schlicht ein fehlender Eintrag ist.
• CSR durch Sortieren bauen. Die Konstruktion per Counting Sort ist O(n + m). Die Kantenliste zuerst zu sortieren, ist O(m log m) und unnötig, auch wenn es eine vertretbare Abkürzung ist, falls Sie ohnehin sortierte Nachbararrays wollten.
• Den umgekehrten Graphen nicht speichern. Vorgängerabfragen auf einem gerichteten CSR erfordern einen vollständigen Durchlauf durch das Zielarray. Wenn Sie sie überhaupt stellen, bauen Sie die transponierte Struktur einmalig.
• Eine Darstellung allein nach der Asymptotik wählen. Eine Adjazenzliste und CSR sind beide Θ(n + m), und CSR ist wegen der Lokalität regelmäßig um ein Mehrfaches schneller. Konstante Faktoren bei speichergebundenem Graphencode sind kein Rundungsfehler.
• Schleifen bei der Gradzählung falsch behandeln. Eine Schleife erhöht den Grad in einem ungerichteten Graphen um 2. Wofür auch immer Sie sich bei der Adjazenzstruktur entscheiden, sorgen Sie dafür, dass die Gradfunktion dazu passt.

17. Glossar

19. Quellen

Quellen für die Definitionen, Komplexitätsschranken und Techniken oben, zusammen mit den Standardwerken, in denen dieses Material entwickelt wird, in chronologischer Reihenfolge aufgeführt.

1. Arlazarov, V. L., Dinic, E. A., Kronrod, M. A. und Faradzev, I. A. (1970). “On economical construction of the transitive closure of a directed graph.” Soviet Mathematics Doklady, 11, 1209–1210.
2. Gustavson, F. G. (1972). “Some basic techniques for solving sparse systems of linear equations.” In Sparse Matrices and Their Applications, Plenum Press, 41–52.
3. Tarjan, R. E. (1972). “Depth-first search and linear graph algorithms.” SIAM Journal on Computing, 1(2), 146–160.
4. Hopcroft, J. und Tarjan, R. E. (1973). “Algorithm 447: efficient algorithms for graph manipulation.” Communications of the ACM, 16(6), 372–378.
5. Aho, A. V., Hopcroft, J. E. und Ullman, J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley.
6. Duff, I. S., Erisman, A. M. und Reid, J. K. (1986). Direct Methods for Sparse Matrices. Oxford University Press.
7. Jacobson, G. (1989). “Space-efficient static trees and graphs.” Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), 549–554.
8. Seidel, R. (1995). “On the all-pairs-shortest-path problem in unweighted undirected graphs.” Journal of Computer and System Sciences, 51(3), 400–403.
9. Chung, F. R. K. (1997). Spectral Graph Theory. CBMS Regional Conference Series in Mathematics 92, American Mathematical Society.
10. Munro, J. I. und Raman, V. (2001). “Succinct representation of balanced parentheses and static trees.” SIAM Journal on Computing, 31(3), 762–776.
11. Blandford, D. K., Blelloch, G. E. und Kash, I. A. (2003). “Compact representations of separable graphs.” Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 679–688.
12. Boldi, P. und Vigna, S. (2004). “The WebGraph framework I: compression techniques.” Proceedings of the 13th International World Wide Web Conference (WWW), 595–602.
13. Cormen, T. H., Leiserson, C. E., Rivest, R. L. und Stein, C. (2009). Introduction to Algorithms, 3. Auflage, Kapitel 22. MIT Press.
14. Kepner, J. und Gilbert, J., Herausgeber (2011). Graph Algorithms in the Language of Linear Algebra. Society for Industrial and Applied Mathematics.
15. Diestel, R. (2017). Graph Theory, 5. Auflage. Springer, Graduate Texts in Mathematics 173.
16. Alman, J. und Vassilevska Williams, V. (2021). “A refined laser method and faster matrix multiplication.” Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 522–539.