[알고리즘] 그래프(Graph)

그래프 정의 그래프는 정점(Vertex)의 집합과 간선(Edge)의 집합으로 이루어진 자료구조입니다. 정점의 집합을 V, 간선의 집합을 E, 그래프를 G라고 했을 때 G = (V, E) 입니다. 정점은 위치를 의미하고, 간선은 정점과 정점을 연결하는 선을 의미합니다. 간선으로 연결되어 있는 두 정점을 가리켜 서로 인접(adjacent)해 있다고 표현합니다. 인접한 두 정점은 경로를 형성하기도 하는데 위 그림을 보면 1, 2, 3, 4 가 경로를 형성합니다. 경로 1, 2, 3, 4 사이에는 간선이 (1, 2), (2, 3), (3, 4) 3개가 있으므로 길이는 3이 됩니다. 경로가 정점 하나를 두 번 이상 거치게 된다면 그 경로는 사이클(Cycle)이 있다고 표현합니다. 위 그림에서 1, 2, 3 경로가..