📌 Graph
그래프는 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료구조이다.
- 정점 (Vertex) : 그래프 구성요소로 하나의 연결점
- 간선 (Edge) : 두 정점을 연결하는 선
- 차수 (Degree) : 정점에 연결된 간선의 수
간선의 수
V : 정점의 개수
- 무향 그래프 간선 수 = 최대 V * (V-1) / 2
- 유향 그래프 간선 수 = 최대 V * (V-1)
그래프 표현
- 인접 행렬
- 인접 리스트
- 간선 리스트
- 간선의 정보를 저장하는 방식, 메모리 성능을 고려해 결정해야 한다.
밀집 그래프 vs 희소 그래프
밀집 그래프
- 정점 개수에 대해 간선 개수가 많다.
- 인접 행렬 사용
희소 그래프
- 정점 개수에 대해 간선 개수가 적다.
- 인접 리스트 사용
인접 행렬
- 두 정점을 연결하는 간선의 유무를 행렬로 표현한 것이다.
- 2차원 배열의 V x V의 정방 행렬
- 행 인덱스와 열 인덱스는 그래프 정점에 대응된다.
- 두 정점이 인접하면
인접행렬[V][V] = true로 표현한다. - 가중치가 있을 경우엔 인접 값을 true가 아닌 가중치를 넣는다.
인접 리스트
- 각 정점에 대한 인접 정점들을 순차적으로 표현한 것이다.
- 하나의 정점에 대한 이접 정점들을 각각 노드로 하는 연결 리스트로 저장한 것이다.
간선 리스트
- 두 정점에 대한 간선 그 자체를 객체로 표현하여 리스트로 저장한 것이다.
