На этом шаге мы рассмотрим этот алгоритм.
В приведённой ниже записи нерекурсивного алгоритма поиска в ширину на графе [1, с.125-126] предполагается, что:
- (1) зафиксирован некоторый линейный порядок на множестве всех вершин графа;
- (2) множество вершин, смежных со всякой вершиной графа, также линейно упорядочено.
while (Имеется хотя бы одна непосещённая вершина)
{
Пусть p - первая из непосещённых вершин.
Посетить вершину p и поместить её в пустую очередь S;
while (Очередь S непуста)
{
Пусть p - вершина, находящаяся на верхушке очереди S;
if (Вершина p имеет непосещённые смежные вершины)
{
Пусть q - первая непосещённая вершина из вершин,
смежных вершине p. Пройти по ребру (p,q), посетить
вершину q и поместить её в очередь S
}
else Удалить вершину p из очереди S
}
}
Замечание. Алгоритмы поиска в ширину на графе изложены в монографиях [2, с.198-205], [3, с.92-94].
(1)Касьянов В.H., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ. - М.: Наука, 1986. - 272 с.
(2)Пападимитриу Х., Стайнглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985. - 512 с.
(3)Липский В. Комбинаторика для программистов. - М.: Мир, 1988. - 213 с.
На следующем шаге мы рассмотрим вычисление компонентов связности графа.
