[Python] Erstellen einer Adjazenzmatrix / Adjazenzliste [Graphentheorie]

Einführung

Bei der Wettbewerbsprogrammierung ist die Wand, die früher oder später trifft, die "Graphentheorie". Es handelt sich um ein Problem im Zusammenhang mit der (?) Graphentheorie, das mit der Suche nach Breitenpriorität und der Suche nach Tiefenpriorität beginnt und eine unendliche Ausdehnung aufweist. Diesmal wird jedoch in Python "Adjazenzmatrix" und "Adjazenzliste" erstellt Ich fasste zusammen. Es wird von Zeit zu Zeit aktualisiert ...

Benachbarte Matrix und Adjazenzliste

Betrachten Sie beispielsweise das folgende Diagramm.

Es gibt zwei Haupttypen von Diagrammdatenstrukturen auf einem Computer. Verwenden wir es je nach Situation richtig. Eine ist die "benachbarte Matrix", die die Form einer $ n \ times n $ -Matrix hat. Obwohl es viel Speicher benötigt, hat es den Vorteil, feststellen zu können, ob es in einer festgelegten Zeit eine bestimmte Kante gibt oder nicht.

adj_m.txt

[[0, 1, 1, 0, 1],
 [1, 0, 1, 1, 0],
 [1, 1, 0, 1, 1],
 [0, 0, 1, 1, 1],
 [1, 0, 1, 1, 0]]

Die andere ist die "benachbarte Liste". Obwohl weniger Speicher benötigt wird, hat es den Nachteil, dass im schlimmsten Fall $ O (V) $ benötigt wird, um festzustellen, ob eine bestimmte Kante vorhanden ist.

adj_l.txt

[[2, 3, 5], [1, 3, 4], [1, 2, 4, 5], [2, 3, 5], [1, 3, 4]]

Das eigentliche Problem besteht darin, dass Sie zwei Endpunkte der Seiten erhalten, z. B. AtCoder Beginners Contest 168 D .. (Double Dots). Es gibt viele.

Wenn ich versuche, die Eingabe für dieses Diagramm auszudrücken, sieht es wie folgt aus. (Die Anzahl der Eckpunkte n und die Anzahl der Seiten m werden in die erste Zeile eingegeben.)

input.txt

5 8
1 2
1 3
1 5
2 3
2 4
3 4
3 5
4 5

Code

Ich werde einen Spickzettel schreiben, der diese in Adjazenzmatrizen und Adjazenzlisten umwandelt.

Eingabe in benachbarte Matrix

Wenn es kein Gewicht gibt

input_to_adj_m.py

n, m = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(m)]

l = [[0]*n for i in range(n)]
for v in p:
    l[v[0]-1][v[1]-1] = 1
    l[v[1]-1][v[0]-1] = 1  #Löschen, wenn es sich um einen gerichteten Graphen handelt

print(l)  # [[0, 1, 1, 0, 1], ..., [1, 0, 1, 1, 0]]

Wenn es Gewicht gibt, ändert es sich leicht.

input_to_adj_m.py

n, m = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(m)]

graph = [[0]*n for _ in range(n)]
for v in p:
    graph[v[0]-1][v[1]-1] = v[2]  #Hier ändert sich
    graph[v[1]-1][v[0]-1] = v[2]  #Löschen, wenn es sich um einen gerichteten Graphen handelt

print(graph)  # [[0, 1, 1, 0, 1], ..., [1, 0, 1, 0, 0]]

Eingabe in benachbarte Liste

input_to_adj_l.py

n, m = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(m)]

graph = [[] for _ in range(n)]
for v in p:
    graph[v[0]-1].append(v[1])
    graph[v[1]-1].append(v[0])  #Löschen, wenn es sich um einen gerichteten Graphen handelt

print(graph)  # [[2, 3, 5], ..., [1, 3, 4]]

abschließend

Danke fürs Lesen. Ich wäre Ihnen dankbar, wenn Sie mir mitteilen könnten, ob Fehler oder Tippfehler vorliegen.