- 노드와 에지(연결선)로 구성된 집합
유니온 파인드
- 그래프의 사이클 유무 판별하는 알고리즘
위상 정렬
- 사이클이 없는 방향이 있는 그래프 일 때
- ex) 수강신청, 테크트리 같이 전 후 관계가 있는 그래프
다익스트라, 벨만-포드, 플로이드-워셜
- 최단거리 알고리즘
- S 시작점에서 다른 모든 노드로 가능 최단거리를 구하는 알고리즘
- 간선의 가중치가 음수면 안된다. (다익스트라)
- 간선의 가중치가 음수도 가능(벨만-포드)
- 시작점이 없고, 모든 노드에 최단거리, 대신 시간이 오래걸림(플로이드-워셜)
- 최소 신장 트리
- 모든 노드를 연결하는 데 최소 비용을 사용해서 하는 알고리즘
- 유니온 파인드를 포함
표현 방법
에지리스트
- 가중치 없는 그래프 구현
- 2차원 배열로 표현
- 가중치가 있는 그래프
- 2차원 배열을 3으로 저장
- 벨만 포드, 크루스칼 알고리즘에 사용
인접행렬
- n번 만큼 탐색
- 노드의 개수가 적은 경우에 사용
- 인접 행렬로 가중치 없는 그래프
- [n][n] 2차원 배열로 1,0을 넣어서 표현
- 인접 행렬로 가중치 있는 그래프
- [n][n] 2차원 배열로 가중치를 넣어서 표현
인접리스트
- 인접리스트로 가중치 없는 그래프
- ArrayList<Integer>[]로 선언
- 인접리스트로 가중치 있는 그래프
- ArrayList<Node>[]로 선언