08-1 그래프의 표현
- 그래프를 구현하는 3가지 방법에 대해 알아보자.
[2차원 리스트 생성]
- 0으로 초기화한 행(row) 개수 3, 열(column) 개수 4인 2차원 리스트를 생성하는 방법
- 리스트 객체 생성 방법 추천
A = [[0 for col in range(4)] for row in range(3)]에지 리스트
- 에지 리스트는 에지를 중심으로 그래프를 표현한다. 에지 리스트는 리스트에 출발 노드, 도착 노드를 저장하여 에지를 표현한다. 또는, 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현한다.
- [1, 2]는 1에서 2로 뻗어나가는 에지이다.
- [1, 2, 8]은 1에서 2로 향하는 가중치가 8인 에지이다.
- 최단 거리 구하는 벨만-포드, 최소 신장 트리를 찾는 크루스칼 알고리즘에서 사용한다.
- 노드 중심 알고리즘에서는 잘 사용하지 않는다.
인접 행렬
- 인접 행렬은 2차원 리스트를 자료구조로 이용해 표현한다.
- 에지 리스트와 다르게 노드 중심으로 그래프를 표현한다
- 1행 2열에 1 저장: 1에서 2로 향하는 에지를 표현한다. (1을 저장하는 것은 가중치가 없다는 것이다.)
- 2행 5열에 15 저장: 2에서 5로 향하며 가중치가 15인 에지를 표현한다.
- 에지와 가중치 값은 리스트에 직접 접근하면 바로 확인할 수 있는 것이 장점이다.
- 하지만 에지 탐색하려면 N번 접근해야 하므로 시간 복잡도가 인접 리스트에 비해 느리고 공간 효율성이 떨어진다.
인접 리스트 선호
- 인접 리스트는 파이썬의 리스트를 이용하여 그래프를 표현한다.
- 노드 개수만큼 리스트를 선언한다.
- 리스트의 input data 형태는 문제의 조건에 맞게 설정한다.
A = [[] for _ in range(N+1)][인접 리스트로 가중치 없는 그래프 표현하기]
1 -> 2 | 3
2 -> 4 | 5
3 -> 4
4 -> 5
5
[인접 리스트로 가중치 있는 그래프 표현하기]
- input data: (도착 노드, 가중치)
1 -> 2, 8 | 3, 3
2 -> 4, 4 | 5, 15
3 -> 4, 13
4 -> 5, 2
5
탐색하는 시간은 매우 뛰어나며, 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않는다. 실제 코딩 테스트에서는 인접 리스트를 이용한 그래프 구현을 선호한다. 그래프 구현과 함께 DFS, BFS를 복슴하며 그래프 구현에 익숙해지자.
안녕하세요 :)