728x90
구성요소
- Vertext(node)
- edge
그래프 종류
- 방향성
- 무방향 그래프(양방향 그래프)
- 방향 그래프
- 순환성
- 순환 그래프(Cyclic Graph)
- 비순환 그래프(Acyclic Graph)
- 방향성 비순환 그래프(DAG. Directed Acyclic Graph)
VCS (Version Control System)
버전 관리 시스템으로 대표적으로 git과 github가 있다. 또한 이는 대표적인 방향성 비순환 그래프이다.
연결 요소(Connected Component)
아래 그림은 연결요소가 3개인 그래프이다.
코드로 그래프를 나타내는 방법
- 인접행렬
- 인접리스트
인접행렬 vs 인접리스트
둘 중에 뭘 써야할까? 여기에서 시간과 공간 사이의 trade off를 알 수 있다.
- 메모리 공간
- 인접행렬 노드가 n개이면, 간선의 수에 상관없이 n제곱만큼의 메모리 공간을 소비한다.
- 인접리스트는 간선의 수가 적으면 메모리 공간을 더 적게 소비한다.
- 시간
- 인접행렬에서는 O(1)로 특정 노드간의 간선이 연결되어있는지 확인할 수 있다.
- 인접리스트는 O(N)
728x90
