Нахождение корня дерева

Question

Как я могу получить из множества узлов и ребер получить дерево с корнем?(Я работаю с матрицей связности, каждое ребро имеет вес: graph [i] [j], без каких-либо отрицательных ребер).Позже мне нужно сделать DFS и найти LCA в этом дереве, так что это было бы хорошо для оптимизации.

Answer 1

Я полагаю, что ваша матрица представляет дочерние отношения (т. Е. M[i][j] говорит, что j является дочерним для i), для ориентированного графа G (V, E) .

У вас есть 2 разные стратегии:

• используйте битовый вектор, пройдитесь по каждой ячейке вашей матрицы и отметьте дочерний индекс в векторе, если вес ячейки не равен нулю): корень - это вершина, не заданная в векторе,
• поиск столбцов (или строк, если ваша матрица является первым столбцом), все ячейки которых равны нулю (без предков),

Второе решение лучше для плотных матриц. Его худшее время выполнения будет, когда корнем является последняя запись (O (V²)). В этом случае вы можете остановиться на первом ударе или запустить до конца, чтобы получить все корни, если у вашего графика их много.

Первый лучше подходит для разреженных матриц, так как вам нужно пройти через все ячейки. Время работы в O (E). Вы также получаете все корни с помощью этого алгоритма.

Если вы уверены, что у вашего графа только один корень, вы можете использовать технику обхода по краям, как описано в других ответах.

Answer 2

Вот вычислительно МНОГО МЕДЛЕННАЯ версия, которую также гораздо проще кодировать.Для небольших графиков это просто отлично.

Найти узел с нулем в градусах!

Вы должны вычислить все степени узла, O (n), но в зависимости от настройки это часто намного проще кодировать и, следовательно, меньшеподвержен ошибкам.

Answer 3

Выберите один узел в дереве и идите вверх, то есть против ориентации краев.Когда вы находите узел без предка, у вас есть корень.

Если вам нужно часто делать что-то подобное, просто запомните родительский узел для каждого узла.

Answer 4

поиск DFS по любому графику дает вам дерево (конечно, при условии, что граф подключен).

вы можете выполнить его итерацию и, начиная с каждого узла в качестве возможного корня, вы получите spanningдерево в конце концов таким образом, если есть.сложность будет O (V ^ 2 + VE)

РЕДАКТИРОВАТЬ: это работает, потому что для любого конечного графа, если есть корневой узел формы от узла к узлу b, будет путьот а до б в дереве создает DFS.Итак, если предположить, что существует возможное связующее дерево, есть корень r, который вы можете получить от каждого v в V. При итерации, когда r выбран в качестве корня, существует путь от r к каждому v в V, поэтомубыть путем от r до него в связующем дереве.