전체태그 보기

#크루스칼 (4개의 포스트)

그래프 알고리즘 정리
wan088

그래프 알고리즘 정리

2019년 8월 13일0개의 댓글
그래프? 정점과 간선들로 이루어진 집합. 즉 트리 역시 그래프에 속한다고 할 수 있다. - 그래프를 표현하는 세가지 방법 1.간선 리스트 말그대로 배열에 간선들을 저장한다. 가장 간단하게 구현되지만 한 정점의 간선에 대한 정보를 얻으려면 모든 간선리스트를 탐색해야 하기 때문에 벨만-포드 알고리즘과 크루스칼 알고리즘 같은 일부 알고리즘이 아...
doontagi
image.png 문제 파악 일반적인 최소 스패닝 트리는 트리의 가중치 합이 최소가 되어야 한다. 그러나 이 문제의 요구 조건은 스패닝 트리를 이루는 가중치의 최대값과 최소값의 차이가 최소가 되어야 하는 것이다. 생각한 방식은 min값과 max값을 계속 갱신해 나가면서 스패닝 트리를 만드는 것인데 이렇게 되면, 가중치를 정렬함으로써 간선을 효율적...
doontagi

그래프 최소 스패닝 트리

2019년 7월 25일0개의 댓글
크루스칼 알고리즘 크루스칼 알고리즘이란 크루스칼 알고리즘과 프림 알고리즘은 최소 스패닝 트리를 만들기 위해 자주 쓰이는 알고리즘이다. 크루스칼 알고리즘의 원리는 매우 간단하다. 그래프의 간선들을 가중치 순으로 정렬해 가장 작은 가중치부터 그리디 알고리즘과 같이 선택해 트리에 포함시키는 것이다. 이 때 사이클이 생기면 안되므로 만약 간선이 추가됨으로...
skyepodium

programmers 섬연결하기

2019년 1월 26일1개의 댓글
문제 한줄요약: 1) 크루스칼 알고리즘으로, 2) 최소 스패닝 트리를 만든다. - 최소 스패닝 트리 정점이 n개인 그래프의 간선중 일부인 n-1개의 간선을 선택해서 모든 정점을 연결한 트리중 가중치의 합이 최소인 트리 - 크루스칼 알고리즘 최소 스패닝 트리를 찾는 알고리즘...