sundori DevStory

최단 경로 최단 경로는 신장 트리가 아닌 가중치 그래프, 즉 네트워크에서 정점 u와 정점 v를 연결하는 경로 중에서 가중치의 합이 최소인 경로이다. 예를 들어 지하철 노선 어플을 보면 내가 원하는 출발지에서 목적지까지의 최단 경로를 구하는 어플, 그리고 내비게이션이 있다. 이러한 최단 경로를 구하는 가중치 그래프에서는 가중치 인접 행렬 Weight Adjacent Matrix를 사용하는데, 이 가중치 인접 행렬은 2차원 배열이며, 두 정점 사이에 간선이 없으면 0이 아니라 무한∽이라는 값이 저장되어 있다고 가정하고 사용한다. 그렇게 최단 경로를 찾는 방법에는 하나의 시작 정점에서 다른 정점까지의 최단 경로를 구하는 다익스트라 Dijkstra 최단 경로 알고리즘과 모든 정점에서 다른 모든 정점까지의 최단 ..

목차 크루스칼 알고리즘 2 이 알고리즘은 가중치가 낮은 간선을 삽입하면서 최소 비용 신장 트리를 만들어가는 알고리즘이다. 크루스칼 알고리즘 2를 적용한 최소 비용 신장트리를 만들기 위해서는 밑에 4가지의 순서를 지키며 트리를 생성하면 되는데... 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬한다. 그래프에서 가중치가 가장 낮은 간선을 삽입한다. 단, 이때 정점을 그래프에서 사이클을 형성하는 간선은 삽입할 수 없으므로 그다음으로 가중치가 낮은 간선을 삽입한다. 그래프에 간선이 n-1개 삽입될 때까지 2번 과정을 반복한다. 그래프에 간선이 n-1개가 되면최소 비용 신장 트리가 완성된다. 그렇다 이 순서를 읽어보면 크루스칼 알고리즘 1과 다르게 정점과 간선을 삽입하면서 최소 비용 신장 트리를 만들어가는..

목차 신장트리 그래프의 관점에서 트리를 보면 사이클이 없는 연결 그래프이다. 사이클이란 순환 경로에서 시작 정점과 종료 정점이 동일한 경우를 말한다. 모든 정점이 n개인 무방향 그래프에서 정점이 n개이고 간선이 n-1개인 트리의 형태의 부분 그래프를 신장 트리 Spanning Tree라고 한다. 깊이 우선 탐색을 이용하여 생성된 신장 트리를 깊이 우선 신장 트리(Depth First Spanning Tree)라고하며, 너비 우선 탐색을 이용하여 생성된 신장 트리를 너비 우선 신장트리(Breadth First Spanning Tree)라고 한다. 위의 사진을 보면 알다시피 모든 정점이 무조건 한 번씩 연결이 되어있는데 이것이 바로 간선을 최소로 이용하여 모든 정점을 연결한 신장트리이다. 이렇게 간선을 최소..