Упражнения для программирования¶

1. Измените функцию поиска в глубину, чтобы она могла делать топологическую сортировку.
2. Измените функцию поиска в глубину, чтобы она могла находить сильно связные компоненты.
3. Напишите метод transpose для класса Graph.
4. Используя поиск в ширину, напишите алгоритм, умеющий определять кратчайший путь от каждой вершины до всех остальных. Это называется задачей поиска всех кратчайших путей между парами.
5. Используя поиск в ширину, пересмотрите программу для лабиринта из главы о рекурсии, чтобы она могла находить из него кратчайший путь.
6. Напишите программу для решения следующей задачи. У вас есть две фляги - на 4 и на 3 галлона. Ни один из них не имеет маркировки. Есть колонка, из которой фляги можно наполнить водой. Как получить ровно два галлона в 4-х галлонной фляге?
7. Обобщите задачу выше, чтобы параметры вашего решения включали размеры каждой фляги и итоговый объём воды, который должен остаться в большем сосуде.
8. Напишите программу для решения следующей задачи. Три миссионера и три каннибала подошли к берегу реки, возле которого привязана лодка, вмещающая только двух человек. Каждому нужно перебраться на другой берег, чтобы продолжить путешествие. Однако, если на каком-нибудь из берегов каннибалов окажется больше, чем миссионеров, то миссионеры будут съедены. Найдите такую последовательность перевозок, чтобы все безопасно оказались на другом берегу реки.