Adjazenzmatrix – Darstellung von Graphen
Ein Graph ist eine Struktur aus Knoten (Vertices) und Kanten (Edges), die diese Knoten miteinander verbinden. Graphen können verwendet werden, um Beziehungen zwischen Objekten oder ein Netzwerk darzustellen. Oft nutzt man sie, um Verbindungen zwischen Städten, Personen oder sogar abstrakten Entitäten abzubilden.
Graphen können gerichtet oder ungerichtet sein:
- Gerichtete Graphen: Alle Kanten besitzen eine Richtung, d. h. es gibt eine „Straße“ von einem Knoten zum anderen, aber nicht unbedingt in die entgegengesetzte Richtung – vergleichbar mit einer Einbahnstraße. Trotzdem kann es in einem gerichteten Graphen beide Richtungen geben. Sie sind dann jeweils explizit markiert (wie die Verbindung zwischen den Knoten 5 und 8 im Graphen).
Yet, it’s possible to have both directions in a directed graph. They are just explicitly marked for that (the connection between vertices 5 and 8 in the graph).
- Ungerichtete Graphen: Die Kanten besitzen keine Richtung. Das bedeutet, wenn zwei Knoten verbunden sind, gilt dies in beide Richtungen.
Eine Möglichkeit, einen Graphen darzustellen, ist die sogenannte Adjazenzmatrix. Dabei handelt es sich um eine quadratische Matrix, die den gesamten Graphen beschreibt. Jede Zeile und Spalte der Matrix repräsentiert einen Knoten des Graphen. Besteht eine Kante zwischen zwei Knoten, so ist der entsprechende Eintrag in der Matrix auf 1 gesetzt. Ansonsten bleibt er 0.
Eine mögliche Adjazenzmatrix für den oben abgebildeten gerichteten Graphen könnte folgendermaßen aussehen:
g = [
# 1 2 3 4 5 6 7 8
[0, 1, 0, 1, 0, 0, 0, 0], # ausgehende Verbindungen von Knoten 1
[0, 0, 0, 0, 1, 0, 0, 0], # ausgehende Verbindungen von Knoten 2
[0, 1, 0, 0, 0, 0, 0, 0], # ausgehende Verbindungen von Knoten 3
[0, 0, 0, 0, 0, 0, 0, 0], # ausgehende Verbindungen von Knoten 4
[0, 0, 0, 0, 0, 1, 0, 1], # ausgehende Verbindungen von Knoten 5
[0, 0, 0, 1, 0, 0, 1, 0], # ausgehende Verbindungen von Knoten 6
[0, 0, 0, 0, 0, 0, 0, 1], # ausgehende Verbindungen von Knoten 7
[0, 0, 0, 0, 1, 0, 0, 0], # ausgehende Verbindungen von Knoten 8
]Beachten Sie, dass für eine bidirektionale Kante in beiden Richtungen jeweils eine 1 gesetzt wird.
Außerdem sehen Sie, dass wir die Indizes etwas verändert haben. Greift man beispielsweise auf
g[0] zu, erhält man alle Verbindungen des Knotens mit Index 1. Man könnte auch 9 Zeilen und 9 Spalten nutzen, um eine direkte Entsprechung zur Abbildung herzustellen – das bleibt Ihnen überlassen 😎.Herausforderung: Kanten zur Adjazenzmatrix
Gegeben ist ein Graph mit
v Knoten und e Kanten. Ihre Aufgabe ist es, die Adjazenzmatrix dieses Graphen zu erzeugen.Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
v (1 ≤ v ≤ 1000) und e (1 ≤ e ≤ 100 000).Die folgenden
e Zeilen enthalten jeweils ein Paar aus zwei ganzen Zahlen v1, v2 (1 ≤ v1, v2 ≤ v). Dieses Paar bedeutet, dass der Knoten v1 mit dem Knoten v2 und umgekehrt verbunden ist.Ausgabe
Das Programm soll die Adjazenzmatrix des Graphen ausgeben. Die Werte jeder Zeile sollen durch ein Leerzeichen getrennt sein.
Beispiele
Input | Output |
8 9
1 4
4 6
3 2
2 1
5 2
5 6
8 5
7 6
7 8 | 0 1 0 1 0 0 0 0
1 0 1 0 1 0 0 0
0 1 0 0 0 0 0 0
1 0 0 0 0 1 0 0
0 1 0 0 0 1 0 1
0 0 0 1 1 0 1 0
0 0 0 0 0 1 0 1
0 0 0 0 1 0 1 0 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 5 MB