![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 18. Поиск на графе
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.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. Алгоритмы на графах
cout «" -" «t «" -" «w; if (v! = w) cout «" -" «v; else cout «endl; } public: EULER(const Graph & G): SEARCH< Graph> (G) { search(); } };
РИСУНОК 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 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. Алгоритмы на графах
Программа 18.6. Раскраска графа в два цвета (двудольные графы)_______________ Конструктор рассматриваемого класса DFS устанавливает переменной ОК значение true тогда и только тогда, когда может установить значение 0 или 1 вектору vc, индексированному именами вершин таким образом, что каждое из ребер v-w графа, vc[v] и vc[w], являются попарно различными. template < class Graph> class BI { const Graph & G; bool OK; vector < int> vc; bool dfsR(int v, int c) { vc[v] = (c+1) %2; typename Graph:: adjIterator A(G, v); for (int t = A.beg();! A.end(); t = A.nxt()) if < vc[t] == -1) { if (! dfsR(t, vc[v])) return false; } else if (vc[t]! = c) return false; return true; } public: BI(const Graph & G): G(G), OK(true), vc(G.V(), -l) { for (int v = 0; v < G.V(); v++) if (vc[v] == -1) if (! dfsR(v, 0)) { OK = false; return; } } bool bipartite() const { return OK; } int color(int v) const { return vc[v]; } };
|