비선형 자료구조: 하나의 데이터 뒤에 N개의 데이터가 이어질 수 있는, 1:N 또는 N:N 구조로 데이터가 나열되는 자료구조 -> 계층적 구조를 나타내기 편리함, 하나하나 탐색하지 않아도 됨
※ 그래프 ※
- 인접: 두 장점이 간선으로 연결되어 있으면 인접하다고 함
- 차수: 정점에 연결된 간선의 수 (B의 차수는 3)
- 진입 차수: 해당 정점으로 향하는 간선의 수
- 진출 차수: 해당 정점에서 나가는 간선의 수
- 경로: 한 정점에서 다른 정점으로 이어지는 정점들의 리스트
- 경로 길이: 경로를 구성하는 간선의 수
- 단순 경로: 모두 다른 정점으로 구성된 경로
- 사이클: 한 정점에서 시작해 같은 정점으로 돌아올 수 있는 경로

*그래프의 종류
① 무방향 그래프
: 간선에 방향성이 없는 그래프, (A, B)와 (B, A)는 동일한 간선
정점의 개수가 n일 때, 최대 간선의 개수는 n x (n - 1) / 2

② 방향 그래프
: 간선에 방향성이 있는 그래프, A에서 B로 향하는 간선을 <A, B>로 표기
정점의 개수가 n일 때, 최대 간선의 개수는 n x (n - 1)

③ 부분 그래프: 기존 그래프에서 일부 정점 또는 간선을 제외
④ 가중치 그래프: 간선에 비용이나 가중치 할당
⑤ 완전 그래프: 간선을 최대로 가진 그래프
⑥ 유향 비순환 그래프(DAG): 방향 그래프 + 사이클 X
※ 경로 탐색 ※
1. 너비 우선 탐색(BFS)
: 탐색을 시작하는 정점에서 가까운 정점을 먼저 탐색하는 방식

2. 깊이 우선 탐색 (DFS)
: 시작 정점에서 탐색 가능한 최대 깊이의 정점까지 탐색, 재귀 호출 또는 스택으로 구현

BFS 대비 저장 공간을 적게 사용
'공부 기록 > CS' 카테고리의 다른 글
| 4.3 비선형 자료구조 (3) (0) | 2024.08.08 |
|---|---|
| 4.3 비선형 자료구조 (2) (0) | 2024.08.07 |
| 4.2 선형 자료구조 (0) | 2024.08.05 |
| 4.1 복잡도 (0) | 2024.08.02 |
| 3단원 요약정리 (0) | 2024.08.01 |