[python] 파이썬 인접행렬, 인접리스트 구현(PS 를 위한)

파이썬으로 그래프 문제를 풀 때 아직 익숙하지 않아서 계속 헷갈려서 이 글에서 정리를 한다.

인접리스트

인접리스트는 정점의 개수가 많은데에 비해 간선의 개수가 적을 때 유용하다.

6 10 # 노드수 간선 수

0 1 # 출발노드 도착노드
0 2
0 3
1 2
1 3
1 4
3 5
4 3
4 5

# 인접리스트의 구현
node, edge = map(int, input().split())

graph = [[] for i in range(node)]

for _ in range(edge):
    startNode, endNode = map(int, input().split())
    graph[startNode].append(endNode)
    graph[endNode].append(startNode)

위의 소스코드는 무방향그래프(양방향그래프)일 경우를 산정하고 만든 그래프이다.

 

인접행렬

인접행렬은 정점수에 비해 간선의 수가 많을 때 유리하다.

6 10 # 노드수 간선 수

0 1 # 출발노드 도착노드
0 2
0 3
1 2
1 3
1 4
3 5
4 3
4 5

# 인접행렬의 구현
node, edge = map(int, input().split())

graph = [[] for j in range(node) for i in range(node)]

for _ in range(edge):
    startNode, endNode = map(int, input().split())
    graph[startNode][endNode] = 1
    graph[endNode][startNode] = 1

# 인접행렬에서 n행 m열의 정보가 주어지는 경우
row, column, edge = map(int, input().split())

graph = [[] for j in range(column) for i in range(row)]

for _ in range(edge):
    startNode, endNode = map(int, input().split())
    graph[startNode][endNode] = 1
    graph[endNode][startNode] = 1

위의 소스코드는 무방향그래프(양방향그래프)일 경우를 산정하고 만든 그래프이다.