그래프 구현

Created At

2022/02/03 02:35

Updated At

2022/03/13 17:08

분류

자료구조

그래프

•

방향여부 : 무향그래프(양방향) vs 유향그래프(단방향)

•

가중치여부 : 비가중치그래프 vs 가중치그래프

파이썬에 그래프 구현 방법

n*n 배열(인접행렬)

딕셔너리 or 배열(인접리스트)

이 문제는 가중치 단방향그래프이다.

Code

인접행렬

n, m = map(int, input().split())
graph = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    i, j, w = map(int, input().split()) # 시작,도착,가중치
    graph[i][j] = w

for i in range(1, n + 1):
    for j in range(1, n + 1):
        print(graph[i][j], end=" ")
    print()

"""
6 9
1 2 7
1 3 4
2 1 2
2 3 5
2 5 5
3 4 5
4 2 2
4 5 5
6 4 5
"""

0 7 4 0 0 0 
2 0 5 0 5 0 
0 0 0 5 0 0 
0 2 0 0 5 0 
0 0 0 0 0 0 
0 0 0 5 0 0
Python
복사

인접리스트(배열)

# 인접리스트 방식 (배열사용)

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    i, j, w = map(int, input().split())
    graph[i].append((j, w))  # (j,w) == (도착노드, 가중치)

for i in range(len(graph)):
    print(f"{i} : {graph[i]}")

"""
6 9
1 2 7
1 3 4
2 1 2
2 3 5
2 5 5
3 4 5
4 2 2
4 5 5
6 4 5
"""

0 : []
1 : [(2, 7), (3, 4)]
2 : [(1, 2), (3, 5), (5, 5)]
3 : [(4, 5)]
4 : [(2, 2), (5, 5)]
5 : []
6 : [(4, 5)]
Python
복사

인접리스트(딕셔너리)

제일 좋은 방식

# 인접리스트 방식 (딕셔너리사용)

n, m = map(int, input().split())
graph = {}

# 노드값으로 딕셔너리에 key 생성
for i in range(1, n + 1): # 1번노드부터 n번까지로 해야하므로 
    graph[i] = []

# 그래프 생성
for _ in range(m):
    i, j, w = map(int, input().split())
		graph[i].append((j, w))  # i : 시작노드, j : 도착노드, w : 가중치
    # graph[i] += [(j, w)]  # 똑같은 코드

for i in graph.keys():
    print(f"{i} : {graph[i]}")

"""
6 9
1 2 7
1 3 4
2 1 2
2 3 5
2 5 5
3 4 5
4 2 2
4 5 5
6 4 5
"""

1 : [(2, 7), (3, 4)]
2 : [(1, 2), (3, 5), (5, 5)]
3 : [(4, 5)]
4 : [(2, 2), (5, 5)]
5 : []
6 : [(4, 5)]
Python
복사

이 방식이 제일 좋은 이유는 인접노드가 없는 노드도 생성을 해준다. (5번노드)

비추천

# 인접리스트 방식 2 (딕셔너리사용)

n, m = map(int, input().split())
graph = {}
for _ in range(m):
    i, j, w = map(int, input().split())
    graph[i] = graph.get(i, []) + [(j, w)]  # append((j,w)) 로 하면 안됨! append 의 리턴은 None 이므로
		# (j,w) == (도착노드, 가중치)

for i in graph.keys():
    print(f"{i} : {graph[i]}")

"""
6 9
1 2 7
1 3 4
2 1 2
2 3 5
2 5 5
3 4 5
4 2 2
4 5 5
6 4 5
"""

1 : [(2, 7), (3, 4)]
2 : [(1, 2), (3, 5), (5, 5)]
3 : [(4, 5)]
4 : [(2, 2), (5, 5)]
6 : [(4, 5)]
Python
복사

똑같이 딕셔너리로 구현을 했지만 get() 함수를 써야하고, 인접노드가 없는 노드 (5번노드) 는 아예 생성이 안된 것을 볼 수 있다. 간혹 이것때문에 예외처리를 해줘야할 때가 있어서 그냥 1번 딕셔너리 방식이 더 편하다.