Union-Find는 그래프와 어떤 관련이 있습니까?

Question

전은 data structure이고 후자는 mathematical structure입니다.

그러나 구현되면 동일한 기능과 동작을 많이 공유하는 것처럼 보입니다.

분리 세트의 각 요소는 그래프의 정점으로 간주 될 수 있습니다. 그래프에서 모서리가 Union-Find의 집합을 나타냅니다.

• 이 두 요소/정점이
  을 연결되어 :

  http://algs4.cs.princeton.edu/15uf/ 및 http://algs4.cs.princeton.edu/42digraph/

  을 검토 한 후 둘 다 같은 질문에 대답 할 수 생각?

• 주기가 있습니까?

내가보기에는 두 가지 차이가 ​​더 큽니까? 언제 다른 하나를 사용하도록 선택해야합니까?

나는 그래프 알고리즘은 연합 찾기 구조 내부 http://algs4.cs.princeton.edu/43mst/KruskalMST.java.html

구현 세부 사항 사용할 수있는 볼 수 있지만, 연합 찾기가 빠르, 왜 사용 깊이 우선 검색 사이클 테스트? http://algs4.cs.princeton.edu/44sp/DirectedCycle.java.html

Answer 1

유니언 찾기는 동적 연결 문제에 대한 데이터 구조입니다 (예 : 런타임에 하나씩 가장자리를 연결하고 연결이 있는지 알고 싶을 때). 미로 또는 액체 침투를 생각해보십시오. 또한 동적 연결 문제에서는 대개 고유 한 항목 집합을 처리합니다. 본질적으로 등가 클래스를 구축하고 있습니다. 그러나 많은 그래프 문제에서 경로 또는 연결된 구성 요소를 찾고 있습니다.

귀하의 질문에 답하기 위해 가장자리를 추가/제거하고 시스템이 연결되었을 때 또는 연결된 항목의 수를 확인하려는 분리 된 세트 나 문제를 다루는 경우 union-find를 사용하십시오. 그렇지 않으면 DFS/BFS와 같은 그래프 알고리즘이 더 빠르고 쉽게 구현 될 수 있습니다.