Сначала ширина против глубины

StackOverflow https://stackoverflow.com/questions/687731

Вопрос

При обходе дерева/графа в чем разница между «сначала в ширину» и «сначала в глубину»?Любые примеры кодирования или псевдокода были бы великолепны.

Это было полезно?

Решение

Эти два термина различают два разных способа ходьбы по дереву.

Вероятно, проще всего просто продемонстрировать разницу.Рассмотрим дерево:

    A
   / \
  B   C
 /   / \
D   E   F

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

A, B, D, C, E, F

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

А широта первый обход будет посещать узел в этом порядке

A, B, C, D, E, F

Здесь мы работаем до конца через каждый уровень перед спуском.

(Обратите внимание, что в порядках обхода есть некоторая двусмысленность, и я схитрил, чтобы сохранить порядок «чтения» на каждом уровне дерева.В любом случае я мог бы добраться до Б до или после С, и точно так же я мог бы добраться до Е до или после F.Это может иметь или не иметь значения, зависит от вашего приложения...)

Оба вида обхода могут быть достигнуты с помощью псевдокода:

Store the root node in Container
While (there are nodes in Container)
   N = Get the "next" node from Container
   Store all the children of N in Container
   Do some work on N

Разница между двумя порядками обхода заключается в выборе Container.

  • Для сначала глубина используйте стек.(Рекурсивная реализация использует стек вызовов...)
  • Для в ширину используйте очередь.

Рекурсивная реализация выглядит так

ProcessNode(Node)
   Work on the payload Node
   Foreach child of Node
      ProcessNode(child)
   /* Alternate time to work on the payload Node (see below) */

Рекурсия заканчивается, когда вы достигаете узла, который не имеет потомков, поэтому она гарантированно заканчивается для конечные, ациклические графы.

На этом этапе я все же немного схитрил.Проявив немного смекалки, вы также можете работа над узлы в следующем порядке:

D, B, E, F, C, A

это вариант подхода «сначала в глубину», когда я не выполняю работу в каждом узле, пока не поднимусь обратно вверх по дереву.однако у меня есть посетил высшие узлы на пути вниз, чтобы найти своих детей.

Этот обход вполне естественен в рекурсивной реализации (используйте строку «Альтернативное время» выше вместо первой строки «Работа»), а не слишком сложно, если вы используете явный стек, но я оставлю это в качестве упражнения.

Другие советы

Разбираемся в терминах:

Эта картинка должна дать вам представление о контексте, в котором слова широта и глубина используются.

Understanding Breadth and Depth

Поиск в глубину:

Depth-First Search

  • Алгоритм глубокого поиска действует так, как если бы он хотел получить как можно дальше от начальной точки как можно быстрее.

  • Обычно используется Stack помнить, куда ему следует идти, когда он заходит в тупик.

  • Правила, которым следует следовать:Нажмите первую вершину A на Stack

    1. Если возможно, посетите соседнюю непосещенную вершину, пометьте ее как посещенную и поместите в стек.
    2. Если вы не можете следовать Правилу 1, то, если возможно, извлеките вершину из стека.
    3. Если вы не можете следовать Правилу 1 или Правилу 2, все готово.

  • Java-код:

    public void searchDepthFirst() {
    // Begin at vertex 0 (A)
    vertexList[0].wasVisited = true;
    displayVertex(0);
    stack.push(0);
    while (!stack.isEmpty()) {
        int adjacentVertex = getAdjacentUnvisitedVertex(stack.peek());
        // If no such vertex
        if (adjacentVertex == -1) {
            stack.pop();
        } else {
            vertexList[adjacentVertex].wasVisited = true;
            // Do something
            stack.push(adjacentVertex);
        }
    }
    // Stack is empty, so we're done, reset flags
    for (int j = 0; j < nVerts; j++)
        vertexList[j].wasVisited = false;
}

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

Поиск в ширину:

