Graph
- 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조
- 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조이다.
- 예시) 지도, 지하철 노선도의 최단 경로
Graph 종류
1. 방향 그래프
- In-degree : 다른 버텍스에서부터 오는 아크의 개수
- Out-degree : 다른 버텍스로 가는 아크의 개수
2. 무방향 그래프
- Degree : 양쪽으로 모두 연결되어 있는 아크의 개수
Graph를 코드로 표현하는 방법
1. 이차원 배열
공간을 많이 차지하지만 간단하다.
2. 연결 리스트
공간은 적게 차지하지만 복잡하다.