На этом шаге мы рассмотрим.этот алгоритм.
В приведённой ниже записи нерекурсивного алгоритма поиска в глубину на графе [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, с.361-364], [3, с.88-91], [4, с.198-205], [5, с.323-327].
(1)Касьянов В.H., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ. - М.: Наука, 1986. - 272 с.
(2)Рейнгольд Э. 3, Hивергельт Ю. 3, Део H. Комбинаторные алгоритмы. Теория и практика. - М.: Мир, 1980. - 476 с.
(3)Липский В. Комбинаторика для программистов. - М.: Мир, 1988. - 213 с.
(4)Пападимитриу Х., Стайнглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985. - 512 с.
(5)Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. - М.: Наука, 1990. - 384 с.
На следующем шаге мы рассмотрим поиск в ширину на графе.
