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 |$vertical bar, V, vertical bar Ecken von 0 bis $| V | -1$vertical bar, V, vertical bar, minus, 1. Hier ist der soziale Netzwerk Graph mit seinen 10 nummerierten Knoten.

Eine einfache Möglichkeit, einen Graphen darzustellen, ist eine Liste oder ein Array von $| E |$vertical bar, E, vertical bar 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 $\Theta (E)$\Theta, left parenthesis, E, right parenthesis. Zum Beispiel, hier ist die Darstellung, einer Kantenliste in JavaScript für unser soziales Netzwerk:

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 |$vertical bar, E, vertical bar Kanten. Eine Frage zum Nachdenken: Wie können wir eine Kantenliste organisieren, um die Suche nach einer bestimmten Kante zu beschleunigen und in $O (\lg E)$O, left parenthesis, \lg, E, right parenthesis zu erledigen? Die Antwort ist ein wenig heikel.

Um einen Graphen mit $| V |$vertical bar, V, vertical bar Ecken darzustellen, wird eine Nachbarschaftsmatrix der Größe $| V | \cdot | V |$vertical bar, V, vertical bar, dot, vertical bar, V, vertical bar aus 0-en und 1-ern, verwendet. Ein Eintrag in Zeile $i$i und Spalte $j$j ist gleich 1 ist, wenn die Kante $(i, j)$left parenthesis, i, comma, j, right parenthesis 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$i, Spalte $j$j ein. Hier ist die Nachbarschaftsmatrix für das soziale Netzwerk:

In JavaScript repräsentieren wir diese Matrix folgendermaßen:

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)$left parenthesis, i, comma, j, right parenthesis im Graphen enthalten ist, indem man graph [i] [j] betrachtet. Was sind die Nachteile einer Nachbarschaftsmatrix? Zwei Dinge: Zuerst benötigt sie $\Theta (V^2)$\Theta, left parenthesis, V, squared, right parenthesis 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$i angrenzen, musst du alle $| V |$vertical bar, V, vertical bar Einträge in Zeile $i$i untersuchen, auch wenn nur eine kleine Anzahl von Eckpunkten an den Knoten $i$i angrenzen.

Bei einem ungerichteten Graphen ist die Nachbarschaftsmatrix symmetrisch : Das heißt, dass wenn der Eintrag in Zeile $i$i, Spalte $j$j 1 ist, dann ist auch der Eintrag in $j$j, Spalte $i$i Eintrag 1\ ist. Bei einem gerichteten Graphen muss die Nachbarschaftsmatrix nicht symmetrisch sein.

Die Darstellung eines Graphen mit Nachbarschaftslisten kombiniert Nachbarschaftsmatrizen mit Kantenlisten. Für jeden Knoten $i$i, wird ein Array benachbarter Knoten angelegt. Wir haben typischerweise ein Array von $| V |$vertical bar, V, vertical bar 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:

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)$left parenthesis, i, comma, j, right parenthesis im Graphen vorhanden ist, gehen wir in die Nachbarschaftsliste von $i$i in konstanter Zeit und suchen dann nach $j$j in $i$i 's Nachbarschaftsliste. Wie lange dauert das im ungünstigsten Fall? Die Antwort ist $\Theta (d)$\Theta, left parenthesis, d, right parenthesis, wobei $d$d der Grad des Knotens $i$i ist, denn dieser gibt an, wie lange $i$i 's Nachbarschaftsliste ist. Der Grad des Knotens $i$i könnte so groß sein wie $| V | -1$vertical bar, V, vertical bar, minus, 1 (also in dem Fall, wenn $i$i an alle anderen $| V | -1$vertical bar, V, vertical bar, minus, 1 Knoten angrenzt) oder so niedrig sein wie 0 (wenn $i$i isoliert, also ohne Zwischenkanten, ist). In einem ungerichteten Graphen ist der Knoten $j$j genau dann in $i$i 's Nachbarschaftsliste enthalten, wenn auch $i$i in der Nachbarschaftsliste von $j$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$i ist. Um eine Funktion doStuff aufzurufen, die jeden an $i$i angrenzenden Knoten aufruft, könnten wir den folgenden JavaScript-Code verwenden:

Alternativ kann man das auch so schreiben:

Wie viel Speicherplatz belegen die Nachbarschaftslisten? Wir haben $|V|$vertical bar, V, vertical bar Listen, und obwohl jede Liste so viele wie $|V| -1$vertical bar, V, vertical bar, minus, 1 Knoten haben könnte, enthalten die Nachbarschaftslisten für einen ungerichteten Graphen $2|E|$2, vertical bar, E, vertical bar Elemente. Warum $2 | E |$2, vertical bar, E, vertical bar? Jede Kante $(i, j)$left parenthesis, i, comma, j, right parenthesis erscheint genau zweimal in den Nachbarschaftslisten, einmal in $i$i 's Liste und einmal in $j$j' s Liste, und es gibt $| E |$vertical bar, E, vertical bar Kanten. Für einen gerichteten Graphen enthalten die Nachbarschaftslisten insgesamt $| E |$vertical bar, E, vertical bar 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.