If you're seeing this message, it means we're having trouble loading external resources on our website.

Wenn du hinter einem Webfilter bist, stelle sicher, dass die Domänen *. kastatic.org und *. kasandbox.org nicht blockiert sind.

Hauptinhalt

Graphen darstellen

Graphen können auf verschiedene Arten repräsentiert werden. Jede Art der Darstellung hat ihre jeweiligen Vor- und Nachteile. Einige der Algorithmen, die wir mit Graphen als Eingabe ausführen wollen, benötigen die eine oder andere Repräsentation. Im folgenden werden wir drei Arten der Graphenrepräsentation kennenlernen.
Wir werden diese nach drei Kriterien beurteilen. Dabei unterscheiden wir nach dem Umfang des benötigten Speichers, der für eine Darstellung benötigt wird. Wir verwenden dazu die asymptotische Notation. Ja, wir können die asymptotische Notation für andere Zwecke als Laufzeiten verwenden! Sie ist wirklich eine gute Methode um, Funktionen zu charakterisieren, und eine Funktion kann eine Laufzeit, einen Platzbedarf oder eine andere Ressource beschreiben. Die anderen zwei Kriterien, die wir verwenden, beziehen sich auf die Zeit: Erstens untersuchen wir, wie lange es dauert, um festzustellen, ob eine gegebene Kante Teil eines Graphen ist. Zweitens bestimmen wir wie lange es dauert um den Nachbarn eines gegebenen Knotens zu finden.
Es ist üblich, Knoten nicht mit Namen zu identifizieren (wie z.B. "Audrey", "Boston" oder "Pullover"), sondern stattdessen mit einer Nummer. Das heißt, wir nummerieren normalerweise die |V| Ecken von 0 bis |V|1. Hier ist der soziale Netzwerk Graph mit seinen 10 nummerierten Knoten.

Kantenlisten

Eine einfache Möglichkeit, einen Graphen darzustellen, ist eine Liste oder ein Array von |E| Kanten, die wir eine Kantenliste nennen. Um eine Kante zu repräsentieren, nehmen wir nur ein Array von zwei Knoten-Zahlen oder ein Array von Objekten, die die Knoten-Zahlen der Knoten enthalten, die den Kanten verbunden sind. Wenn Kanten Gewichte haben, füge entweder ein drittes Element zum Array hinzu oder mehr Informationen zum Objekt, das das Gewicht der Kante angibt. Da jeder Rand nur zwei oder drei Zahlen enthält, ist der benötigte Gesamtspeicher für eine Kantenliste Θ(E). Zum Beispiel, hier ist die Darstellung, einer Kantenliste in JavaScript für unser soziales Netzwerk:
[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5],
[3,8], [4,5], [4,9], [7,8], [7,9] ]
Kantenlisten sind einfach, aber wenn wir bestimmen wollen, ob der Graph eine bestimmte Kante enthält, müssen wir die Kantenliste durchsuchen. Wenn die Kantenliste unsortiert ist, dann ist das eine lineare Suche durch |E| Kanten. Eine Frage zum Nachdenken: Wie können wir eine Kantenliste organisieren, um die Suche nach einer bestimmten Kante zu beschleunigen und in O(lgE) zu erledigen? Die Antwort ist ein wenig heikel.

Adjazenzmatrizen

