Шаблоны Python - реализация графов. Гвидо ван Россум
Читать

Шаблоны Python - реализация графов. Гвидо ван Россум

Графы - это сети, состоящие из узлов, соединенных ребрами или дугами. В ориентированных графах соединения между узлами имеют направление и называются дугами; в неориентированных графах соединения не имеют направления и называются ребрами. Мы, в основном, обсудим ориентированные графы. Алгоритмы для графов включают поиск пути между двумя узлами, поиск кратчайшего пути между двумя узлами, нахождение циклов в графе (цикл - это непустой путь, соединяющий узел с самим собой), поиск пути, проходящего через все узлы (знаменитая "задача коммивояжера"), и т.д. Иногда узлы или дуги графа имеют вес или цену, ассоциированную с ними, и нас интересует нахождение пути наименьшей цены.