그래프 이론(graph theory): 수학에서 객체 간에 짝을 이루는 관계를 모델링하기 위해 사용되는 수학 구조인 그래프에 대한 연구
: 꼭짓점(버텍스/vertex), 교점(노드/node), 점(포인트/point)으로 구성되며 이것들은 변(엣지/edge, 간선), 즉 선으로 연결된다.
무향(무방향성)그래프: 이는 각 변(선)으로 연결되는 두 개의 꼭짓점 간에 구별이 없다는 의미
유향그래프: 변은 한 꼭짓점에서 다른 꼭짓점 간에 방향이 있을 수도 있다.
(더 자세한 정의와 이러한 유형의 그래프의 변종에 대해서는 ( ᐛ )و그래프 이론 용어를 참고할 것)
가장 일반적인 의미에서 그래프(graph)는 순서쌍 G = (V, E)으로 볼 수 있으며, 여기에서 집합 V는 꼭짓점, E는 간선(변)을 의미한다. 혼동을 피하기 위해, 이러한 형태의 그래프는 정확히 방향이 없으며(무향), 단순한 그래프라고 기술할 수 있다.
(서로 다른 개체가 연결 or 여러 도시의 연결 과 같은 경우는 그래프 알고리즘 의심)
2차원 배열을 사용하는 방식 ex> 플로이드 워셜 알고리즘 when faced with 최단경로 문제 if 노드의 개수가 적다면,,
*플로이드 워셜 알고리즘: 모든 노드에서 각각의 다른 노드까지 최단 경로를 구하는 알고리즘
모든 노드에 대하여 다른 노드로 가는 최소 비용을 $V^2$크기의 2차원 리스트에 저장한 뒤에 해당 비용을 갱신해서 최단 거리를 계산
소요 메모리: O($V^2$)
소요 접근 시간: O(1)