Um einen Graphen mit |V| Ecken darzustellen, wird eine Nachbarschaftsmatrix der Größe |V||V| aus 0-en und 1-ern, verwendet. Ein Eintrag in Zeile i und Spalte j ist gleich 1 ist, wenn die Kante (i,j) im Graphen existiert. Wenn nicht, dann verwendet man den Wert 0, um eine abwesende Kante anzuzeigen. Wenn man ein Kantengewicht angeben möchte, dann trägt man es an Stelle der 1 in Zeile i, Spalte j ein. Hier ist die Nachbarschaftsmatrix für das soziale Netzwerk:
In JavaScript repräsentieren wir diese Matrix folgendermaßen:
[ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
  [1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
  [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
  [0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
  [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
  [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
  [1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
  [0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]
Mit einer Nachbarschaftsmatrix können wir in konstanter Zeit herausfinden, ob eine Kante existiert, indem wir einfach den entsprechenden Eintrag in der Matrix abfragt. Wenn z. B. die Nachbarschaftsmatrix graph benannt wird, können wir abfragen, ob die Kante (i,j) im Graphen enthalten ist, indem man graph [i] [j] betrachtet. Was sind die Nachteile einer Nachbarschaftsmatrix? Zwei Dinge: Zuerst benötigt sie Θ(V2) Speicher, auch wenn der Graph spärlich ist , d.h. relativ wenige Kanten hat. Mit anderen Worten, für einen spärlichen Graphen enthält die Nachbarschaftsmatrix meist Nullen, und wir verwenden viel Speicherplatz, um nur wenige Kanten zu repräsentieren. Zweitens, wenn du herausfinden willst, welche Knoten an einen gegebenen Knoten i angrenzen, musst du alle |V| Einträge in Zeile i untersuchen, auch wenn nur eine kleine Anzahl von Eckpunkten an den Knoten i angrenzen.
Bei einem ungerichteten Graphen ist die Nachbarschaftsmatrix symmetrisch : Das heißt, dass wenn der Eintrag in Zeile i, Spalte j 1 ist, dann ist auch der Eintrag in j, Spalte i Eintrag 1\ ist. Bei einem gerichteten Graphen muss die Nachbarschaftsmatrix nicht symmetrisch sein.

Adjazenzlisten

Die Darstellung eines Graphen mit Nachbarschaftslisten kombiniert Nachbarschaftsmatrizen mit Kantenlisten. Für jeden Knoten i, wird ein Array benachbarter Knoten angelegt. Wir haben typischerweise ein Array von |V| Nachbarschaftslisten, also eine Nachbarschaftsliste pro Knoten. Hier ist eine Nachbarschaftslisten-Darstellung des sozialen Netzwerks:
In JavaScript repräsentieren wir diese Nachbarschaftslisten durch Arrays wie folgt:
[ [1, 6, 8],
  [0, 4, 6, 9],
  [4, 6],
  [4, 5, 8],
  [1, 2, 3, 5, 9],
  [3, 4],
  [0, 1, 2],
  [8, 9],
  [0, 3, 7],
  [1, 4, 7] ]
In einer Nachbarschaftsliste dürfen die Knotennummern in beliebiger Reihenfolge angeordnet sein. Es ist allerdings of einfacher, sie in aufsteigender Reihenfolge aufzuführen, wie im obigen Beispiel gezeigt.
Wir können die Nachbarschaftsliste jedes Knotens in konstanter Zeit erreichen, weil wir nur in ein Array hinein indizieren müssen. Um herauszufinden, ob eine Kante (i,j) im Graphen vorhanden ist, gehen wir in die Nachbarschaftsliste von i in konstanter Zeit und suchen dann nach j in i 's Nachbarschaftsliste. Wie lange dauert das im ungünstigsten Fall? Die Antwort ist Θ(d), wobei d der Grad des Knotens i ist, denn dieser gibt an, wie lange i 's Nachbarschaftsliste ist. Der Grad des Knotens i könnte so groß sein wie |V|1 (also in dem Fall, wenn i an alle anderen |V|1 Knoten angrenzt) oder so niedrig sein wie 0 (wenn i isoliert, also ohne Zwischenkanten, ist). In einem ungerichteten Graphen ist der Knoten j genau dann in i 's Nachbarschaftsliste enthalten, wenn auch i in der Nachbarschaftsliste von j enthalten ist. Wenn wir mit gerichteten Graphen arbeiten, dann ist jedes Element in jeder Nachbarschaftsliste entweder ein zweidimensionales Array oder ein Objekt, welches die Knotennummer und das Kantengewicht enthält.
Wir können eine For-Loop verwenden, um über die Knoten einer Nachbarschaftsliste zu iterieren. Angenommen, wir haben eine Nachbarschaftslisten-Darstellung eines Graphen in der Variablen graph, so dass graph [i] ein Array mit den Nachbarn des Knotens i ist. Um eine Funktion doStuff aufzurufen, die jeden an i angrenzenden Knoten aufruft, könnten wir den folgenden JavaScript-Code verwenden:
for (var j = 0; j < graph[i].length; j++) {
    doStuff(graph[i][j]);
}
Alternativ kann man das auch so schreiben:
var vertex = graph[i];
for (var j = 0; j < vertex.length; j++) {
    doStuff(vertex[j]);
}
Wie viel Speicherplatz belegen die Nachbarschaftslisten? Wir haben |V| Listen, und obwohl jede Liste so viele wie |V|1 Knoten haben könnte, enthalten die Nachbarschaftslisten für einen ungerichteten Graphen 2|E| Elemente. Warum 2|E|? Jede Kante (i,j) erscheint genau zweimal in den Nachbarschaftslisten, einmal in i 's Liste und einmal in j' s Liste, und es gibt |E| Kanten. Für einen gerichteten Graphen enthalten die Nachbarschaftslisten insgesamt |E| Elements, ein Element pro gerichteter Kante.

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.

Willst du an der Diskussion teilnehmen?

Noch keine Beiträge.
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.