그래프 보충

ㅎㅇ 나다

인접행렬과 인접리스트를 너무 대충 다뤄서
추가 보충을 하겠다

둘의 표현 방식 예시

무방향 그래프

노드: 1~5, 엣지: (1-2), (1-3), (2-4), (3-5)

🔹 인접 행렬 (Adjacency Matrix)

🔹 인접 리스트 (Adjacency List)

1 -> 2 -> 3 -> None
2 -> 1 -> 4 -> None
3 -> 1 -> 5 -> None
4 -> 2 -> None
5 -> 3 -> None

방향 그래프

노드: 1~5, 엣지: 1→2, 2→3, 3→4, 4→5

🔹 인접 행렬 (Adjacency Matrix)

🔹 인접 리스트 (Adjacency List)

1 -> 2 -> None
2 -> 3 -> None
3 -> 4 -> None
4 -> 5 -> None
5 -> None

둘의 차이

둘의 차이를 둔 이유는 당연하게도 성능의 차이 때문이다

각각 더 잘 어울리는 상황이 존재한다

그래프는 보통 $G = (V,E)$로 표현하는데

• $G$ = 그래프
• $V$ = 정점 집합
• $E$ = 간선 집합

인접리스트 방식은 희소 그래프에서 효율적이다

희소 그래프가 뭔데?


그건…

희소그래프

희소 그래프란,
정점에 비해 간선이 적은 ($|E|$ < $|V^2|$보다도 훨 작은) 경우의 그래프이다

밀집그래프

반대되는 개념으로 밀집 그래프가 있다
얜 반대로 정점 수에 비해 간선 수가 매우 많은 그래프다
(일반적으로 $|E| ≈ |V²|$)

아무튼, 인접리스트 방식의 경우

메모리 효율이 $O(V+E)$인데

$E$가 적으니 더 효율적이다

인접리스트가 희소 그래프에서 유용했으니

인접배열은 당연히 밀집 그래프에서 유용하다

왜 그러냐?

인접행렬의 경우 공간 메모리를 $O(V^2)$만큼 소모하는 대신
연결 확인속도가 $O(1)$로 무척 빠르다

인접리스트의 경우는 $O(V)$인 반면 말이다

요약

| 구분 | 희소 그래프 (Sparse) | 밀집 그래프 (Dense) | | ——- | ————— | ————– | | 간선 수 | 적음 E ≪ V² | 많음 E ≈ V² | | 표현 방식 | 인접 리스트 (효율적) | 인접 행렬 (효율적) | | 예시 | 소셜 네트워크, 트리 | 완전 그래프, 도로망 시뮬 | | 공간 효율 | O(V + E) | O(V²) | | 알고리즘 특성 | 일부 알고리즘에서 성능 우수 | 전체 탐색 알고리즘에 적합 | ___

___