[Python] Comment créer une matrice de contiguïté / liste de contiguïté [Théorie des graphes]

introduction

Lors de la programmation compétitive, le mur qui frappe tôt ou tard est la «théorie des graphes». C'est un problème lié à (?) La théorie des graphes qui commence par la recherche de priorité de largeur et la recherche de priorité de profondeur et a une étendue infinie, mais cette fois comment créer une "matrice d'adjacence" et une "liste d'adjacence" en Python J'ai résumé sur. Il sera mis à jour de temps en temps ...

Matrice adjacente et liste de contiguïté

Par exemple, considérons le graphique suivant.

Il existe deux principaux types de structures de données graphiques sur un ordinateur. Utilisons-le correctement en fonction de la situation. L'une est la «matrice adjacente», qui se présente sous la forme d'une matrice $ n \ times n $. Bien qu'il utilise beaucoup de mémoire, il a l'avantage de pouvoir déterminer s'il y a ou non un front spécifique dans un temps fixe.

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]]

L'autre est la «liste adjacente». Bien qu'il utilise moins de mémoire, il a l'inconvénient qu'il faut au pire $ O (V) $ pour déterminer s'il existe un bord spécifique.

adj_l.txt

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

Le problème réel est que l'on vous donne «deux extrémités des côtés», comme AtCoder Beginners Contest 168 D .. (Double Dots). Il y a beaucoup de.

Lorsque j'essaie d'exprimer l'entrée de ce graphique, cela devient comme suit. (Le nombre de sommets n et le nombre de côtés m sont entrés dans la première ligne)

input.txt

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

code

J'écrirai une feuille de triche qui les convertit en matrices de contiguïté et listes de contiguïté.

Entrée dans la matrice adjacente

Quand il n'y a pas de poids

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  #Effacer s'il s'agit d'un graphe orienté

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

S'il y a du poids, cela changera légèrement.

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]  #Ici change
    graph[v[1]-1][v[0]-1] = v[2]  #Effacer s'il s'agit d'un graphe orienté

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

Entrée dans la liste adjacente

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])  #Effacer s'il s'agit d'un graphe orienté

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

en conclusion

Merci pour la lecture. Je vous serais reconnaissant de bien vouloir me faire savoir s'il y a des erreurs ou des erreurs typographiques.