edge 2
[알고리즘] 최소 신장 트리(Minimum Spanning Tree)
최소 신장 트리(Minimum Spanning Tree) 신장 트리(Spanning Tree)는 그래프 내에 있는 모든 정점을 연결하고 사이클이 없는 그래프를 의미합니다. n개의 정점이 있다면 신장 트리의 간선 수는 n-1개가 됩니다. 최소 신장 트리는 각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장 트리입니다. 가중치는 거리, 비용, 시간 등 여러가지로 응용할 수 있습니다. 최소 신장 트리의 대표적인 알고리즘으로는 프림 알고리즘(Prim’s Algorithm)과 크루스칼 알고리즘(Kruskal’s Algorithm)이 있습니다. 프림 알고리즘(Prim’s Algorithm) 프림 알고리즘은 로버트 프림(Robert C. Prim)이 만든 최소 신장 트리 알고리즘 입니다. 프림 알고리즘은 최소 신..
[알고리즘] 그래프(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 경로가..