수리링의 데이터교실

# infinite 값을 선언하기
INF = float('inf')

# 행렬 그래프로 나타내기 - 가중치 weight 고려해서 표현
graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

graph[0][1]
>>> 7 (0번과 1번 도시가 연결됨)

graph[2][1]
>>> inf (2번과 1번 도시가 연결 안 됨)

# 연결된 도시만 리스트로 표현

graph = [
    [(1, 7), (2, 5)], # --> 0번 도시의 연결 리스트업
    [(0, 7)], # --> 1번 도시의 연결 리스트업
    [(0, 5)]  # --> 2번 도시의 연결 리스트업
]

graph[0][0][1]
>>> 7

# 행렬보다 직관성은 떨어질 수 있다.

graph_dict = {
    "0" : [("1", 7), ("2", 5)],
    "1" : [("0", 7)],
    "2" : [("0", 5)],
}

graph = [
    [], # --> 0번 도시는 비워두고 시작
    [(1, 7), (2, 5)], # --> 1번 도시부터 기록
    [(0, 7)],
    [(0, 5)] 
]

[메모리]

인접 행렬(Adjacency Matrix): 모든 관계를 저장하므로 노드 개수가 많을 수록 불필요한 메모리가 소요된다.

인접 리스트(Adjacency List): 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다.

출처 입력

[속도]

인접 행렬(Adjacency Matrix): 모든 경우의 수가 제시되어 있으므로 인접리스트보다 빠르다.

인접 리스트(Adjacency List): 인접행렬방식에 비해 정보를 얻는 속도가 느리다. 인접리스트방식에서는 연결된 데이터를 하나씩 확인해야 하기 때문이다.

출처 입력