-
그래프의 이해와 종료 (+추가 예정)Algorithm\자료구조 2021. 8. 23. 16:00
그래프 알고리즘 : 출발지와 목적지를 정하고 그에 맞는 최적의 경로를 찾는 방법
- 수학자 '오일러'에 의해 고안되었음 (쾨니히스베르크의 다리)
"정점 별로 연결된 간선의 수가 모두 짝수이어야, 한번씩만 지나서 처음 출발했던 정점으로 도착"
- 정점 (vertex) : 연결의 대상이 되는 개체 또는 위치
- 간점 (edge) : 이들 사이의 연결을 의미
- 무방향 그래프 (undirected) : 방향성이 없는 그래프
- 방향 그래프 (directed, digraph) : 간선에 방향 정보가 포함된 그래프
- 완전 그래프 : 각각의 정점에서 다른 모든 정점을 연결한 그래프
- 무방향 그래프와 방향 그래프는 간선의 연결 형태의 따라 구분됨
- 방향 그래프의 간선의 수는 무방향 그래프의 간선선의 수에 두 배 (쌍방 가능해야되서)
-그래프 구현 방법
- 인접 행렬 (adjacent matrix) 기반 : 정방 행렬을 활용
- 인접 리스트 (adjacent list) 기반 : 연결 리스트를 활용
'Algorithm\자료구조' 카테고리의 다른 글
팩토리얼 / 순열 / 조합 (0) 2021.09.06 최대공약수와 최소공배수 (+ 소수) (0) 2021.09.04 너비 우선 탐색 (Breadth First Search, BFS) (1) 2021.08.23 [알고리즘/Algorithm] 알고리즘의 개요 (0) 2021.08.23