4.3 비선형 자료구조 (1)

비선형 자료구조: 하나의 데이터 뒤에 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 대비 저장 공간을 적게 사용