알고리즘2 MST, 최소 신장 트리, 크루스칼 알고리즘 cost가 작은 최소 연결 트리 최소 연결 = 간선의 수가 가장 적다 DFS, BFS을 이용하여 신장 트리를 찾을 수 있다. 탐색 도중에 사용된 간선만 모으면 만들 수 있다. n개의 정점을 연결함으로 (n-1)개 간선으로 연결함 Spanning Tree 사용 예시? 회사 내 모든 전화기를 가장 적은 수의 케이블을 이용하여 연결하는 경우 최소의 선으로 링크를 연결하는 경우 MST 특징 1.간선 Cost가 최소 2. (N-1)개 간선 3. 간선이 포함되면 안됨 쿠르스칼 알고리즘 : MST 구현방법 1. 간선 가중치를 오름차순 정렬 2. 부모를 본인 자신으로 하는 경우로 parent 배열 초기화 3. 싸이클이 존재하지 않는 경우 union find 알고리즘 적용(싸이클이 생기지 않는 경우) 이를 순서대로 su.. 2019. 10. 6. 벨만-포드 알고리즘 음의 가중치가 있는 최단거리알고리즘 start, destination, weight 로 구성됨 https://ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/ 벨만-포드 알고리즘 · ratsgo's blog 이번 글에서는 최단 경로(Shortest Path)를 찾는 대표적인 기법 가운데 하나인 벨만-포드 알고리즘(Bellman-Ford’s algorithm)을 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님과 역시 같은 대학의 김황남 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다. concept 최단경로 문제의 optimal substructure를 확장하면 최단경로를 다음과 같이 분해(decompos.. 2019. 9. 29. 이전 1 다음
