se5674   1년 전

크루스칼 알고리즘에서 10번째 줄과 11번째 줄을 

find_parent(parent,a)

find_parent(parent,b)

라고 각각 적기도 하던데

42번째 줄에서 a와 b에 대한 find_parent 함수를 호출했기때문에 바로 parent[a]와 parent[b]로 접근해도 문제 없는 건가요??

bamgoesn   1년 전

틀린 말은 아닙니다만 그렇게 할 경우 "분리집합 (유니온파인드)"라는 자료구조를 단독으로 사용할 땐 경로 압축의 이득을 보기 어려워집니다.

이 코드라는 특수한 상황에선 문제 없으나 일반적인 관점에서는 문제가 될 수 있습니다.

wak8835   1년 전

일단 글 작성자분께서 올려주신 알고리즘은 Union-Find 알고리즘으로 크루스칼 알고리즘은 아닙니다.

위에 이미 달린 답변과 질문대로 42번 라인을 먼저 수행하고 (경로 압축), 그 다음 43번 라인 union 과정을 수행하기에 현 코드 내에서는 문제가 없습니다.

다만, parent 배열에 대해서 직접 접근하는 상황은 자기 자신의 값으로 초기화(init)하는 경우를 제외하고는 모두 find 를 통하여 간접적으로 값을 가져오는 것이 옳습니다.


이는 union과정에 의해 트리 형태로 복잡하게 연결되어 있는 노드들이 find 과정에서 (find_parent 함수가) 경로 압축에 해당하는 

`parent[x] = find_parent(parent, parent[x]);` 에 의해 재귀적으로 연결된 노드들이 1-depth 로 단번에 경로가 압축되기 때문입니다. 

요약하자면 이렇습니다.

1. union-find 에서 find 과정에서는 부모 노드를 단순히 가져오는 것이 아니라 경로 압축이 수행되기에 초기화 과정 외에 parent 배열의 직접 접근 보다 find를 사용하여 간접적으로 가져오는 것이 옳음

2. 즉, 보통의 경우에는 union 과정 내에서 find 과정으로 부모 노드를 가져오는 것을 권장됨 (10~11번 라인은 find_parent가 사용되는 것이 권장)

댓글을 작성하려면 로그인해야 합니다.