크루스 칼의 알고리즘 설명

Question

나는 wikipeida을 읽고 다음과 같이 크루스 칼의 의사 코드 발견 : 나는 FIND_SET()가 무엇을 확인 조용히 아니에요, 그리고 위키 백과는 다음과 설명이

KRUSKAL(G):  
    foreach v ∈ G.V:  
     MAKE_SET(v)  
    G.E = sort(G.E)  
    i = 0  
    while (i != |V|-1):  
     pick the next (u, v) edge from sorted list of edges G.E   
     if (FIND_SET(u) != FIND_SET(v)):   
      UNION(u, v)   
      i = i + 1 

을 :

하는 경우를 가장자리는 두 개의 서로 다른 나무를 연결 한 다음 두 개의 나무를 하나의 나무로 결합하여 숲에 추가합니다.

두 개의 다른 트리가 연결되어 있는지 확인합니다.하지만 실제로이 의미는 무엇입니까?

FIND_SET(u) != FIND_SET(v) 

는 U 및 V가 똑같은 접속되지 않도록 : 비교되도록

Answer 1

처음에는 각 정점은 모두 그 자체로 세트입니다 : 모든 정점 v에 대한 {v}을 설정 싱글이있다. 의사 코드에서이 세트는 make_set(v)의 결과입니다.

주어진 정점이 v 인 경우 find_set(v) 함수는 v을 포함하는 집합을 제공합니다.

알고리즘은 반복적 세트를 병합되므로 {u} 경우 {v}는 단일 세트는 최초이며 에지 (u, v) 다음 알고리즘들의 조합 {u, v}하여 두 세트의 대체가있다. 이제 find_set(u)과 find_set(v) 모두 해당 집합을 반환합니다.

|V| - 1 가장자리를 추가하면 알고리즘이 종료됩니다. 트리의 가장자리 수와 정확히 일치합니다.

Answer 2

FIND_SET (X)는, 에지 (X)와 연관된 세트를 찾는다. 그것에 대해 생각할 수있는 유용한 방법은 값이 자체적으로 설정되는 u 및 v의 "값"을 찾는 것입니다. 두 세트를 병합

UNION(u,v) 

:

숲을 병합하는 방법에 대한 부분은 FIND_SET와는 아무 상관이 아니라 다음 행이 없습니다.

Answer 3

find_set()은 Union-Find로 알려진 일종의 데이터 구조의 일반적인 작업입니다. 이 데이터 구조의 아이디어는 분리 된 세트 (예 : 정점)를 갖는 것입니다.

이 알고리즘에서는 각 세트가 연결되어있는 정점을 나타내는 것으로 생각합니다.

따라서 find_set()을 호출하면 정점이 지나가고 연결된 verxtex 집합을 나타내는 요소가 나타납니다.

Answer 4

find_set(u)!=find_set(v) 

는 다음 그래프에서주기가 보여주고 그들이 동일한 cycles.If을하지 않는 것입니다 스패닝 트리의 기본 속성을 의미한다.

우리는 기본적으로 Kruskal 알고리즘을 통해 최소 에지 가중치의 포리스트를 만들고 각 단계에서주기를 만들지 여부를 확인합니다.

도움이 되길 바랍니다.