그래프(Graph)란?

: 정점(=노드)과 간선으로 이루어진 구조
: 비선형 자료구조 - 하나의 자료 뒤에 여러개의 자료가 존재할 수 있음 !
그래프를 구현하는 방식
1. 인접 행렬
: |V| * |V| 크기의 2차원 배열을 만들어서 연결 관계를 표현하는 것. [ |V|는 정점 수 ]
- A→B로 가는 길이 있다면 배열의 값을 1로, 가는 길이 없다면 배열의 값을 0으로 지정한다.
- ‘플로이드-워셜’ 알고리즘에 사용

주요 시간 복잡도와 공간 복잡도
- 특정 정점 I, J가 연결되어 있는지 확인 : O(1)
- 특정 정점과 연결되어 있는 모든 정점을 확인: O(|V|)
- 공간 복잡도: O(|V|*|V|)
2. 인접 리스트
: |V| 개의 연결 리스트를 만들고, 연결 리스트에 특정 정점과 인접해있는 정점들의 정보를 담는 방식
- ‘다익스트라’ 알고리즘에 이용

주요 시간 복잡도와 공간 복잡도
- 특정 정점 I, J가 연결되어 있는지 확인 : O(min(degree(I)),degree(J))
- 특정 정점과 연결되어 있는 모든 정점을 확인: O(degree(X))
- 공간 복잡도: O(|V|+|E|)
REFERENCE
코드트리
'[Algorithm] 알고리즘' 카테고리의 다른 글
| 최소 신장 트리(MST) (1) | 2024.07.09 |
|---|---|
| 이진 탐색 (0) | 2024.07.09 |
| 플로이드 워셜 알고리즘 (0) | 2024.07.09 |
| [Python][백준1931] 회의실 배정 (3) | 2024.07.02 |
| 그리디(Greedy) 알고리즘 (1) | 2024.07.02 |