Как можно представить граф (имеющий направленные и ненаправленные ребра) средствами лиспа, наиболее естественным образом в плане дальнейшей обработки (например, поиска кратчайшего пути между вершинами)?
На ум приходит только матрица связности, представленная возможно треугольным массивом или каким-нибудь хитрым разряженным массивом.
Здравствуйте, uncommand, Вы писали:
U>Как можно представить граф (имеющий направленные и ненаправленные ребра) средствами лиспа, наиболее естественным образом в плане дальнейшей обработки (например, поиска кратчайшего пути между вершинами)?
U>На ум приходит только матрица связности, представленная возможно треугольным массивом или каким-нибудь хитрым разряженным массивом.
Такие же как и везде. Лисп ничего нового в плане структур данных не привнес
chukichuki пишет:
> Такие же как и везде. Лисп ничего нового в плане структур данных не привнес
Кхм. кхм. Я бы перефразировал высказывание предыдущего оратора.
Языки программирования после лиспа ничего нового в плане структур данных
не привнесли. Лисп как никак все же второй высокоуровневый язык программирования
в мире.
Posted via RSDN NNTP Server 2.1 beta
uncommand пишет:
> Как можно представить граф (имеющий направленные и ненаправленные ребра)
Направленные и ненаправленные ребра я бы представлял все как направленные.
Т.е. направленную дугу — как просто напр. дугу, а ненапр. дугу — как
две противоположно направленных.
> средствами лиспа, наиболее естественным образом в плане дальнейшей
> обработки (например, поиска кратчайшего пути между вершинами)?
Тогда наиболее естественно представлять это все в виде CONS-ов
(они же "списки", хотя это не совсем правильно их так называть).
> На ум приходит только матрица связности, представленная возможно
> треугольным массивом или каким-нибудь хитрым разряженным массивом.
Можно и так, и матрицей (инцедентности только, а не связности), и в
хэшмап можно класть дуги, и все остальные способы.
Как правило, алгоритмы диктуют способы хранения, так что выбирайте
алгоритм сперва.
Posted via RSDN NNTP Server 2.1 beta
