알고리즘/크루스칼 (Kruskal) (1) 썸네일형 리스트형 크루스칼 알고리즘 (Kruskal algorithm) 최소 신장 트리 : 노드를 모두 연결하는 트리에서 가장 짧게 연결할 수 있는 트리 (가장 적은 비용으로 모든 노드를 연결) 크루스칼 알고리즘은 그래프가 주어졌을 때 최소 신장 트리를 찾는 알고리즘이다. 위 그래프에서 최소 신장 트리는 선으로 굵게 칠해진 부분들이다. 우선 크루스칼 알고리즘을 구현 하기전에 Union-Find 알고리즘을 알아야 한다. 또 다른 이름으로는 서로소 집합(disjoint-set)알고리즘 이라고도 부른다. 이 알고리즘은 두 개의 노드가 주어졌을 때 서로 같은 집합인지 아닌지 판별해준다. #include using namespace std; int d[11]; int n = 10; int find_parent(int a) //집합의 부모(루트)를 찾아줌 { if (d[a] == a).. 이전 1 다음
