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

Чтобы определить, какая из вершин достижима из некоторой заданной вершины, мы, по-видимому, должны начинать обход с нового поиска в глубину из этой вершины (см. рис. 19.11). Можем ли мы воспользоваться информацией, накопленной во время преды­дущих поисков с тем, чтобы сделать этот процесс для последующих вершин более эффек­тивным? Мы рассмотрим такие аспекты достижимости в разделе 19.7.

При определении, принадлежит ли заданный неориентированный граф к числу связ­ных, мы полагаемся на знание того факта, что вершины соединены со своими предками в дереве DFS посредством (по меньшей мере) одного пути в этом дереве. В противопо­ложность этому, рассматриваемый путь в дереве ведет в неправильном направлении в орграфе: ориентированный путь из конкретной вершины орграфа к ее предку существует только в том случае, если существует обратное ребро из какого-либо ее потомка в эту же вершину или в более дальний ее предок. Более того, связность неориентированных гра­фов для каждой вершины ограничивается деревом DFS с корнем в этой вершине; в от­личие от этого, в орграфах поперечные ребра могут перенести нас в любую ранее посе­щенную часть рассматриваемой структуры поиска, даже если эта часть находится в другом дереве леса DFS. В неориентированных графах мы могли воспользоваться пре­имуществом этих особенностей свойства связности для того, чтобы идентифицировать каждую вершину со связной компонентой в одном поиске в глубину, а затем использо­вать эту информацию в качестве основы для операций АТД, выполняемых за постоянное время, с целью определить, являются ли любые две вершины связными. В случае оргра­фа, как мы уже смогли убедиться в этой главе, подобные цели труднодостижимы.

В этой, равно как и в предыдущих главах, мы не раз подчеркивали, что различные способы выбора непосещенных вершин приводят к различным динамикам поиска в глу­бину. Что касается орграфов, то структурная сложность деревьев DFS приводит к раз­личиям в динамике поиска, которые еще ярче выражены, чем те, что наблюдались в нео­риентированных графах. Например, рис. 19.11 может служить иллюстрацией того, что мы получаем заметные различия для орграфов даже в тех случаях, когда мы просто меняем порядок, в котором вершины проверяются высокоуровневыми функциями. Только кро­хотная часть этих возможностей отображена на этом рисунке — в принципе, каждый из V! различных порядков проверки вершин может приводить к различным результатам. В разделе 19.7 мы будем рассматривать один важный алгоритм, который построен на ис­пользовании упомянутой гибкости и выполняет обработку непосещенных вершин на вер­хнем уровне (корни деревьев DFS) в особом порядке, которые позволяет немедленно выявить сильные компоненты.