ні з s вершини множини V. Алгоритм припиняє свою роботу після обходу всіх вершин графа, або у разі виконання наявного умови.
Розглядаючи наступний приклад, будемо вважати, що в процесі роботи алгоритму кожна з вершин графа може бути забарвлена ??в один з трьох кольорів: чорний, білий або сірий. Спочатку всі вершини білі. У процесі обходу кожна з вершин, у міру виявлення, забарвлюється спочатку в сірий, а потім у чорний колір. Певний момент обходу описує наступні умову: якщо вершина чорна, то всі її нащадки пофарбовані в сірий або чорний колір.
Маємо змішаний граф (див. рис.) з | V |=4 і | E |=5. Виконаємо обхід його вершин, використовуючи алгоритм пошуку в ширину. У якості стартової вершини візьмемо вузол 3. Спочатку він позначається сірим як виявлений, а потім чорним, оскільки виявлені суміжні з ним вузли (1 і 4), які, у свою чергу, в зазначеному порядку позначаються сірим. Наступним в чорний забарвлюється вузол 1, і знаходяться його сусіди - вузол 2, який стає сірим. І, нарешті, вузли 4 і 2, в даному порядку, проглядаються, обхід в ширину завершується.
Алгоритм пошуку в ширину працює як на орієнтованих, так і на неорієнтованих графах. Дати зрозуміти це був покликаний змішаний граф, використовуваний в прикладі. Варто відзначити, в неорієнтованому зв'язкового графі даний метод обійде всі наявні вузли, а в змішаному або орграфе це необов'язково станеться. До того ж, досі розглядався обхід всіх вершин, але цілком імовірно, достатнім виявиться, наприклад перегляд певної їх кількості, або знаходження конкретної вершини. У такому випадку доведеться трохи пристосувати алгоритм, а не змінювати його повністю або зовсім відмовитися від використання такого.
Тепер перейдемо до більш формального опису алгоритму пошуку в ширину. Основними об'єктами - трьома структурами даних, задіяними в програмі, будуть:
· матриця суміжності графа GM;
· чергу queue;
· масив відвіданих вершин visited.
Дві перші структури мають цілочисельний тип даних, остання - логічний. Відвідані вершини, заносяться в масив visited, що запобіжить зациклення, а черга queue буде зберігати задіяні вузли. Нагадаємо, що структура даних чергу працює за принципом перший прийшов - першим вийшов raquo ;. Розглянемо розбитий на етапи процес обходу графа:
. масив visited обнуляється, тобто жодна вершина графа ще не переглянуло;
2. в якості стартової, вибирається деяка вершина s і поміщається в чергу (в масив queue);
. вершина s досліджується (позначається як відвідана), і всі суміжні з нею вершини поміщаються в кінець черги, а сама вона віддаляється;
. якщо на даному етапі чергу виявляється порожньою, то алгоритм припиняє свою роботу; інакше відвідується вершина, що стоїть на початку черги, позначається як відвідана, і всі її нащадки заносяться в кінець черги;
. пункт 4 виконується поки це можливо.
Пошук в ширину, починаючи зі стартовою вершини, поступово йде від неї все далі і далі, проходячи рівень за рівнем. Виходить, що по закінченню роботи алгоритму будуть знайдені всі найкоротші шляхи з початкової вершини до кожного доступного з неї вузла.
1.1 Неформальне опис
1. Помістити вузол, з якого починається пошук, в спочатку порожню чергу.
2.Ізвлечь з початку черги вузол і позначити його як розгорнутий.
oЕслі вузол є цільовим вузлом, то завершити пошук з результатом успіх .
oв іншому випадку, в кінець черги додаються всі наступники вузла, які ще не розгорнуті і не перебувають у черзі.
3. Якщо чергу порожня, то всі вузли зв'язного графа були переглянуті, отже, цільової вузол недосяжний через початкового; завершити пошук з результатом невдача raquo ;.
4. Повернутися до п.2.
Малюнок 1.1 - Білий - вершина, яка ще не виявлена. Сірий - вершина, вже виявлена ??і додана в чергу. Чорний - вершина, витягнута з черги
1.2 Формальний опис
Нижче наведено псевдокод алгоритму для випадку, коли необхідно лише знайти цільової вузол. Залежно від конкретного застосування алгоритму, може знадобитися додатковий код, що забезпечує збереження потрібної інформації (відстань від початкового вузла, вузол-батько і т.п.)
Рекурсивна формулювання:
BFS ( start_node , goal_node ) {
return BFS '({ start_node },?, goal_node );
} '( fringe ...
