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

Question

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

Answer 1

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

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

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

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