Breadth-First Search

  • Алгоритм поиска по ширине предпочитает оставаться как можно ближе к отправной точке.
  • Этот вид поиска обычно реализуется с помощью Queue.
  • Правила, которым следует следовать:Сделать начальную вершину A текущей вершиной
    1. Посетите следующую непосещенную вершину (если она есть), примыкающую к текущей вершине, отметьте ее и вставьте в очередь.
    2. Если вы не можете выполнить Правило 1, поскольку непосещенных вершин больше нет, удалите вершину из очереди (если возможно) и сделайте ее текущей вершиной.
    3. Если вы не можете выполнить Правило 2, потому что очередь пуста, все готово.

  • Java-код:

    public void searchBreadthFirst() {
    vertexList[0].wasVisited = true;
    displayVertex(0);
    queue.insert(0);
    int v2;
    while (!queue.isEmpty()) {
        int v1 = queue.remove();
        // Until it has no unvisited neighbors, get one
        while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {
            vertexList[v2].wasVisited = true;
            // Do something
            queue.insert(v2);
        }
    }
    // Queue is empty, so we're done, reset flags
    for (int j = 0; j < nVerts; j++) 
        vertexList[j].wasVisited = false;
}

  • Приложения:Поиск в ширину сначала находит все вершины, находящиеся на расстоянии одного ребра от начальной точки, затем все вершины, находящиеся на расстоянии двух ребер, и так далее.Это полезно, если вы пытаетесь найти кратчайший путь от начальной вершины до заданной вершины.

Надеюсь, этого будет достаточно для понимания поиска в ширину и в глубину.Для дальнейшего чтения я бы порекомендовал главу «Графы» из превосходной книги Роберта Лафоре о структурах данных.

Учитывая это двоичное дерево:

enter image description here

Обход в ширину:
Пройдите через каждый уровень слева направо.

«Я G, мои дети D и I, мои внуки B, E, H и K, их внуки A, C, F»

- Level 1: G 
- Level 2: D, I 
- Level 3: B, E, H, K 
- Level 4: A, C, F

Order Searched: G, D, I, B, E, H, K, A, C, F

Обход в глубину:
Обход не выполняется ПО ВСЕМ уровням одновременно.Вместо этого обход сначала погружается в ГЛУБИНУ (от корня к листу) дерева.Однако это немного сложнее, чем просто вверх и вниз.

Существует три метода: 

1) PREORDER: ROOT, LEFT, RIGHT.
You need to think of this as a recursive process:  
Grab the Root. (G)  
Then Check the Left. (It's a tree)  
Grab the Root of the Left. (D)  
Then Check the Left of D. (It's a tree)  
Grab the Root of the Left (B)  
Then Check the Left of B. (A)  
Check the Right of B. (C, and it's a leaf node. Finish B tree. Continue D tree)  
Check the Right of D. (It's a tree)  
Grab the Root. (E)  
Check the Left of E. (Nothing)  
Check the Right of E. (F, Finish D Tree. Move back to G Tree)  
Check the Right of G. (It's a tree)  
Grab the Root of I Tree. (I)  
Check the Left. (H, it's a leaf.)  
Check the Right. (K, it's a leaf. Finish G tree)  
DONE: G, D, B, A, C, E, F, I, H, K  

2) INORDER: LEFT, ROOT, RIGHT
Where the root is "in" or between the left and right child node.  
Check the Left of the G Tree. (It's a D Tree)  
Check the Left of the D Tree. (It's a B Tree)  
Check the Left of the B Tree. (A)  
Check the Root of the B Tree (B)  
Check the Right of the B Tree (C, finished B Tree!)  
Check the Right of the D Tree (It's a E Tree)  
Check the Left of the E Tree. (Nothing)  
Check the Right of the E Tree. (F, it's a leaf. Finish E Tree. Finish D Tree)...  
Onwards until...   
DONE: A, B, C, D, E, F, G, H, I, K  

3) POSTORDER: 
LEFT, RIGHT, ROOT  
DONE: A, C, B, F, E, D, H, K, I, G

Использование (то есть, почему нас это волнует):
Мне очень понравилось это простое объяснение на Quora методов обхода в глубину и того, как они обычно используются:
«Обход по порядку будет печатать значения [в порядке BST (двоичное дерево поиска)]»
«Обход по предварительному заказу используется для создания копии [двоичного дерева поиска]».
«Обход постпорядка используется для удаления [двоичного дерева поиска]».
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing

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

Лично мне нравится интерпретация BFS как затопления ландшафта:Сначала будут затоплены низменные районы, а уже потом - высокогорные.Если вы представите высоты ландшафта в виде изолиний, как мы видим в учебниках по географии, легко увидеть, что BFS одновременно заполняет всю область под одной и той же изолинией, как это было бы в физике.Таким образом, интерпретация высот как расстояния или масштабированной стоимости дает довольно интуитивное представление об алгоритме.

Имея это в виду, вы можете легко адаптировать идею поиска в ширину, чтобы легко найти минимальное остовное дерево, кратчайший путь, а также многие другие алгоритмы минимизации.

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

Итак, для меня разница между ними заключается в том, какое природное явление лучше всего соответствует модели их распространения (трансверсации) в реальной жизни.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top