На этом шаге мы рассмотрим организацию такого поиска.
Для организации простейшего поиска в графе, заданном с помощью списочной структуры неизвестного типа, используется абстрактный тип данных "множество".
Приведем пример функции, реализующей такой поиск.
-- Демонстрация организации поиска вершины в графе graph -- путем преобразования списочной структуры графа в одно- -- уровневый список (используется абстрактный тип данных -- "множество") --------------- import LibGrp_2 ------------------------------------------------ poisk:: Integer -> [(Integer,[Integer])] -> Bool poisk x graph | elem x (walk graph) = True | True = False ------------------------------------------- -- Неудачные тестовые примеры: ---------------------------------------------------------- test = poisk 1 [] == False && poisk 1 [(1,[])] == True && poisk 2 [(1,[])] == False && poisk 5 [(1,[2,3,4]),(5,[6,7]),(8,[9])] == True && poisk 4 [(1,[2,3,4]),(2,[3]),(3,[4])] == True && poisk 5 [(1,[2,3,4]),(2,[]),(3,[4,3,2])] == False
Наиболее распространенные алгоритмы поиска на графе называются поиском в глубину и поиском в ширину.
На следующем шаге мы рассмотрим поиск в глубину на графе.
