그래프 (Graph)

그래프란?

그래프는 정점(Vertex) 과 간선(Edge) 으로 이루어진 자료구조이다.
그렇다면 정점과 간선은 무엇일까?

각각의 데이터를 나타내는 것을 노드(Node)라고 하는데, 그래프에서는 이 노드를 정점(vertex) 이라고 부른다.
그리고 이 정점을 잇는 선을 간선(edge) 이라고 부른다.

그래프 알고리즘

BFS(Breadth-First Search; 너비 우선 탐색)

현재 정점에서 가까운 정점부터 차례대로 탐색하는 방식으로 큐를 사용하여 구현한다.

DFS(Depth-First Search; 깊이 우선 탐색)

현재 정점에서 연결된 정점을 하나 선택해 끝까지 탐색한 뒤, 더 이상 갈 곳이 없으면 되돌아가며 다른 경로를 탐색하는 방식으로 스택을 사용하여 구현한다.

다익스트라(Dijkstra)

하나의 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘이다.

플로이드 워셜(Floyd-Warshall)

그래프에 있는 모든 정점들 사이의 최단 거리를 구하는 알고리즘이다.