c 언어 알고리즘 썸네일형 리스트형 최소신장트리(Minimum Spanning Trees) 크루스칼(Kruskal) 알고리즘 최소신장트리(Minimum Spanning Trees) 크루스칼(Kruskal) 알고리즘 신장트리란? - 사이클을 형성하지 않고 그래프의 모든 정점이 간선으로 연결되어 있는 것 최소 신장 트리(MST : Minimum Spanning Trees)란? - 최소한의 비용(가중치)로 신장 트리를 형성하는 것 크루스칼(Kruskal) 알고리즘 - 최소 신장 트리를 형성하기 위한 알고리즘 - Disjoint-set을 사용한다. * 대표 원소(representitive)를 통해 각 set을 분별하는 방식. * 이에 대해서는 차 후에 자세하게 다루겠다. 1. 동작원리 (1) 모든 정점들(vertices)을 독립적인 원소(set)로 만든다. (2) 모든 선분들(edges)을 가중치를 기준으로 정렬한다. (3) 가중치가.. 더보기 벨먼-포드 알고리즘(Bellman-Ford algorithm) 벨먼-포드 알고리즘(Bellman-Ford algorithm) - 가중치 그래프에서 시작점에서 목표점까지의 최단 경로를 찾는 알고리즘이다. - 다익스트라 알고리즘과 흡사하지만, 다익스트라보다 조금 더 느리다. + 음수 가중치를 판단할 수 없는 다익스트라에 비해 조금 더 유연하다. 동작 원리 (1) 시작점을 제외한 모든 점의 거리를 무한으로 초기화한다. ( 시작점의 거리는 0 ) (2) 모든 점의 수 만큼 반복적으로 가중치가 있는 모든 선분을 검사한다. (3) 갱신 가능한 거리가 있으면 최단거리를 갱신한다. (4) 음수 싸이클이 있는지 검사하고, 검사 결과를 반환한다. [ Fig. 1 ] process of bellmanford. cite : introduction to algorithm 3/E 함수 설명.. 더보기 이전 1 다음
