그래프와 구현 방법

그래프 ?

• 아래와 같은 자료구조를 그래프라고 한다.

• 대표적인 구현 방식으로 3가지가 있다.
  • 엣지 리스트
  • 인접 행렬
  • 인접 리스트

엣지 리스트

• 이름에서 알 수 있듯이 엣지(Edge; 간선)를 중심으로 그래프를 표현한다. → 즉 그래프의 모든 간선을 리스트 형태로 저장한다 !
  • 가중치 X → 두 정점(출발지, 도착지)
  • 가중치 O → 두 정점(출발지, 도착지), 가중치

List<Edge> edgeList = new ArrayList<>();
edgeList.add(new Edge(1, 2, 5)); // 간선 (1 -> 2), 가중치 5
edgeList.add(new Edge(2, 3, 3)); // 간선 (2 -> 3), 가중치 3

• 장점

  1. 간선의 개수가 적을 때 메모리를 절약할 수 있다 !
  2. 구현이 간단하고, 특정 알고리즘(ex: 크루스칼 MST(최소 신장트리))에 적합하다.

• 단점

  1. 특정 정점과 관련된 간선을 찾으려면 모든 간선을 탐색해야 하므로 비효율적이다 !

인접 행렬