코딩 테스트/개념
그래프
ornni
2024. 7. 21. 10:00
728x90
반응형
그래프: 노드와 에지로 구성된 집합
- 노드: 데이터를 표현하는 단위
- 에지: 노드 연결
ex) 그래프가 아래와 같다고 하자!!
그래프 생성 방법 1. 에지 리스트 (edge list)
에지를 중심으로 그래프 표현
| 출발노드 | 도착노드 | (가중치) |
| 1 | 2 | 7 |
| 1 | 3 | 5 |
| 2 | 4 | 18 |
| 3 | 4 | 9 |
| 3 | 5 | 14 |
| 4 | 5 | 3 |
그래프 생성 방법 2. 인접 행렬 (adjacency matrix)
노드를 중심으로 그래프 표현
가중치가 없는 경우 모두 1로 표현
| 도착노드 | ||||||
| 출발노드 | index | 1 | 2 | 3 | 4 | 5 |
| 1 | 7 | 5 | ||||
| 2 | 18 | |||||
| 3 | 9 | 14 | ||||
| 4 | 3 | |||||
| 5 | ||||||
그래프 생성 방법 3. 인접 리스트 (adjacency list)
가중치가 없는 경우 ()없이 표현
| List | ||
| 1 | > | (2, 7), (3, 5) |
| 2 | > | (4, 18) |
| 3 | > | (4, 9), (5, 14) |
| 4 | > | (5, 3) |
| 5 | > | |
반응형