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:

Adjazenzliste

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

Im Allgemeinen ist der Raum complexität wird sein O(V + E).

Worst-Case-Weltraumkommunikationplexität wird sein 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 das Folgende anwing Diagramm und seine Adjazenzmatrix:

Adjazenzmatrix

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. Anderewise, der Graph ist 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. Da es weniger Kanten im Diagramm gibt, kann die Zuweisung eines derart großen Speichers eine Verschwendung sein. Also, die Weltraumkommunikationplexity unter Verwendung der Adjazenzmatrix wird sein O(N2), wobei N die Anzahl der Knoten im Diagramm bedeutet.