как разделить дерево на два поддерева - PullRequest
Новая
       50

как разделить дерево на два поддерева

0 голосов
/ 08 февраля 2012

У меня есть симметричный двумерный массив «myMSTdata [] []» точек, представляющий минимальное связующее дерево MST со значениями 0, если нет ребра или действительного значения, представляющего веса на ребрах, и теперь мне нужно разделить этодерево в два поддерева (часть 1, часть 2), где критерием резки является край с максимальным весом.Затем многократно продолжайте разделять поддерево большего размера (что означает поддерево с большим числом узлов), пока оставшееся количество узлов в поддереве большего размера не станет K.

1 Ответ

0 голосов
/ 24 февраля 2012

Было бы предложено использовать список смежности для этого вида операций, так как

  1. Вам необходимо повторно разделять вершины
  2. Количество ребер <$ n $ количество вершин. </li>
  3. Большие преимущества времени выполнения.

Могу ли я узнать, на какую сложность вы смотрите?

Если вас устраивает какая-либо сложность, я бы предложил повторную DFS, поскольку вы работаете с деревом, повторная DFS покроет все ребра и вершины. Время выполнения будет около O (n ^ 2) в худшем случае.

...