Применение BFS на дереве, чтобы найти самый длинный путь между двумя вершинами
В дереве я должен найти две вершины, между которыми есть максимальное число вершин (связанных), включая обе. Затем мне нужно найти общее количество вершин между ними. Я хочу подойти к этой проблеме, используя алгоритм поиска по ширине, но не получая никакой подсказки. Как справиться с этим?
пример (для 5 узлов) — ссылки на дерево:
1-2
1-3
3-4
3-5
тогда самый длинный путь
2-1-3-4 или 2-1-3-5
таким образом, этот путь имеет всего 4 вершины.
Решение
Самый простой способ — использовать матрицу смежности.
Идея состоит в том, чтобы сделать матрицу смежности для каждого узла, сделав его исходным узлом, т.е. в вашем примере всего 5.
Затем перейдите к каждой матрице и найдите максимальное количество подключенных узлов для этого узла. Поместите путь отслеживания наибольшего значения в стек для дальнейшего использования.
Повторяйте этот процесс, пока вы не охватите всю матрицу. Сравните результаты со всей матрицы. Выбирается тот, у кого наибольшее значение, а соответствующее ему значение в стеке — заданный путь.
Это также можно решить с помощью динамического программирования. Пожалуйста, смотрите ссылку ниже, которая объясняет алгоритм Floyds Warshall. Пожалуйста, посмотрите, как он находит кратчайший путь с помощью динамического программирования. Вы можете настроить его, чтобы найти решение своей проблемы с помощью DP.
http://www.youtube.com/watch?v=EMAoMMsA5Jg
-Bhupesh
Другие решения
Поскольку это дерево, запуск BFS с любого исходного узла просто вернет то же дерево с вашим источником в качестве root (в отличие от общего графа, где BFS может игнорировать ребра, которые создают более короткий путь между двумя узлами, которые вы хотите сравнить ).
Вы хотите две самые дальние вершины, для любого данного корня, они могут быть на разных ветвях (в этом случае вы можете найти самый дальний лист на каждом плече), или они могут быть на одной ветке (в этом случае вы могли бы продолжить на это поддерево. Однако это включает в себя форму DP, которая немного больше, чем одна BFS.
Вы можете попытаться запустить один запуск BFS из произвольного корня, добавить обратные ребра (каждый дочерний элемент указывает на отца), а затем распространить обратно самый длинный найденный лист в каждой ветви на родительский. По пути вверх вычислите максимальное расстояние для каждого поддерева в пути, и, если родитель имеет более высокую доступность дерева из-за расстояния между ветвями — замените локальный максимум.
Я должен признать, однако, что на данный момент отличие от просто BFS является довольно существенным.
detector