Глава 18. Поиск на графе

public:

CC(const Graph & G): G(G), ccnt(O), id(G.V(), -1) {

for (int v = 0; v < G.V(); v++)

if (id[v] == -1) { ccR(v); ccnt++; } }

int count() const { return cent; } bool connect (int s, int t) const

{ return id[s] == id[t]; } };

Какими преимуществами решение задачи определения связности графа, использующее поиск в глубину и реализованное программой 18.4, обладает перед подходом, использу­ющим алгоритм объединения-поиска, который рассматривался в главе 1 применительно к решению задачи определения связности графа, в случае, когда граф задан списком ре­бер? Теоретически поиск в глубину обладает большим быстродействием, чем алгоритм объединения-поиска, поскольку он обеспечивает постоянное время выполнения, в то время как алгоритм объединения-поиска не способен на это; на практике, однако, эта разница незначительна. В конечном итоге, алгоритм объединения-поиска выполняется быстрее, поскольку для него не надо строить полное представление графа. Что еще важ­нее, алгоритм объединения-поиска работает в оперативном режиме (мы можем прове­рить, имеется ли связь между двумя какими-либо вершины за время, близкое к постоян­ному), в то время как решение, использующее поиск в глубину, должно выполнить предварительную обработку, чтобы ответить на запрос о связности за постоянное время. В силу этих причин, мы предпочитаем применять алгоритм объединения-поиска, напри­мер, когда определение связности графа является нашей единственной целью или когда многочисленные запросы перемешиваются с операциями вставки ребер, в то же время мы можем посчитать решение с использованием поиска в глубину более подходящим приме­нительно к АТД графа, поскольку оно с большей эффективностью использует существу­ющую инфраструктуру. Ни тот, ни другой подход не способен работать эффективно в ус­ловиях смеси большого числа вставок ребер, удалений ребер и запросов определения связности; оба подхода требуют отдельных поисков в глубину для вычисления пути. Эти рассуждения показывают, с какими осложнениями приходится сталкиваться при анали­зе алгоритмов на графах; подробное их исследование проводится в разделе 18.9.

Программа 18.5. Двухпроходный эйлеров цикл________________________________

Этот класс DFS печатает каждое ребро дважды, по одному в каждом направлении, в порядке двухпроходного эйлерова цикла. Мы перемещаемся в разных направлениях по обратным ребрам и игнорируем прямые ребра (см. текст). Этот класс является производным от базового класса SEARCH из программы 18.2.

template < class Graph>

class EULER: public SEARCH< Graph>

{

void searchC(Edge e) { int v = e.v, w = e.w; ord[w] = cnt++; cout «" -" «w;

typename Graph:: adjIterator A(G, w); for (int t = A.beg();! A.end(); t = A.nxt()) if (ord[t] == -1) searchC(Edge(w, t));

Часть 5. Алгоритмы на графах

else if (ord[t] < ord[v])

cout «" -" «t «" -" «w;

if (v! = w) cout «" -" «v; else cout «endl; } public:

EULER(const Graph & G): SEARCH< Graph> (G)

{ search(); } };

Двухпроходный эйлеров цикл. Программа 18.5 реализует класс, использующий поиск в глубину и осуществляющей поиск пути, который использует все ребра графа в точнос­ти два раза - по одному в каждом направлении (см. раздел 17.7). Этот путь соответству­ет исследованию Тремо, по условиям которого мы разматываем нить, куда бы ни шли. Мы не применяем освещения перекрестках, зато проверяем, есть ли нить в коридоре (следовательно, мы должны проходить по коридорам, ведущим к перекресткам, на ко­торых уже были), и сначала подготавливаем возможность перемещаться взад и вперед по каждой связи назад (первый раз, когда мы сталкиваемся с тем или иным обратным реб­ром), после чего игнорируем связи вниз (при втором выходе на каждое обратное ребро). Можно также игнорировать связи вниз (при первой встрече) и перемещаться взад и впе­ред по связям вниз (вторая встреча) (см. упражнение 18.25).

РИСУНОК 18.14. ДВУХПРОХОДНЫЙ ЭЙЛЕРОВ ЦИКЛ

Поиск в глубину предоставляет возможность исследовать любой лабиринт, проходя коридор в каждом направлении. Мы вносим изменения в исследование Тремо, которое заключается в том, что мы разматываем нить, куда бы ни шли, и проходим взад и вперед по коридорам, в которых нет нити и которые ведут к посещенным перекресткам. На этом рисунке показан порядок обхода, который отличается от изображенного на рисунках 18.2 и 18.3 главным образом тем, что мы можем найти такой путь обхода, который не пересекает сам себя. Такое упорядочение может иметь место, например, когда при построении списков смежных вершин для представления графа ребра подверга­лись обработке в каком-то другом порядке; либо когда могли быть внесены изменения непосредственно в поиск в глубину с таким расчетом, чтобы было принято во внимание геометрическое расположение узлов (см. упражнение 18.26). Двигаясь по нижнему пути, исходящему из 0 и далее через 2, 6, 4 и 7, мы возвращаемся из 7 в 0, затем меняем направление обхода на обратное, поскольку ord[0] меньше ord[7]. Затем мы идем в 1, назад в 7, назад в 4, в 3, в 5, из 5 следуем в 0 и назад, идем назад из 5 в 4 и назад, далее назад в 3, назад в 4, назад в 6, назад в 2 и назад в 0. Такой путь может быть получен с помощью рекурсивного обхода в прямом и обратном порядке дерева DFS (игнорируя при этом заштри­хованные вершины, которые означают, что мы встречаемся с данным ребром второй раз), при этом мы распечатываем имя соответствующей вершины, просматриваем в рекурсивном режиме поддере­вья, затем снова печатаем имя этой вершины.

Глава 18. Поиск на графе

Остовный лес. На заданном связном графе с V вершинами требуется найти множество из V— 1 ре­бер, соединяющее эти вершины. Если в графе имеют­ся С связных компонент, необходимо найти остовный лес (с V-C ребрами). Мы уже ознакомились с клас­сом DFS, который решает эту задачу: см. программу 18.3.

Поиск вершин. Сколько вершин находится в той же компоненте, что и заданная вершина? Мы легко можем решить эту проблему, начав поиск в глубину с заданной вершины и подсчитывая количество поме­ченных вершин. В насыщенном графе мы можем су­щественно ускорить этот процесс, остановив поиск в глубину после пометки V вершин - в этой точке мы уже знаем, что никакое ребро не приведет нас в вер­шину, которой мы еще не видели, поэтому мы игно­рируем остальные ребра. Подобное усовершенство­вание, по-видимому, позволит нам посетить все вершины за время, пропорциональное V log V, но не E(см. раздел 18.8).

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

РИСУНОК 18.15. РАСКРАСКА ДЕРЕВА DFS В ДВА ЦВЕТА

Чтобы раскрасить граф в два цвета, мы меняем цвет в процессе движения вниз по дереву DFS, затем проводим проверку обратных ребер на несовмес­тимость. В дереве, изображенном в верхней части рисунка, дерево DFS графа, взятого в качестве примера и представленного на рис. 18.9, обратные ребра 5-4 и 7-0 показыва­ют, что рассматриваемый граф не допускает окраски в два цвета ввиду наличия циклов нечетной длины 4-3-5-4 и 0-2-6-4-7-0. В дереве в нижней части рисунка, представляю­щем собой дерево DFS двудольного графа, изображенного на рис. 17.5, таких несоответствий не существу­ет; в рассматриваемом случае окраска в два цвета изображена с применением штриховки.

Часть 5. Алгоритмы на графах