5.4. ПОИСК В ГЛУБИНУ В ОРИЕНТИРОВАННОМ ГРАФЕ

Алгоритм 5.2 может также находить ориентированный остовный лес для ориентированного графа если определить список узлов, "смежных" с узлом у, как ребро из т. е. это список узлов, которые являются концами ребер с началом у.

Пример 5.7. На рис. 5.13,а изображен ориентированный граф, а на рис. глубинный остовный лес для него. Как и раньше, мы рисуем древесные ребра сплошными линиями, а прочие ребра — штриховыми.

Рис. 5.13. Поиск в глубину в ориентированном графе: а — ориентированный граф; б - остовный лес.

Чтобы построить остовный лес, начнем с узла вызывает а тот вызывает Последний вызов ничего не добавляет к дереву, ибо единственное ребро с началом идет в узел уже помеченный как "старый". Поэтому возвращаемся к который добавляет в качестве второго сына узла заканчивает работу, ничего не добавляя к лесу, поскольку узел уже "старый". Затем заканчивается ибо все ребра, выходящие из к данному моменту просмотрены. Поэтому возвращаемся обратно в и вызываем Последний вызов ничего не добавляет к дереву; аналогично ничего не может добавить и

Теперь возьмем в качестве корня нового глубинного остовного дерева. Его построение аналогично предыдущему, и мы оставляем его читателю. Заметим, что узлы посещались в порядке Следовательно, в процессе поиска в глубину узлу был приписан номер

При поиске в глубину на ориентированном графе в дополнение к древесным ребрам возникает еще три типа ребер. Это обратные ребра, такие, как на рис. поперечные справа налево, такие, как на том же рисунке, и прямые ребра, такие, как Однако никакое ребро не идет из узла с меньшим номером, присвоенным в процессе поиска в глубину, в ребро с большим номером, если только последнее не является потомком первого. Это не случайно.

Объяснение аналогично объяснению того, почему в неориентированном случае нет поперечных ребер. Пусть ребро и узел был посещен до (т. е. Каждый узел, которому приписывается номер в период между началом и концом процедуры становится потомком узла Но узел должен получить свой номер, когда рассматривается ребро если только он уже не получил номер раньше. Если получает номер в то время, когда рассматривается ребро то становится древесным ребром, а в противном случае прямым ребром. Таким образом, не может быть такого поперечного ребра что

Поиск в глубину в графе разбивает множество его ребер на четыре класса.

1) Древесные ребра, идущие к новым узлам в процессе поиска.

2) Прямые ребра, идущие от предков к подлинным потомкам, но не являющиеся древесными ребрами.

3) Обратные ребра, идущие от потомков к предкам (возможно, из узла в себя).

4) Поперечные ребра, соединяющие узлы, которые не являются ни предками, ни потомками друг друга.

Ключевое свойство поперечных ребер устанавливается в следующей лемме.

Лемма 5.6. Если поперечное ребро, то поперечные ребра идут справа налево.

Доказательство. Доказательство аналогично доказательству леммы 5.3 и остается в качестве упражнения.