Продолжаем публикацию наиболее интересных глав из книги Magnus Lie Hetland «Python Algorithms». Предыдущая статья расположена по адресу habrahabr.ru/blogs/algorithm/111858. Сегодня же речь пойдет об эффективной работе с графами и деревьями и особенностях их реализации в Python. Базовая терминология теории графов уже обсуждалась (например здесь: habrahabr.ru/blogs/algorithm/65367), так что я не включил часть главы о терминах в эту статью.

Реализация графов и деревьев

Многие задачи, например, задача обхода точек по кратчайшему маршруту, могут быть решены с помощью одного из мощнейших инструментов — с помощью графов. Часто, если вы можете определить, что решаете задачу на графы, вы по-крайней мере на полпути к решению. А если ваши данные можно каким-либо образом представить как деревья, у вас есть все шансы построить действительно эффективное решение.