📌 그래프를 구현하는 3가지 방법
1. 에지 리스트
- 에지를 중심으로 그래프 표현
- 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현
또는 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현
◾ 가중치가 없는 그래프
- 배열의 duf 2개만 사용 (출발 노드, 도착노드로 표현하기 때문)
- 여러가지 자료형 사용 가능
- 만약 방향이 없는 그래프라면 [1,2] , [2,1] 를 같은 표현으로 본다.
출처 : https://velog.io/@dhsdb02/DFS-35aoelt1
◾ 가중치가 있는 그래프
- 배열의 열 3개 필요 (출발 노드, 도착노드, 가중치)
- 에지 리스트는 구현하기 쉽지만 특정 노드와 관련되어 있는 에지를 탐색하기 어려움
- 에지 리스트는 벨만 포드나 크루스칼 알고리즘에 사용하며 노드 중심 알고리즘에는 잘 사용하지 않음.
출처 : https://velog.io/@dhsdb02/DFS-35aoelt1
2. 인접 행렬
- 2차원 배열의 자료구조를 이용하여 그래프 필요
- 노드가 5개인 그래프를 5 X 5 인접 행렬로 표현
◾ 인접 행렬로 가중치 없는 그래프 표현하기
출처 : https://velog.io/@dhsdb02/DFS-35aoelt1
- 1 → 2 를 향하는 에지를 인접행렬은 1행 2열에 1을 저장하는 방식으로 표현
=> 1을 저장하는 이유는 가중치가 없기 때문
(에지의 유무 표현으로 이해하기)
◾ 인접 행렬로 가중치 있는 그래프 표현하기
- 기존에 유무를 표현했던 곳에 가중치만 넣어주면된다.
노드와 관련되어 잇는 에지를 탐색하려면 N번 접근해야 하므로 노드 개수에 비해 에지가 적을 때에는 공간 효율성이 떨어짐.
따라서 인접 행렬 노드 개수에 따라 사용 여부를 적절하게 판단해야 함
3. 인접 리스트
- Array List로 그래프 표현
- 노드 개수만큼 Array List를 선언
- 자료형 경우에 맞게 사용
- 인덱스를 통해 시작노드를 표현
◾ 인접 리스트로 가중치 없는 그래프 표현하기
출처 : https://velog.io/@dhsdb02/DFS-35aoelt1
ArrayList<Integer>[N]
◾ 인접 리스트로 가중치 있는 그래프 표현하기
출처 : https://velog.io/@dhsdb02/DFS-35aoelt1
- 가중치가 있을 때 Class를 넣어준다 ex)
ArrayList<Node>[N] - 구현은 복잡하지만 노드와 연결되어 있는 에지를 탐색하는 시간이 매우 뛰어나다
→ 인덱스를 통해 시작 노드를 표현하기 때문에
