Утверждение:
"Рассмотрим произвольный граф G = (V, E) и исходную вершину s, которая находится в V. Для каждого дерева кратчайших путей, укорененного в s, существует упорядочение вершин впредставление списка смежности G, которое приводит именно к этому дереву кратчайших путей, когда BFS запускается из s. "
Я изо всех сил пытаюсь придумать контрпример для этого утверждения, которое я принял за номинальную стоимостьбыть ЛОЖНЫМ.
Я понимаю, что порядок имеет значение, когда дело доходит до дерева кратчайших путей, полученного из BFS, при условии, что порядок вершин в списке смежности является порядком, который следует за BFS, но не может показаться, чтоПодумайте о контрпримере, который нарушает это утверждение.
Редактировать: Я не спрашиваю, как найти другие пути кратчайшего дерева, но пример, который показывает, что существуют ДРУГИЕ пути кратчайшего дерева, которые не найденыпо BFS.