Модификация алгоритма поиска в глубину с использованием матрицы смежности для поиска определенного конечного узла

Question

Итак, у меня есть матрица смежности размером N x N для графа с N узлами. Я хотел бы провести Поиск в глубину по этой матрице, чтобы определить, существует ли путь от узла Source до узла Destination или нет. Если он существует, я бы хотел напечатать путь.

В приведенном ниже псевдокоде используется матрица / график G, чтобы найти все вершины, к которым можно получить доступ с начального узла v. Как бы я изменил этот алгоритм, чтобы у меня было что-то похожее на это: procedure DFS(G,v,d), где d - целевой узел, который я ищу?

procedure DFS(G,v):
    label v as discovered
    for all edges from v to w in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
            recursively call DFS(G,w)

Кроме того, в качестве идентификатора, как бы я добавил возможность возвращать общий вес всех ребер для пути, который он обнаружил?

Answer 1

Алгоритм необходимо изменить двумя способами

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

В приведенном ниже псевдокоде переменная пути P начинается как пустой список. Когда пункт назначения найден, узел назначения помещается в P. Затем, когда возвращается каждый уровень рекурсии, текущий путь w добавляется к пути. Когда возвращается вызов верхнего уровня, P содержит полный путь. Есть только одна проблема, путь обратный: пункт назначения к источнику. Так что вам придется перевернуть его.

procedure DFS(G,v,d,P=empty):
    if v equals d
        initialize P with d
        return P
    label v as discovered
    for all edges from v to w in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
            recursively call DFS(G,w,d,P)
            if P is not empty
                append v to P
                return P
    return empty