Самый короткий путь: DFS, BFS или оба?

Question

Я знаю, что только BFS может найти кратчайший путь на невзвешенном графике, но я также читал на нескольких сайтах, где люди утверждали, что BFS или DFS могут это сделать. Я просто хотел подтвердить, что это, вероятно, ошибки и что только BFS может это сделать (я не был полностью уверен даже после быстрого поиска Google). Если я ошибаюсь, может кто-то объяснить, как DFS может дать кратчайший путь.

Answer 1

DFS не обязательно дает кратчайшие пути в неориентированном графе. BFS будет правильным выбором здесь.

В качестве примера рассмотрим график, образованный путем взятия углов треугольника и их соединения. Если вы попытаетесь найти кратчайший путь от одного узла к другому с помощью DFS, тогда вы получите неправильный ответ, если не будете следовать краю, напрямую связанному с начальным и целевым узлами.

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

Answer 2

Итеративный поиск углубления (IDS), который состоит из множества раундов поиска по глубине (в основном DFS, но прекратите поиск, если вы достигли предела глубины d), которые постепенно увеличивают глубину от 1, найдут кратчайший путь в невзвешенном графике.

// Iterative deepening search 
// isGoal is a function that checks whether the current node is the goal 
function ids(graph, start, isGoal) { 
    maxDepth = 1 
    do { 
     found = dls(graph, start, isGoal, maxDepth, 0) 
     // Clear the status whether a node has been visited 
     graph.clearVisitedMarker(); 
     // Increase maximum depth 
     depth = depth + 1 

    // You can slightly modify the dls() function to return whether there is a 
    // node beyond max depth, in case the graph doesn't have goal node. 
    } while (found == null) 

    return found 
} 

// Depth-limited search 
// isGoal is a function that checks whether the current node is the goal 
function dls(graph, currentNode, isGoal, maxDepth, currentDepth) { 
    if (graph.visited(currentNode)) { 
     return null 
    } 
    graph.setVisited(currentNode) 

    if (isGoal(currentNode)) { 
     return currentNode 
    } 

    // Stop searching when exceed max depth 
    // This is the only difference from DFS 
    if (currentDepth >= maxDepth) { 
     return null 
    } 

    for (adjNode in graph.getAdjacent(currentNode)) { 
     found = dls(graph, adjNode, goal, maxDepth, currentDepth + 1) 
     if (found != null) { 
      return found 
     } 
    } 

    return null 
} 

Это работает, так как вы постепенно увеличивать допустимую длину от начального узла: узел, который имеет расстояние а + 1 не будет изучаться перед узлом, который имеет расстояние а, из-за лимита на глубину.

Общая проблема заключается в том, что узлы с расстоянием a будут повторно посещены (d - a + 1) раз, где d - глубина кратчайшего пути к цели. Это зависит от графика или дерева поиска, если мы хотим поговорить о производительности. В дереве поиска с большим коэффициентом ветвления узлы, сгенерированные на глубине d, становятся доминирующим, поэтому проблемы с переходом не так уж много. BFS непригодна для такого случая из-за требования к экспоненциальному пространству, но IDS будет использовать только полиномиальное пространство.

Answer 3

Оба BFS и DFS будут давать кратчайший путь от A до B, если вы внесли правильный.

Давайте рассмотрим весь график как дерево. В основном, BFS будет запускать каждый уровень дерева и определять путь, пройдя все уровни. В отличие от этого, DFS будет работать с каждым узлом листа и узнать путь, когда пересекает узел по этому пути. Оба они используют поиск путей поиска выходов, поэтому оба они гарантируют поиск кратчайшего пути, если вы правильно выполнили эти алгоритмы.

Плюсы и минусы использования BFS и DFS является следующее:

BFS, использует больше памяти, пройти все узлы

DFS, использует меньше памяти, может быть немного быстрее, если вам повезет, чтобы выбрать путь узла листа содержит интересующий вас узел. (Не обязательно проходить все узлы).

Answer 4

Перспектива для понимания: BFS на графике без веса и направления совпадает с Dijkstra (вес = 1, в одном направлении), поэтому понимание того, почему Dijkstra прав, может помочь. Более подробная информация будет добавлена, если я ее пропустил.