Adjazenzmatrix in Python
- Erstellen Sie eine Adjazenzmatrix
- Erstellen Sie eine Adjazenzmatrix in Python mit 2D-Listen
- Erstellen Sie eine Adjazenzmatrix in Python mit dem NumPy-Modul
- Abschluss
Eine Diagrammdatenstruktur wird in Python verwendet, um verschiedene reale Objekte wie Netzwerke und Karten darzustellen. Wir können einen Graphen mit einer Adjazenzmatrix darstellen.
In diesem Artikel werden verschiedene Möglichkeiten zur Implementierung der Adjazenzmatrix in Python erörtert.
Erstellen Sie eine Adjazenzmatrix
Betrachten Sie die folgende Grafik.
In der Grafik gibt es 6 Knoten, die von 1 bis 6 nummeriert sind. Es gibt 7 Kanten in der Grafik, die die Knoten verbinden; eine Kante eij verbindet Knoten i und Knoten j.
Um den Graphen darzustellen, verwenden wir eine Adjazenzmatrix.
- Eine Adjazenzmatrix besteht aus einem zweidimensionalen Gitter.
- Jede Zeile oder Spalte im Raster repräsentiert einen Knoten.
- Wenn für einen ungewichteten Graphen, wie oben gezeigt, der Wert an der Position
(i,j)im Raster 1 ist, bedeutet dies, dass Knoteniund Knotenjverbunden sind. - Wenn der Wert an Position
(i,j)0 ist, sind Knoteniund Knotenjnicht verbunden.
Wenn Sie eine Adjazenzmatrix für den Graphen im obigen Bild erstellen möchten, sieht sie wie folgt aus.
| 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 | 0 |
Die obige Tabelle zeigt, dass der Wert an Position (i,j) auch an Position (j,i) vorhanden ist. Dies liegt daran, dass die Kante eij dieselbe ist wie die Kante eji.
Dies führt auch zu einer Adjazenzmatrix, die entlang ihrer Diagonalen symmetrisch ist.
In einem ungewichteten Diagramm haben die Kanten kein Gewicht. Mit anderen Worten, alle Kanten haben gleiche Gewichte.
Aus diesem Grund enthält die Adjazenzmatrix nur die Werte 0 und 1.
Betrachten Sie nun den folgenden gewichteten Graphen.
Bei einem gewichteten Graphen bleibt bis auf die Gewichte für die Kanten alles gleich. Sie können beobachten, dass jeder Kante im Bild ein Wert zugewiesen wurde.
Daher ist in der Adjazenzmatrix der Wert an Position (i,j) das Gewicht der Kante eij im Graphen.
Die Adjazenzmatrix für das obige Bild sieht wie folgt aus.
| 0 | 5 | 0 | 0 | 0 | 0 |
| 5 | 0 | 1 | 12 | 0 | 0 |
| 0 | 1 | 0 | 8 | 0 | 4 |
| 0 | 12 | 8 | 0 | 7 | 0 |
| 0 | 0 | 0 | 7 | 0 | 2 |
| 0 | 0 | 4 | 0 | 2 | 0 |
Auch hier können Sie beobachten, dass der Wert an Position (i,j) in der Matrix auch an Position (j,i) vorhanden ist. Dies liegt daran, dass die Kante eij dieselbe ist wie die Kante eji.
Dies führt wiederum zu einer symmetrischen Adjazenzmatrix entlang ihrer Diagonalen.
Erstellen Sie eine Adjazenzmatrix in Python mit 2D-Listen
Um eine Adjazenzmatrix für einen ungewichteten Graphen mit n Knoten zu erstellen, erstellen wir zunächst eine zweidimensionale Liste mit n inneren Listen. Zusätzlich enthält jede innere Liste n Nullen.
Nachdem wir eine zweidimensionale Liste mit Nullen erstellt haben, weisen wir den Positionen (i,j), an denen die Kante eij im Graphen existiert, 1 zu. Für diese Aufgabe verwenden wir die folgenden Schritte.
-
Zuerst erstellen wir eine leere Liste namens
adjacency_matrix. Danach wandeln wir es mit einerfor-Schleife und derappend()-Methode in eine 2-dimensionale Liste um. -
Innerhalb der
for-Schleife erstellen wir eine leere Liste mit dem Namenrow. Dann werden wir die leere Liste mit Nullen füllen, indem wir eine weiterefor-Schleife verwenden, und schließlich werden wirrowan dieadjacency_matrixanhängen. -
Im Code haben wir die Menge der Kanten durch eine Liste von Tupeln dargestellt. Jedes Tupel enthält 2 Werte, die die verbundenen Knoten des Diagramms darstellen.
-
Nachdem wir die Kanten definiert haben, weisen wir den Positionen, an denen Kanten im Graphen vorhanden sind, mit einer
for-Schleife den Wert 1 zu.
Code:
import pprint
row_num = 6
col_num = 6
adjacency_matrix = []
for i in range(row_num):
row = []
for j in range(col_num):
row.append(0)
adjacency_matrix.append(row)
edges = [(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
for edge in edges:
row = edge[0]
col = edge[1]
adjacency_matrix[row - 1][col - 1] = 1
adjacency_matrix[col - 1][row - 1] = 1
print("The edges in the graph are:")
print(edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)
Ausgang:
The edges in the graph are:
[(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
The adjacency matrix is:
[[0, 1, 0, 0, 0, 0],
[1, 0, 1, 1, 0, 0],
[0, 1, 0, 1, 0, 1],
[0, 1, 1, 0, 1, 0],
[0, 0, 0, 1, 0, 1],
[0, 0, 1, 0, 1, 0]]
Im Code können Sie beobachten, dass wir eine 0-basierte Indizierung haben. Aus diesem Grund wird jeder Knoten (i,j) durch die Position (i-1,j-1) in der Adjazenzmatrix dargestellt.
Um eine Adjazenzmatrix für einen gewichteten Graphen zu erstellen, erstellen wir zuerst eine zweidimensionale n x n-Liste mit Nullen. Danach weisen wir das Gewicht der Kante eij an der Position (i,j) in der Matrix zu.
Dies können Sie im folgenden Beispiel beobachten.
import pprint
row_num = 6
col_num = 6
adjacency_matrix = []
for i in range(row_num):
row = []
for j in range(col_num):
row.append(0)
adjacency_matrix.append(row)
weighted_edges = [
(1, 2, 5),
(2, 4, 12),
(2, 3, 1),
(3, 4, 8),
(4, 5, 7),
(3, 6, 4),
(5, 6, 2),
]
for edge in weighted_edges:
row = edge[0]
col = edge[1]
weight = edge[2]
adjacency_matrix[row - 1][col - 1] = weight
adjacency_matrix[col - 1][row - 1] = weight
print("The edges in the graph are:")
print(weighted_edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)
Ausgang:
The edges in the graph are:
[(1, 2, 5), (2, 4, 12), (2, 3, 1), (3, 4, 8), (4, 5, 7), (3, 6, 4), (5, 6, 2)]
The adjacency matrix is:
[[0, 5, 0, 0, 0, 0],
[5, 0, 1, 12, 0, 0],
[0, 1, 0, 8, 0, 4],
[0, 12, 8, 0, 7, 0],
[0, 0, 0, 7, 0, 2],
[0, 0, 4, 0, 2, 0]]
Im obigen Code wurden die Kanten mit einem Zahlentripel dargestellt. Die ersten 2 Zahlen stellen die Knoten des Graphen dar, die durch die Kante verbunden sind.
Die dritte Zahl repräsentiert das Gewicht der Kante.
Erstellen Sie eine Adjazenzmatrix in Python mit dem NumPy-Modul
Um mit dem NumPy-Modul eine Adjazenzmatrix für einen Graphen zu erstellen, können wir die Methode np.zeros() verwenden.
Die Methode np.zeros() nimmt ein Tupel in Form von (row_num,col_num) als Eingabeargument und gibt eine zweidimensionale Matrix der Form row_num x col_num zurück. Hier sind row_num und col_num die Anzahl der Zeilen und Spalten in der Matrix.
Wir werden die folgenden Schritte verwenden, um eine Adjazenzmatrix mit der Methode np.zeros() zu erstellen.
-
Zuerst erstellen wir eine Matrix der Größe
n x n, indem wir ein Tupel(n,n)an die Methodezeros()übergeben. -
Dann werden wir die Werte an der Position
(i-1,j-1)für jede Kante eij im Diagramm auf 1 aktualisieren; hier verwenden wir eine 0-basierte Indizierung. Aus diesem Grund wird der Knoten(i,j)durch die Position(i-1,j-1)im Code dargestellt.
Nachdem Sie die obigen Schritte ausgeführt haben, erhalten wir die Adjazenzmatrix, wie im folgenden Beispiel gezeigt.
import pprint
import numpy as np
row_num = 6
col_num = 6
adjacency_matrix = np.zeros((row_num, col_num), dtype=int)
edges = [(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
for edge in edges:
row = edge[0]
col = edge[1]
adjacency_matrix[row - 1][col - 1] = 1
adjacency_matrix[col - 1][row - 1] = 1
print("The edges in the graph are:")
print(edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)
Ausgang:
The edges in the graph are:
[(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
The adjacency matrix is:
array([[0, 1, 0, 0, 0, 0],
[1, 0, 1, 1, 0, 0],
[0, 1, 0, 1, 0, 1],
[0, 1, 1, 0, 1, 0],
[0, 0, 0, 1, 0, 1],
[0, 0, 1, 0, 1, 0]])
Um die Adjazenzmatrix für die gewichteten Graphen zu erstellen, aktualisieren wir die Werte an der Position (i,j) auf das Gewicht der Kante eij, wie unten gezeigt.
import pprint
import numpy as np
row_num = 6
col_num = 6
adjacency_matrix = np.zeros((row_num, col_num), dtype=int)
weighted_edges = [
(1, 2, 5),
(2, 4, 12),
(2, 3, 1),
(3, 4, 8),
(4, 5, 7),
(3, 6, 4),
(5, 6, 2),
]
for edge in weighted_edges:
row = edge[0]
col = edge[1]
weight = edge[2]
adjacency_matrix[row - 1][col - 1] = weight
adjacency_matrix[col - 1][row - 1] = weight
print("The edges in the graph are:")
print(weighted_edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)
Ausgang:
The edges in the graph are:
[(1, 2, 5), (2, 4, 12), (2, 3, 1), (3, 4, 8), (4, 5, 7), (3, 6, 4), (5, 6, 2)]
The adjacency matrix is:
array([[ 0, 5, 0, 0, 0, 0],
[ 5, 0, 1, 12, 0, 0],
[ 0, 1, 0, 8, 0, 4],
[ 0, 12, 8, 0, 7, 0],
[ 0, 0, 0, 7, 0, 2],
[ 0, 0, 4, 0, 2, 0]])
Abschluss
In diesem Artikel werden zwei Möglichkeiten zum Implementieren einer Adjazenzmatrix in Python beschrieben. Wir empfehlen Ihnen, eine Adjazenzmatrix mit dem NumPy-Modul zu implementieren, da es in Bezug auf die Speicheranforderungen viel effizienter ist.
Außerdem ist das Ausführen verschiedener Operationen auf einem NumPy-Array in Bezug auf Zeit- und Speicheranforderungen viel effizienter.
Aditya Raj is a highly skilled technical professional with a background in IT and business, holding an Integrated B.Tech (IT) and MBA (IT) from the Indian Institute of Information Technology Allahabad. With a solid foundation in data analytics, programming languages (C, Java, Python), and software environments, Aditya has excelled in various roles. He has significant experience as a Technical Content Writer for Python on multiple platforms and has interned in data analytics at Apollo Clinics. His projects demonstrate a keen interest in cutting-edge technology and problem-solving, showcasing his proficiency in areas like data mining and software development. Aditya's achievements include securing a top position in a project demonstration competition and gaining certifications in Python, SQL, and digital marketing fundamentals.
GitHub