그래프
- Vertex, edge로 구성된 자료구조
- Vertex == Node
그래프 Graph
- 네비게이션 길찾기
- 게임 내 캐릭터 이동
- 지식 그래프
쾨니히스베르크의 다리 문제
- 한 다리를 두번 이상 건너지 않고 모든 다리를 건널 수 있나? -> 불가능함
방향 그래프 Directed Graph
가중치 그래프
루프 loop
순환 그래프 Cyclic Graph
그래프의 구현
- 인접 행렬
- 2차원 배열로 구현
단점은 메모리를 많이 써야한다,
새로운 노드 생기면 연산량이 늘어난다.
인접 리스트
- Vertex 갯수 만큼의 list 사용
효율적인 메모리 공간
생성 추가 수월함
인접행렬보다 edge를 찾는데 오래 걸릴 수 있음
그래프 순회
- 그래프 탐색
- 위상 정렬
- 그래프의 최단거리
DFS
- 깊이 우선 탐색
BFS
- 너비 우선 탐색
'자료구조&알고리즘' 카테고리의 다른 글
| 힙 Heap 자료구조 (0) | 2022.04.08 |
|---|---|
| 트리 자료구조 (이진트리) (0) | 2022.04.08 |
| 탐색과 정렬 알고리즘 (이진 탐색, 버블 정렬, 삽입 정렬, 합병 정렬, 퀵 정렬) (0) | 2022.04.08 |
| HASH와 HASH Collision 그리고 Chaining (해시 자료구조) (0) | 2022.04.07 |
| 스택과 큐에 대하여 (0) | 2022.04.07 |