8.6. Подсказки к задачам

Задача 8.7: Подводный камень, с которым вы столкнётесь — это то, что из каждой вершины вы будете пытаться пойти в вершину-родителя текущей вершины и программа будет считать, что она нашла цикл, хотя на самом деле это — не цикл. Самый простой способ, который я знаю, чтобы избежать этой проблемы — это передавать в процедуру find дополнительный параметр — вершину-родителя текущей вершины — и перед рекурсивным вызовом проверять, не является ли та вершина, куда мы пытаемся пойти, родителем текущей.

Задача 8.8: Могут существовать несвязные графы, в которых эйлеров цикл все-таки существует.

Задача 8.12: Идея номер один состоит в следующем: будем в отдельном массиве для каждой вершины хранить её текущую исходящую степень. Тогда при удалении вершины будет достаточно пробежаться по всем входящим в неё рёбрам и уменьшить на единицу исходящую степень соответствующих вершин; сами исходящие ребра можно не удалять и даже не хранить (храним только входящие). Сток искать тогда можно просто пробегаясь по этому массиву и ища в нем нули. Идея два состоит в том, чтобы, в добавок ко всему вышесказанному, хранить все стоки в отдельном массиве (по принципу стека, например). Когда мы уменьшаем исходящую степень очередной вершины, то посмотрим: если степень стала нулевой, то вершина стала стоком и мы её заносим в этот массив. Теперь не надо на каждом шагу пробегаться по всему массиву степеней в поисках нулей — у нас есть отдельный массив, в котором хранятся вершины с нулевой исходящей степенью. Реализация и дополнительные комментарии в ответах (но сначала попробуйте сами написать!).

Задача 8.15: Попробуйте понять, что получится, если алгоритм Кнута запустить на графе, в котором есть циклы?

Задача 8.16: Рассмотрите следующий граф: три вершины, два ребра: из первой во вторую и из третьей во вторую.

Задача 8.19: Подумайте, что же, собственно, делает алгоритм топологической сортировки в плане времён выхода?

Задача 8.22: Пусть есть перекрёстное ребро. Рассмотрите тот его конец, в который мы при поиске в глубину попали раньше. При просмотре его соседей мы должны будем наткнуться на другой конец этого же ребра. Пойдём ли мы в него?