Union Find Algorithm - чтение чужого кода - PullRequest
Новая
       28

Union Find Algorithm - чтение чужого кода

0 голосов
/ 18 апреля 2020

Я пытался понять код на https://www.geeksforgeeks.org/union-find/.

Я не уверен, относится ли «родитель» в выделенной части к объекту «defaultdict», который должен ввести пользователь. Кроме того, может ли кто-нибудь объяснить мне, откуда взято «-1» (обратите внимание, что ни одна из вершин не будет иметь значения -1)?

Picture

Я прошу прощения за мой глупый вопрос ,

1 Ответ

1 голос
/ 18 апреля 2020

Я не уверен, относится ли «родитель» в выделенной части к объекту «defaultdict», который пользователь должен ввести

Нет. defaultdict - это график, который вводит пользователь. parent - это дерево, которое представляет наборы связанных компонентов графа - это любое дерево, которое соединяет все узлы из одних и тех же связанных компонентов. Существует несколько способов построить такое дерево, некоторые из которых лучше, чем другие

Например, у вас есть график, состоящий из 2 компонентов: 

1--2
|  |
3--4   5---6

Дерево (точнее, лес ) может быть 

  1        5       parent[2] = 1, parent[3] = 1, parent[4] = 3, parent[6] = 5
 / \        \      parent[1] = parent[5] = -1
2   3        6
     \
      4

также может быть 

1         5      parent[2] = 1, parent[3] = 2, parent[4] = 3, parent[6] = 5
 \         \
  2         6    parent[1] = parent[5] = -1
   \
    3
     \
      4

Первая версия лучше, потому что дерево короче по высоте. На самом деле лучшее дерево для представления компонента на приведенном выше графике: 

     1        5
   / | \      |
  2  3  4     6

Формально:

  • parent[u] == -1 означает, что u является root дерева.
  • parent[u] == v означает, что u и v принадлежат одним и тем же подключенным компонентам. Однако обратите внимание, что обратное неверно: это может быть parent[u] != v, но u и v принадлежат одним и тем же подключенным компонентам. Почему? Потому что может случиться так, что parent[u] == w, parent[w] == v и u и v связаны ассоциацией.
  • Так как определить, связаны ли два узла u и v? Вам нужно найти корни деревьев, которые содержат u и v, и если два корня одинаковы, то u и v принадлежат одному и тому же дереву, и они связаны.
  • Как найти root? Поднимаясь по родительскому узлу до достижения root (у которого родительский элемент равен -1)

Существуют также некоторые приемы, позволяющие сократить высоту деревьев при сохранении его представления. Обычно высота дерева поиска объединения должна быть и может быть очень короткой, в следующем порядке: log * (N) (с log * - это итеративный журнал )

...