Wie verwende ich eine Adjazenzmatrix zum Speichern von Diagrammen in Java?

1. Der letzte Schliff

Die Adjazenzmatrix verwendet normalerweise ein eindimensionales Array zum Speichern der Informationen der Knoten im Diagramm und ein zweidimensionales Array zum Speichern der Adjazenzbeziehung zwischen den Knoten im Diagramm Graph.

Adjazenzmatrix kann zur Darstellung ungerichteter Graphen, gerichteter Graphen und Netzwerke verwendet werden.

1. Adjazenzmatrix des ungerichteten Graphen

Wenn es im ungerichteten Graphen eine Kante vom Knoten Vi zum Knoten Vj gibt, dann ist die Adjazenzmatrix M[i][j] = M[j][i]= 1, andernfalls M[i][j] = 0.

Die Adjazenzmatrix eines ungerichteten Graphen wird wie folgt angegeben.

a Die Adjazenzmatrix eines ungerichteten Graphen ist eine symmetrische Matrix und eindeutig.

b Die Anzahl der Nicht-Nullen in der i-ten Zeile oder i-ten Spalte entspricht genau dem Grad des i-ten Knotens.

2. Adjazenzmatrix des gerichteten Graphen

Wenn es im gerichteten Graphen eine Kante vom Knoten Vi zum Knoten Vj gibt, dann ist die Adjazenzmatrix M[i][j]=1, andernfalls M[i][j] = 0.

Die Adjazenzmatrix eines gerichteten Graphen wird wie folgt angegeben.

a Die Adjazenzmatrix eines gerichteten Graphen ist nicht unbedingt symmetrisch.

b Die Anzahl der Nicht-Null-Elemente in der i-ten Zeile entspricht genau dem Out-Grad des i-ten Knotens, und die Anzahl der Nicht-Null-Elemente in der i-ten Spalte entspricht genau dem In-Grad von der i-te Knoten.

3. Die Adjazenzmatrix des Netzwerks

Das Netzwerk ist ein gewichteter Graph und muss die Gewichte der Kanten speichern. Die Adjazenzmatrix wird ausgedrückt als: M[i][j] = Wij in anderen Fällen unendlich.

2. Algorithmusschritte

1 Geben Sie die Anzahl der Knoten und Kanten ein.

2 Geben Sie nacheinander die Knoteninformationen ein und speichern Sie sie im Knotenarray Vex[].

3 Initialisieren Sie die Adjazenzmatrix. Wenn es sich um ein Diagramm handelt, initialisieren Sie sie auf 0. Wenn es sich um ein Netzwerk handelt, initialisieren Sie sie auf unendlich.

4 Geben Sie nacheinander die beiden Knoten ein, die an jeder Kante angebracht sind. Wenn es sich um ein Netzwerk handelt, müssen Sie auch das Gewicht der Kante eingeben.

• Wenn es sich um einen ungerichteten Graphen handelt, geben Sie a und b ein, fragen Sie die Speicherindizes i und j der Knoten a und b im Knotenarray Vex[] ab, sei Edge[i][j]=Edge[j][ i]=1.

• Wenn es sich um einen gerichteten Graphen handelt, geben Sie a, b ein, fragen Sie die Speicherindizes i, j der Knoten a, b im Knotenarray Vex[] ab, sei Edge[i][j]=1.

• Wenn es sich um ein ungerichtetes Netzwerk handelt, geben Sie a, b, w ein, fragen Sie die Speicherindizes i und j der Knoten a und b im Knotenarray Vex[] ab, sei Edge[i][j]=Edge[j ][i]=w.

• Wenn es sich um ein gerichtetes Netzwerk handelt, geben Sie a, b, w ein, fragen Sie die Speicherindizes i und j der Knoten a und b im Knotenarray Vex[] ab, sei Edge[i][j]=w.

3. Implementierung

rrree

4. Grün ist die Eingabe und Weiß ist die Ausgabe.

Das obige ist der detaillierte Inhalt vonWie verwende ich eine Adjazenzmatrix zum Speichern von Diagrammen in Java?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!