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

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

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

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

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

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

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

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

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

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

Найдите узел с нулевой степенью входа!

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

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

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

EDIT: это работает, потому что для любого конечного графа, если есть узел корневой формы от a до узла b, в дереве, создаваемом DFS, будет путь от a до b. Итак, если предположить, что существует возможное остовное дерево, есть корень r, из которого вы можете перейти к каждому v в V. при итерации, когда r выбрано в качестве корня, существует путь от r к каждому v в V, поэтому будет — путь от r к нему в остовном дереве.