Рубрики

Алгоритмы | Граф Обходы | Вопрос 12

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

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

Ответ: (с)
Пояснение: Опция (A) — MNOPQR. Это не может быть BFS, так как обход начинается с M, но O посещается до N и Q. В BFS все соседние должны посещаться до смежных с соседними.

Вариант (B) является NQMPOR. Это также не может быть BFS, потому что здесь P посещается до O.

(C) и (D) совпадают до QMNP. Мы видим, что M был добавлен в очередь до N и P (потому что M предшествует NP в QMNP). Поскольку R является соседом M, он добавляется в очередь раньше, чем соседний с N и P (который является O). Таким образом, R посещается до О.

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

Алгоритмы | Граф Обходы | Вопрос 12

0.00 (0%) 0 votes