07.06.255. Поиск путей - justjune/AiSD2026 GitHub Wiki

Дерево открытий

Перед прочтением данного подраздела рекомендуется ознакомиться с предыдущим (см. 07.06.254. Применение обхода )

В процедуре bfs можно реализовать заполнение некоего массива parent таким образом, чтобы вершина, у которой связанная вершина i ещё не была обработана, определялась как parent[i] . Так каждая вершина, кроме начальной (корневой), в результате обхода будет иметь "родителя" (у корневой вершины его можно задать номером -1), а весь массив задаст дерево открытий.

Это дерево обладает одним важным свойством: однозначно определённый путь от корня до любой вершины x использует наименьшее возможное число ребер текущего графа.

Применение дерева открытий

С помощью дерева открытий можно легко воссоздать путь от вершины x к корню по направлению, обратному тому, что используется в процедуре bfs. Чтобы это реализовать, можно либо сохранить путь и явно обратить его с помощью стека, либо написать рекурсию, как сделано в листинге 7.13:

void find_path(int start, int end, int parents[]){
    if((start == end) || (end == -1)){           //конец "прямого хода" рекурсии
        printf("\n%d", start);                   //начало вывода вершин
    }
    else{
        find_path(start, parents[end], parents); //продолжение "прямого хода" рекурсии
        printf(" %d", end);                      //вывод текущей вершины во время "обратного хода" рекурсии
    }
}

Нужно иметь ввиду, что дерево кратчайшего пути полезно только тогда, когда корнем поиска в ширину является вершина x. А ещё поиск в ширину даёт кратчайший путь только для невзвешенных графов. Для взвешенных графов нужны алгоритмы из разд. 8.3.1.