Первый поиск по ширине и первый поиск по глубине

Question

Кто-нибудь может дать ссылку для простого объяснения BFS и DFS с его реализацией?

Answer 1

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

Answer 2

Допустим, вы получили следующую структуру:

Format: Node [Children]

A [B C D]
B [E F]
C [G]
D []
E []
F []
G []

Сначала поиск в ширину посещает всех детей узла, а затем посещает их. Вот псевдокод и решение для вышеуказанной структуры:

1. Enqueue root node.
2. Dequeue and output. If the queue is empty, go to step 5.
3. Enqueue the dequeued node's children.
4. Go to Step 2.
5. Done

Two queues: (Active Node) [Output] [Working Set]
Starting with root:
( ) []              [A]
(A) [A]             [B C D] 
(B) [A B]           [C D E F] 
(C) [A B C]         [D E F G] 
(D) [A B C D]       [E F G] 
(E) [A B C D E]     [F G] 
(F) [A B C D E F]   [G] 
(G) [A B C D E F G] [] 

Done

Сначала поиск по глубине сначала посещает самый низкий уровень (самые глубокие дочерние элементы) дерева. Существует два типа глубинного поиска: предварительный заказ и пост-заказ. Это просто различие между тем, когда вы добавляете узел к выводу (когда вы посещаете его, а не покидаете его).

    var rootNode = structure.getRoot();
    var preOrder = new Array();
    var postOrder = new Array();
    function DepthFirst( rootNode ){
        // Pre-order
        preOrder[ preOrder.length ] = rootNode;

        for( var child in rootNode ){
            DepthFirst( child );
        }

        // Post-order
        postOrder[ postOrder.length ] = rootNode;
    }

Pre-order:
* A B E F C G D

Post-order:
* E F B G C D A

Answer 3

Скажем, у вас есть дерево следующим образом:

альтернативный текст http://i40.tinypic.com/289aslh.jpg

Это может немного сбивать с толку, потому что E является одновременно дочерним для A и F, но это помогает проиллюстрировать глубину в глубине первого поиска. Поиск в глубину ищет дерево, идущее настолько глубоко (отсюда и термин глубина), насколько это возможно. Таким образом, обход слева направо будет A, B, D, F, E, C, G.

Поиск в ширину оценивает сначала всех детей, прежде чем перейти к детям детей. Таким образом, то же дерево будет идти A, B, C, E, D, F, G.

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

Answer 4

вы можете найти все на вики:

BFS и DFS

эта ссылка также может быть полезна. если вам нужна реализация, перейдите по ссылке: библиотека поддержки c ++: DFS

Answer 5

Вот несколько ссылок для проверки:

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

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

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

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

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

Answer 6

Анимация при первом поиске / глубина при первом поиске

Answer 7

фрагмент с 2 указателями.

void BFS(int v,struct Node **p)
{
     struct Node *u;

     visited[v-1] = TRUE;
     printf("%d\t",v);
     AddQueue(v);

     while(IsEmpty() == FALSE)
     {
         v = DeleteQueue();
         u = *(p+v-1);

         while(u!=NULL)
         {
            if(visited(u->data -1) == FALSE)
            {
                  AddQueue(u->data);
                  visited[u->data -1]=TRUE;
                  printf("%d\t",u->data);
            }

            u = u->next;
         }
     }
}

Answer 8

Вот основная идея:

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

Answer 9

обход графа с помощью dfs и bfs.

in c ++ и python .

Answer 10

Прежде всего, BFS и DFS - это два способа реализации обхода двоичного дерева. Breadth First означает прохождение порядка уровня. У Depth First есть три способа реализации -,,.

Предзаказ:

a. Start with root,
b. mark it visited,
c. go to left node
d. (b) - mark it visited
e. Repeat (c) till there is not any new left node remaining
 (We are/might be at leaf node at this point,)
f. Is there any right node available? If yes, go to (a).

Уровень Порядок обхода Сложность времени O (n) - Количество посещений каждого узла - только 1, означает, что всего n раз.

Космическая сложность- Лучший вариант: дерево только левых узлов, является O (1) Средний случай: например, идеальное двоичное дерево, n / 2 число узлов, O (n)