Adjazenzliste und Matrixdarstellung des Diagramms

Auch wenn sie alle unterschiedlich aussehen Arten von Diagrammen lässt sich auf ähnliche Weise darstellen. Im Allgemeinen gibt es zwei Arten der Diagrammdarstellung:

1. Adjazenzmatrix
2. Adjazenzliste

Adjazenzliste

Die Adjazenzliste besteht aus verknüpften Listen. Jeder Scheitelpunkt wird als Array-Index betrachtet und jedes Element stellt eine verknüpfte Liste dar. Diese verknüpften Listen enthalten die Scheitelpunkte, die Kanten mit dem Indexscheitelpunkt haben.

Hier ist ein Beispiel für eine Adjazenzliste:

Nehmen wir an, ein Graph enthält die Anzahl V Eckpunkte und die Anzahl E Kanten.

Im Allgemeinen beträgt die Raumkomplexität O(V + E).

Die schlimmste Raumkomplexität beträgt O(V2) wenn der gegebene Graph der vollständige Graph ist

Adjazenzmatrix

Die Adjazenzmatrix besteht aus einem 2D-Array. Wenn ein Diagramm eine V-Anzahl von Eckpunkten hat, beträgt die Größe der Matrix VxV.

Sagen, matrix[i][j] = 5. Das bedeutet, dass es eine Kante zwischen Knoten i und j gibt, deren Gewicht 5 beträgt.

Schauen wir uns den folgenden Graphen und seine Adjazenzmatrix an:

Wir haben das geschaffen 2D-Array mit diesen Schritten:

Schritt 1) Scheitelpunkt A hat eine direkte Kante mit B und das Gewicht beträgt 5. Die Zelle in Zeile A und Spalte B wird also mit 5 gefüllt. Die restlichen Zellen in Zeile A werden mit Null gefüllt.

Schritt 2) Die Scheitelpunkte B haben eine direkte Kante zu C und das Gewicht beträgt 4. Die Zelle in Zeile B und Spalte C wird also mit 4 gefüllt. Die übrigen Zellen in Zeile B werden mit Null gefüllt, da B zu keinem eine ausgehende Kante hat andere Knoten.

Schritt 3) Die Eckpunkte C haben keine direkten Kanten zu anderen Eckpunkten. Zeile C wird also mit Nullen gefüllt.

Schritt 4) Scheitelpunkt D hat eine gerichtete Kante mit A und C.

• Hier hat die Zelle in Zeile D und Spalte A den Wert 7. Zellen in Zeile D und Spalte C haben den Wert 2.
• Die restlichen Zellen in Zeile D werden mit Nullen gefüllt.

Schritt 5) Die Scheitelpunkte E haben eine gerichtete Kante mit B und D. Die Zelle in Zeile E und Spalte B hat einen Wert von 6. Zellen in Zeile E und Spalte D haben einen Wert von 3. Die übrigen Zellen in Zeile D haben einen Wert von XNUMX mit Nullen gefüllt.

Hier sind einige Punkte, die Sie beachten sollten:

• Der Graph hat keine Selbstschleifen, wenn die Primärdiagonale der Adjazenzmatrix 0 ist.
• Der Graph ist ein gerichteter Graph, wenn die Indizes (a,b) und (b,a) nicht den gleichen Wert haben. Andernfalls ist der Graph ein gerichteter Graph.
• Das Diagramm ist ein gewichtetes Diagramm, wenn der Wert der Zellen mehr als 1 beträgt.

Es gibt ein Problem mit der Adjazenzmatrix, da sie quadratische Leerzeichen erfordert. Hier speichern wir die Kanten, die nicht verbunden sind. Diese Kanten reservieren Platz im Speicher.

Wenn wir beispielsweise ein Diagramm mit 100 Knoten haben, werden 10 Zellen benötigt, um es im zu speichern RAM. Mit weniger Kanten im Graphen kann die Zuweisung eines so großen Speichers Verschwendung sein. Die Speicherkomplexität bei Verwendung der Adjazenzmatrix beträgt also O(N2), wobei N die Anzahl der Knoten im Diagramm bedeutet.