전체태그 보기

#프림 (2개의 포스트)

그래프 알고리즘 정리
wan088

그래프 알고리즘 정리

2019년 8월 13일0개의 댓글
그래프? 정점과 간선들로 이루어진 집합. 즉 트리 역시 그래프에 속한다고 할 수 있다. - 그래프를 표현하는 세가지 방법 1.간선 리스트 말그대로 배열에 간선들을 저장한다. 가장 간단하게 구현되지만 한 정점의 간선에 대한 정보를 얻으려면 모든 간선리스트를 탐색해야 하기 때문에 벨만-포드 알고리즘과 크루스칼 알고리즘 같은 일부 알고리즘이 아...
doontagi

그래프 최소 스패닝 트리

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