Рубрики

ВОРОТА | GATE CS 2008 | Вопрос 17

Алгоритм поиска в ширину был реализован с использованием структуры данных очереди. Один из возможных порядков посещения узлов следующего графа

(A) MNOPQR
(B) NQMPOR
(C) QMNPRO
(D) QMNPOR

Ответ: (с)
Объяснение: Поиск в ширину сначала посещает «ширину», т. Е. Если он посещает узел, то после посещения этого узла он сначала посещает соседние узлы (дочерние узлы), прежде чем перейти к соседям следующего уровня.

Посмотрим как.

Первоначально: если BFS начинается с узла Q, он сначала посещает Q и помещает Q в очередь.

Итак, очередь содержит: Q.

И, порядок посещения еще: Q.

Теперь он удаляет Q и исследует своих соседей: {M, N, P}. Он проверяет тех соседей Q, которые еще не посещены, затем посещает их и помещает их в очередь (чтобы позже можно было посетить их соседей).

Теперь эти соседи можно посещать и помещать их в очередь в любом порядке (зависит от реализации).

Предположим, что он посещает и помещает их в очередь в порядке (MNP), где M находится на переднем, а P на заднем.

Итак, порядок посещения: QMNP.

Теперь он ищет следующую запись в очереди. Поскольку очередь следует принципу FIFO, M снимается с производства.

Очередь содержит: (NP)

Он исследует M, находит своих соседей {N, Q, R}, но перед их посещением проверяет, были ли они посещены ранее, он только посещает и помещает в очередь те узлы, которые еще не посещены. Поскольку N и Q были посещены ранее, он только посетит R и поставит его в очередь.

Порядок посещения: QMNPR.
Очередь содержит: (NPR).

Теперь N снимается с производства.

Очередь содержит: (PR).

Он исследует N, находит своих соседей {M, O, Q}. Поскольку M и Q были посещены ранее, он только посетит и поставит в очередь O.

Порядок посещения: QMNPRO.
Очередь содержит: (PRO).

Теперь P снимается с производства.

Очередь содержит: (RO).

Он исследует P, находит своих соседей {O, Q}. Поскольку O и Q были посещены ранее, он НЕ будет поставлен в очередь.

Теперь R снимается с производства.

Очередь содержит: (O).

Он исследует R, находит своего соседа {M}. Поскольку M был посещен ранее, он не будет поставлен в очередь.

Теперь, O снят с производства.

Очередь содержит: ().

Он исследует O, находит своих соседей {N, P}. Поскольку оба были посещены ранее, это не будет ставить в очередь.

Теперь очередь пуста, поэтому BFS останавливается здесь.

И порядок посещения был: QMNPRO.

Псевдокод для приведенного выше объяснения можно найти по адресу https://en.wikipedia.org/wiki/Breadth-first_search
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE CS 2008 | Вопрос 17

0.00 (0%) 0 votes