[2주차] 그래프 연결 관계 표현(인접 행렬/ 인접 리스트)

프로그래밍에서 그래프는 크게 2가지 방식으로 표현가능

1) 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현하는 방식

2) 인접 리스트(Adjacency List): 리스트로 연결관계를 표현하는 방식

 

인접 행렬 방식

각 노드에 연결된 형태를 기록하는 방식

연결되지 않는 노드끼리는 무한(Infinity)의 비용으로 설정

(논리적으로 정답이 될 수 없는 값들을 넣는다. 9876543221 이렇게 넣기도...)

인접 행렬 방식 예제 그림 (출처: https://www.includehelp.com/ds/addition-and-deletion-of-nodes-and-edges-in-a-graph-using-adjacency-matrix.aspx)

inf = 987654321	# 무한의 비용 선언

graph = {
	[0, 2, 3, Inf, Inf]
    	[2, 0, 15, 2, Inf]
    	[3, 15, 0, Inf, 13]
        [Inf, 2, Inf, 0, 9]
        [Inf, Inf, 13, 9, 0]
}

어쩔 수없이,

1) 대각행렬은 0

2) graph[i][j] = graph[j][i] (대각 행렬 기준으로 접었을 때, 데칼코마니 형태가 된다.)

 

인접 행렬 방식에 비해, 

단점) 모든 관계를 저장하므로, 노드의 개수가 많을 수록 메모리가 불필요하게 낭비된다.

장점) 특정한 두 노드가 연결되어 있는지에 대한 정보를 빠르게 얻을 수 있다.

 

인접 리스트 방식

연결된 노드에 대한 정보를 차례대로 연결하여 저장

인접 리스트(출처: https://www.lavivienpost.com/implement-weighted-graph-as-adjacency-list/)

# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(4)]

# 노드 1에 연결된 노드 정보 저장(노드, 거리)
graph[1].append((2, 5))
graph[1].append((3, 6))

# 노드 2에 연결된 노드 정보 저장(노드, 거리)
graph[2].append((1, 5))
graph[2].append((3, 3))

# 노드 3에 연결된 노드 정보 저장(노드, 거리)
graph[3].append((1, 6))
graph[3].append((2, 3))
graph[3].append((4, 2))

# 노드 4에 연결된 노드 정보 저장(노드, 거리)
graph[4].append((3, 2))

인접 행렬에 비해,

장점) 연결된 정보만 저장하기 때문에, 메모리를 효율적으로 사용한다.

단점) 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다.

 

참조)

이것이 코딩테스트다 with 파이썬 -나동빈님