그래프 (이산수학)
- 수학적 정의 및 자세한 설명은 참조
그래프 (자료구조)
- 자료구조로써 그래프를 구현하는 방법은 2가지가 있다
- 인접 행렬
- 인접 리스트
1. 인접 행렬 (Adjacency Matrix)
- vertex의 수를 N이라 했을 때, N x N 행렬을 정의
- 인접(adjacent)하는 경우 1, 그렇지 않은 경우 0으로 설정
- edge에 가중치가 있는 weighted graph일 경우 가중치 입력
- 공간복잡도 O(N^2)
- undirected graph일 경우 공간 반으로 safe 가능?
- in python : N x N 리스트로 구현
2. 인접 리스트 (Adjacency List)
- 각 vertex 마다 인접하는 vertex들을 담는 리스트를 가짐
- 공간복잡도
- directed : O(v + e)
- undirected : O(v + 2e)
- in python : 그림은 linked list 같지만 dictionary list로 구현 가능
undirected_graph = {
1 : [2, 4],
2 : [1, 4],
3 : [4],
4 : [1, 2, 3]
}
directed_graph = {
1 : [2, 3],
2 : [],
3 : [2]
}
directed_weighted_graph = {
1 : [(2, 1), (3, 4)],
2 : [],
3 : [(2, 2)]
} # (vertex, weight) 형식으로 표현?이미지 출처
hi