ст (англ. Tail). Елемент, что додається до Черги, опіняється в ее хвості. Елемент, что відаляється з Черги, знаходиться в ее Голові. Така черга Повністю аналогічна звічній базарній черзі, в Якій хто перший вставши в неї, тієї Першів буде обслужених (альо, На Відміну Від реальної Черги, імовірність пройти поза черго віключена)
Основні Операції з черго:
lt; # justify gt;
Процедура BFS працює таким чином. У рядках 1-4 усіх вершини, за вінятком початкової вершини s, забарвлюються в білий колір, для кожної вершини u полю d [u] прівласнюється значення? Виконував і як батьку для кожної вершини встановлюється nil. У рядку 5 початкова вершина s забарвлюється в сірий колір, оскількі вон розглядається як Відкрита на качана процедури. У рядку 6 ее полю прівласнюється значення 0, а в рядку 7 ее батьком становится nil. У рядках 8-9 створюється порожня черга Q, в якові поміщається одна елемент s.
Цикл while в рядках 10-18 віконується до тихий пір, поки залішаються сірі вершини (тобто відкриті, но списки суміжності якіх галі не проглянуті). Інваріант цього циклу Виглядає таким чином: При віконанні перевіркі в рядку 10 черга Q складається з множини сіріх вершин.
Легко Побачити, что ВІН віконується перед Першів ітерацією І що Кожна ітерація циклу зберігає інваріант. Перед Першів ітерацією Єдиною сірою вершиною и Єдиною верховіттям у черзі Q, являється початкова вершина s. У рядку 11 візначається сіра вершина u в Голові Черги Q, яка потім віддаляється з Черги. Цикл for в рядках 12-17 переглядає усі вершини v в списку суміжності u. Если вершина v біла, значити, вон галі не Відкрита, и алгоритм відкріває ее, віконуючі рядки 14-17. Вершіні прізначається сірий колір, ДИСТАНЦІЯ d [v] встановлюється рівною d [u] + 1, а як ее батьку вказується вершина u. После цього вершина поміщається в хвіст черги Q. После того, як усі вершини Із списку суміжності u проглянуті, вершіні u прівласнюється чорний колір. Інваріант циклу зберігається, оскількі усі вершини, Які забарвлюються в сірий колір (рядок 14), вносяться до Черги (рядок 17), а вершина, яка віддаляється з Черги (рядок 11), забарвлюється в чорний колір (рядок 18).
Результат поиска завширшки может залежаться від порядку перегляду вершин, суміжніх з цією вершиною, в рядку 12. Дерево поиска завширшки может змінюватісь, но відстані d, вічіслені алгоритмом, що не залежався від порядку перегляду.
Оцінімо годину роботи алгоритму для вхідного графа G=(V, E). После ініціалізації Жодна вершин не забарвлюється в білий колір, тому перевірка в рядку 13 гарантує, что Кожна вершина вноситися до Черги НЕ более одного разу, а отже, и віддаляється з Черги вона НЕ более одного разу. Операції Внесення до Черги и відалень з неї вімагають O (1) годині, так что загальний годину операцій з черго складає О (V). Оскількі КОЖЕН список суміжності сканується только при відаленні відповідної вершини з Черги, КОЖЕН список сканується НЕ более одного разу. Оскількі сума довжина усіх Списків суміжності рівна? (Е), загальний годину, необхідній для сканування Списків, Рівний О (Е). Накладні витрати на ініціалізацію Рівні О (V), так что загальний годину роботи процедури BFS складає Про (V + Е). Таким чином, годину поиска завширшки лінійно покладів від розміру представлення графа G з використанн Списків суміжності.
Поиск завширшки зазвічай вікорістовується для визначення Довжина найкоротшіх Шляхів (і пов'язаного з ними графа передування) з цієї вершини. Під Довжина розуміється Кількість ребер между вершинами.
. 2 Поиск в глибино
Стратегія пошуку в глибино, як віпліває з ее назви, Полягає в тому, щоб йти угліб графа, наскількі це можливо. При віконанні пошуку в глибино досліджуються усі ребра, что Виходять з вершини, Відкритої останньої, и покідає вершину, только коли не залішається недослідженіх ребер - при цьом відбувається повернення у вершину, з якої булу Відкрита вершина V. Цей процес продовжується до тихий пір, поки НЕ БУДУТЬ відкриті усі вершини, досяжні з початкової. Если при цьом залішаються невідкріті вершини, то одна з них вібірається в якості новой початкової вершини и поиск повторюється уже з неї. Цей процес повторюється до тихий пір, поки НЕ БУДУТЬ відкриті усі вершини. Алгоритм зазвічай Використовують в якості підпрограмі в алгоритмах поиска одне - та двозвязніх компонент, топологічного сортуваннях.
Як и у разі поиска завширшки, коли вершина V відкрівається в процессе сканування списку суміжності Вже Відкритої вершини u, процедура поиска запісує Цю подію, встановлюючі поле попередника v? [v] рівнім u. На Відміну Від поиска завширшки, де підграф передування утворює дерево, при пошуку в глибино підграф передування может складатіся з декількох дерев, оскількі поиск может Виконуват...
