Was ist die Diagrammdatenstruktur?

A Graph ist eine nichtlineare Datenstruktur, die aus Eckpunkten und Kanten besteht. Die Eckpunkte werden manchmal auch als Knoten bezeichnet und die Kanten sind Linien oder Bögen, die zwei beliebige Knoten im Diagramm verbinden. Formaler ausgedrückt besteht ein Graph aus einer Reihe von Eckpunkten( IN ) und eine Reihe von Kanten( UND ). Der Graph wird mit bezeichnet G(V, E) .

Darstellungen von Graphen

Hier sind die beiden häufigsten Arten, ein Diagramm darzustellen:

1. Adjazenzmatrix
2. Adjazenzliste

Adjazenzmatrix

Eine Adjazenzmatrix ist eine Möglichkeit, einen Graphen als boolesche Matrix (Nullen und Einsen) darzustellen.

Nehmen wir an, dass es welche gibt N Eckpunkte im Diagramm Erstellen Sie also eine 2D-Matrix adjMat[n][n] mit der Dimension n x n.

• Wenn es eine Kante vom Scheitelpunkt gibt ich Zu J , markieren adjMat[i][j] als 1 .
• Wenn es keine Kante vom Scheitelpunkt gibt ich Zu J , markieren adjMat[i][j] als 0 .

Darstellung eines ungerichteten Graphen zur Adjazenzmatrix:

Die folgende Abbildung zeigt einen ungerichteten Graphen. Zunächst wird die gesamte Matrix initialisiert 0 . Wenn es eine Kante von der Quelle zum Ziel gibt, fügen wir ein 1 in beiden Fällen ( adjMat[Ziel] Und adjMat [ Ziel]) weil wir in beide Richtungen gehen können.

Ungerichteter Graph zur Adjazenzmatrix

Darstellung des gerichteten Graphen zur Adjazenzmatrix:

Die folgende Abbildung zeigt einen gerichteten Graphen. Zunächst wird die gesamte Matrix initialisiert 0 . Wenn es eine Kante von der Quelle zum Ziel gibt, fügen wir ein 1 für dieses besondere adjMat[Ziel] .

Gerichteter Graph zur Adjazenzmatrix

Adjazenzliste

Ein Array von Listen wird zum Speichern von Kanten zwischen zwei Scheitelpunkten verwendet. Die Größe des Arrays entspricht der Anzahl Eckpunkte (d. h. n) . Jeder Index in diesem Array repräsentiert einen bestimmten Scheitelpunkt im Diagramm. Der Eintrag am Index i des Arrays enthält eine verknüpfte Liste mit den Scheitelpunkten, die an den Scheitelpunkt angrenzen ich .

Nehmen wir an, dass es welche gibt N Eckpunkte im Diagramm Erstellen Sie also eine Array von Listen der Größe N als adjList[n].

• adjList[0] enthält alle Knoten, die mit dem Scheitelpunkt verbunden (Nachbar) sind 0 .
• adjList[1] enthält alle Knoten, die mit dem Scheitelpunkt verbunden (Nachbar) sind 1 und so weiter.

Darstellung des ungerichteten Graphen zur Adjazenzliste:

Der folgende ungerichtete Graph hat 3 Eckpunkte. Es wird also ein Listenarray der Größe 3 erstellt, wobei jeder Index die Eckpunkte darstellt. Jetzt hat Scheitelpunkt 0 zwei Nachbarn (d. h. 1 und 2). Fügen Sie also die Scheitelpunkte 1 und 2 an den Indizes 0 des Arrays ein. In ähnlicher Weise hat Scheitelpunkt 1 zwei Nachbarn (d. h. 2 und 0). Fügen Sie also die Scheitelpunkte 2 und 0 an den Indizes 1 des Arrays ein. Fügen Sie für Scheitelpunkt 2 dessen Nachbarn in das Listenarray ein.

Ungerichtete Graph-zu-Adjazenz-Liste

Darstellung des gerichteten Graphen zur Adjazenzliste:

Der unten gerichtete Graph hat 3 Eckpunkte. Es wird also ein Listenarray der Größe 3 erstellt, wobei jeder Index die Eckpunkte darstellt. Jetzt hat Scheitelpunkt 0 keine Nachbarn. Für Scheitelpunkt 1 gibt es zwei Nachbarn (d. h. 0 und 2). Fügen Sie also die Scheitelpunkte 0 und 2 an den Indizes 1 des Arrays ein. Fügen Sie für Scheitelpunkt 2 dessen Nachbarn in das Listenarray ein.

Gerichteter Graph zur Adjazenzliste