# ch04 자료구조 그래프

# ch04 자료구조 그래프

* 그래프 Graph

ex)

- 지도, 내비게이션

- SNS / 메신저

- VCS 버전관리

간선 : Edge

노드 : Node (=Vertex)

무방향그래프 (=양방향그래프) : 방향X

방향그래프 : 방향 O

순환그래프 : Cyclic

비순환그래프 : Acyclic

방향성 비순환 그래프 : 순환이 없으면서 방향을 갖고 있는 그래프 (ex: VCS)

* 트리 Tree

-> 순환성이 없는 무방향 그래프

-> 특정하지 않는 한 어떤 노드든지 루트가 될 수 있다

-> 가장 바깥쪽 노드는 리프노드

- 노드 A에서 노드 B로 가는 경로는 반드시 존재하며 유일

- 노드 개수 = 간선 개수 + 1

- 자료구조에서의 트리는 부모 -> 자식 관계가 있는 방향그래프

- 자료구조에서는 루트노드root-node는 하나

* 그래프를 코드로 나타내는 방법

1. 인접행렬

방향그래프

행은 간선의 시작, 열은 간선의 도착

무방향그래프, 대칭

2. 인접리스트(= 연결리스트)

방향

인접행렬과의 차이는 간선이 없다면 공간자체의 할당 X

무방향

인접행령 vs 인접리스트

: 인접행렬(N^2)은 인접리스트보다 많은 리소스 사양

시간 <=> 공간의 trade-off 관계

: 인접행렬은 임의 접근을 사용해서

from http://gomddu.tistory.com/44 by ccl(A) rewrite - 2021-11-18 17:26:27