그래프의 표현 및 비교 (간선 리스트, 인접 행렬, 인접 리스트)

 

	간선 리스트	인접 행렬	인접 리스트
중심	간선	노드	노드
시간복잡도	-	느림	빠름
구조	[]	d[시작노드][종료노드]	d[시작노드]
입력	(시작노드 ,도착노드, 가중치)	가중치	(도착노드, 가중치)
알고리즘	벨만-포드 MST 크루스칼	플로이드-워셜	다익스트라

 

---

간선 리스트

• Edge list
• 에지 중심으로 그래프를 표현
• 리스트에 출발 노드, 도착 노드, 가중치 저장하여 가중치가 있는 에지 표현
• 벨만-포드, 최소 신장 트리 크루스칼 알고리즘

# 벨만 포드
graph = []
for i in range(m):
    u, v, w = map(int, input().split())
    graph.append((u, v, w))

# 크루스칼
from queue import PriorityQueue

q = PriorityQueue()
for _ in range(E):
    a, b, w = map(int, input().split())
    q.put((w, a, b))

 

인접 행렬

• Adjacency matrix
• 2차원 리스트를 자료구조로 이용
• 노드중심으로 그래프 표현
• 두 노드를 연결하는 에지의 여부와 가중치 값은 리스트에 직접 접근하면 바로 확인할 수 있음
• 노드와 관련되어 있는 에지를 탐색하려면 N번 접근해야 하므로 시간 복잡도가 느리고 고간 효율성 떨어짐
• 플로이드 워셜 알고리즘

d = [[sys.maxsize for j in range(n+1)] for i in range(n+1)]

for i in range(1, n+1):
    d[i][i] = 0

for i in range(m):
    a, b, w = map(int, input().split())
    if d[a][b] > w:
        d[a][b] = w

 

인접 리스트

• Adjacency list
• 리스트를 이용하여 그래프 표현
• N번 노드와 연결되어 있느 노드를 리스트의 index N에 연결된 노드 개수만큼 리스트에 append
• input data를 2개(도착노드, 가중치)로 사용
• 노드와 연결된 에지를 탐색하는 시간은 매우 뛰어나며, 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않음
• 다익스트라 알고리즘

graph = [[] for _ in range(v+1)]

for i in range(e):
    u, v, w = map(int, input().split())
    graph[u].append((v,w))