Как построить дерево BFS после запуска BFS на неориентированном графике?

Question

У меня есть неориентированный граф, и из него я перерисовываю один и тот же граф, но в древовидной структуре (с уровнями). Я знаю, как работает алгоритм Breadth First Search (BFS), но я не уверен, как выполнить переход из графика -> tree.

Здесь, в this Wikipedia article, если вы прокрутите вниз немного, вы увидите две фотографии немецких городов. Даже после прочтения кода pseduo там я просто не понимаю, как вы получаете от первого снимка до второго.

Answer 1

Один стандартный способ получить дерево BFS из графика - запустить BFS и, как вы это делаете, сохранить таблицу, сопоставляющую каждый узел в графе с его родителем в дереве. Вы заполняете его следующим образом: исходный узел не имеет родителя (в конце концов, это корень). Затем, всякий раз, когда вы обрабатываете узел u и исследуете один из его неизведанных соседей v, вы устанавливаете родительский элемент v как u. Попробуйте проследить это на некоторых небольших примерах, и вы увидите, что это неявно создает дерево, за исключением того, что края идут назад (края указывают от детей до родителей, а не наоборот). Затем вы можете просто перевернуть ребра, чтобы вернуть дерево BFS.

Надеюсь, это поможет!