Given the vertices and edges between them, how could we quickly check whether two vertices are connected? For example, Figure 5 shows the edges between vertices, so how can we efficiently check if 0 is connected to 3, 1 is connected to 5, or 7 is connected to 8? We can do so by using the “disjoint set” data structure, also known as the “union-find” data structure. Note that others might refer to it as an algorithm. In this Explore Card, the term “disjoint set” refers to a data structure.
주어진 vertices와 edges들 사이에서 두가지 vetices가 연결이 되었는지 어떻게 빠르게 확인 할 수 있는가. 예를 들어, 그림5는 vertices 사이의 edges들을 보여준다, 그러면 어떻게 '0과3이', '5와 1'이, '8와 7'이 연결되었는지 효과적으로 확인 할 수 있는가. 우리는 'union-find' 자료구조라고도 알려진 'Disjoint set' 자료 구조를 사용해 해결할 수 있다. 다른사람들은 이걸을 알고리즘으로 알고 있다. 이번 챕터에서 'Disjoint set'은 데이터 구조를 말한다.
'disjoint set'은 네트워크 구성요소의 사이의 연결을 설명하기 위해 이전에 사용되었다.
여기서 네트워크는 컴퓨터의 네크워트이거나 사회적 네트워크이다. 예를 들어, 우리는 'disjoint set'을 어떤 두사람이 공통의 선조를 가지는지를 확인할 수 있다.
Terminologies
- Parent node: the direct parent node of a vertex. For example, in Figure 5, the parent node of vertex 3 is 1, the parent node of vertex 2 is 0, and the parent node of vertex 9 is 9.
- Parent node : vertex 의 직접적인 부모 node. 예를 들어, 그림 5에서 , 3의 parent node는 1이고, 2는 0, 9는 9이다
- Root node: a node without a parent node; it can be viewed as the parent node of itself. For example, in Figure 5, the root node of vertices 3 and 2 is 0. As for 0, it is its own root node and parent node. Likewise, the root node and parent node of vertex 9 is 9 itself. Sometimes the root node is referred to as the head node.
- Root node : Parent node를 가지지 않는 node. 이것은 자기스스로 Parent node 로 보일 수 있다. 예를 들어, 그림 5에서, 3과2의 parent node는 0이다. 그래서 0은 스스로 parent node이면서 root node이다. 더욱이, 9의 parent node와 root node는 9자신이다. 때떄로 root node는 head node 가 아닐 수 있다.
Implementing “disjoint sets”
Summary of video content:
- How to implement a “disjoint set”.
- The
findfunction of a disjoint set. - The
unionfunction of a disjoint set.
The two important functions of a “disjoint set.”
In the introduction videos above, we discussed the two important functions in a “disjoint set”.
- The
findfunction finds the root node of a given vertex. For example, in Figure 5, the output of the find function for vertex 3 is 0. - find function 은 주어진 vertex의 root node를 찾는다. 예를 들어, 그림 5에서 vertex3의 find function결과 값은 0이다.
- The
unionfunction unions two vertices and makes their root nodes the same. In Figure 5, if we union vertex 4 and vertex 5, their root node will become the same, which means the union function will modify the root node of vertex 4 or vertex 5 to the same root node. - union function은 두가지 vertice를 묶고, 그들의 root node를 같게 한다. 그림 5에서 4와 5를 묶게 되면, 이들의 root node는 같아 질 것이다. 이는 vertex 4와 5를 같은 root node로 수정함을 의미한다.
