알고리즘2 크루스칼 알고리즘 (최소스패닝트리,cut property, disjoint set 에 기반하여.) 크루스칼 알고리즘은 최소스패닝 트리를 구하는 알고리즘 중 하나이다. 우선 스패닝 트리에 대해알아보자. 스패닝트리 : 그래프의 모든 노드를 포함하는 트리. -> 즉 한붓그리기 가능하면 그 한붓을 스패닝트리 라고함. 한가지 그래프가 있으면 여러개의 스패닝트리가 존재한다. 스패닝트리의 weight = 그 스패닝트리의 가중치합. 스패닝 트리들 중에 weight 가 최소인거 : 최소스패닝 트리. -> 즉 최소스패닝트리 : 그래프의 모든 노드를 포함하는 트리중에 간선 가중치의 합이 최소인 트리. 최소스패닝 트리 구하는 알고리즘중 하나인 크루스칼 알고리즘, 이제좀 감이 잡힌다. 배워보려고 하는데 여기서 우선, 컷정리(cut property) 를 알아야 크루스칼 알고리즘을 배울수있다. 컷 프로퍼티란? 컷.. 2021. 5. 20. 다익스트라 알고리즘 -1 다익스트라 알고리즘은 무엇이고 어떤 용도로 쓰는가? 가중치가 있는 그래프에서 최단거리를 구할 때 쓴다. 여기서 잠깐!! 무방향 인접 그래프에서 최단거리에 관련된 알고리즘은 다음과 같이 대표적으로 3가지 종류가 있음. 1.다익스트라 알고리즘 - 하나의 정점에서 모든 정점까지 최단거리를 다구함 (1 : n) - 간선의 가중치가 양수일때만 사용가능 2.플로이드 알고리즘 -모든 정점에서 모든 정점까지 최단거리를 다구함 ( n : n, 물론 1보다 오래걸림) 3.벨만포드 알고리즘 - 하나의 정점에서 모든 정점까지 최단거리를 다 구함 (1 : n) - 간선의 가중치가 양수,음수 상관없이 사용가능 우선, 모오오오든 최단경로문제를 관통하는 키포인트는 이것이다. 정점 x에서 y까지 최단거리로 가려면 그 직전(y-.. 2021. 5. 20. 이전 1 다음 반응형