| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > LISP > Определение связности графа на Лиспе |
| Автор: МилаР 7.5.2010, 05:20 |
| Пыталась разобраться сама, но думаю это не тот случай, когда можно, быстро все понять. Задание такое: Определение связности графа на Лиспе Напишите программу на языке XLisp, определяющую, является ли данный неориентированный граф связным. Указание: запрограммируйте предварительно предикат (path X Y), проверяющий, существует ли путь из вершины X в вершину Y. Ещё есть Алгоритм поиска в глубину в графе для реализации на Лиспе: Функция (depth V,E,x,y,p,end) выдает путь (список вершин): V - список вершин графа; E - список ребер; x - стартовая (начальная) вершина, при рекурсивном вызове depth, x - текущая вершина, откуда ведется поиск пути; y - список вершин - соседей вершины x; p - накапливаемый путь (накапливающий параметр), в начале поиска - пустой список, вершины накапливаются в обратном пройденному порядке; end - предикат (функциональный аргумент), которому должна удовлетворять целевая (конечная) вершина искомого пути. If x- целевая вершина , then получаем результат , добавляя к пути p вершину x, else if список y вершин-соседей пуст then ответ = nil else if первая вершина в списке y принадлежит пройденному пути p then вызываем рекурсивно функцию depth для хвоста списка y else if первая вершина в списке y не принадлежит пройденному пути p then вызываем рекурсивно функцию, накапливая параметр p и меняя параметры x и y else вызываем рекурсивно функцию depth для хвоста списка y. Буду очень благодарна любой помощи. |