[Python] How to make an adjacency matrix / adjacency list [Graph theory]

Introduction

When you're doing competitive programming, the wall you hit sooner or later is "graph theory." It is a problem related to (?) Graph theory that starts with breadth-first search and depth-first search and has infinite extent, but this time how to create "adjacency matrix" and "adjacency list" in Python I summarized about. It will be updated from time to time ...

Adjacency matrix and adjacency list

For example, consider the following graph.

There are two main types of graph data structures on a computer. Let's use it properly according to the situation. One is the adjacency matrix, which is in the form of a $ n \ times n $ matrix. It uses a lot of memory, but it has the advantage of being able to determine if there is a specific edge in a constant time.

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

The other is the adjacency list. Although it uses less memory, it has the disadvantage that it takes $ O (V) $ at worst to determine if there is a particular edge.

adj_l.txt

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

The actual problem is that you are given a two endpoints of an edge, such as AtCoder Beginners Contest 168 D .. (Double Dots). There are many.

When I try to express the input for this graph, it becomes as follows. (The number of vertices n and the number of sides m are entered in the first line)

input.txt

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

code

I will write a cheat sheet that converts these into adjacency matrices and adjacency lists.

Input to adjacency matrix

When there is no weight

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  #Erase if it is a directed graph

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

If there is weight, it will change slightly.

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]  #Here is changing
    graph[v[1]-1][v[0]-1] = v[2]  #Erase if it is a directed graph

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

Input to adjacency list

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])  #Erase if it is a directed graph

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

in conclusion

Thank you for reading. I would be grateful if you could let me know if there are any mistakes or typographical errors.