🗊Презентация Основы программирования. Поиск на графах

Основы программирования Поиск на графах

Обход графа: поиск в глубину Поиск в глубину позволяет обойти все вершины графа по одному разу, переходя от вершины к вершине по ребрам. Поиск в глубину реализуется рекурсивным алгоритмом: Пусть выбрана некоторая не рассмотренная ранее вершина A Перебираем все исходящие из A ребра, при этом: если ребро ведет в не рассмотренную ранее вершину B, то продолжаем поиск рекурсивно от B после обработки B возвращаемся в A и продолжаем перебирать исходящие из A ребра если все ребра из A проверены, то либо возвращаемся к вершине, из которой мы пришли в A (если такая есть), либо выбираем любую ранее не проверенную вершину и выполняем алгоритм от нее.

Обход графа: поиск в глубину Граф связный, если для любой пары вершин существует соединяющий их маршрут, проходящий по ребрам. Поиск в глубину разбивает множество ребер на 2 подмножества: древесные (от текущей вершины к непроверенной) и обратные (к уже проверенной вершине). Древесные ребра образуют дерево (связный граф без циклов), для которого определен порядок обхода вершин при поиске в глубину. f a b 5 1 2 c d e 4 3 6

Классы MGraph и LGraph Будем добавлять методы к классам MGraph (матрица смежности) и LGraph (списки смежных вершин): class MGraph { bool **mat; // матрица смежности int vernum; // число вершин … }; class LGraph { List *lst; // списки смежных вершин int vernum; // число вершин … };

Методы MGraph для поиска в глубину Формируется массив R[0…n-1], где R[i] – номер вершины i в порядке обхода в глубину (от 1). void MGraph::deep(int cver, int *R, int &cnum) { R[cver] = ++cnum; for (int i = 0; i < vernum; i++) if (mat[cver][i] && !R[i]) deep(i, R, cnum); } int* MGraph::DFS() { int i, cnum, *R = new int[vernum]; for (i = 0; i < vernum; i++) R[i] = 0; for (cnum = i = 0; i < vernum; i++) if (!R[i]) deep(i, R, cnum); return R; }

Метод deep для LGraph void LGraph::deep(int cver, int *R, int &cnum) { int *pv; R[cver] = ++cnum; for (pv = lst[cver].get_first(); pv != NULL; pv = lst[cver].get_next()) if (!R[*pv]) deep(*pv, R, cnum); } Метод DFS точно такой же, как в классе MGraph. Трудоемкость алгоритма DFS на списках смежных вершин составляет ).

Компоненты связности Компоненты связности неориентированного графа это максимальные (по включению вершин) связные подграфы. Для выделения компонент связности используем поиск в глубину, внеся следующие изменения: добавим в класс MGraph целую переменную comptotal, в которой будет вычисляться число компонент изменим процесс формирования массива R: R[i] будет хранить номер компоненты (от 1), включающую вершину i (R[i]=0, если вершина i еще не просмотрена). Приводимые далее методы cdeep и get_comp – это модификации методов deep и DFS.

Методы MGraph для выделения компонент void MGraph::сdeep(int cver, int *R) { R[cver] = comptotal; for (int i = 0; i < vernum; i++) if (mat[cver][i] && !R[i]) cdeep(i, R); } int* MGraph::get_comp() { int i, *R = new int[vernum]; comptotal = 0; for (i = 0; i < vernum; i++) R[i] = 0; for (i = 0; i < vernum; i++) if (!R[i]) { comptotal++; cdeep(i, R); } return R; }

Обход графа: поиск в ширину Поиск в ширину обычно используется для проверки, существует ли маршрут из некоторой вершины-источника v в целевую вершину w, проходящий по ребрам графа. В процессе поиска вершины помещаются в очередь для просмотра. Начальная очередь содержит только v. Пусть u – текущая извлекаемая из очереди вершина. Рассмотрим все ребра (u,x), при этом возможны варианты: x просмотрена или находится в очереди – изменений нет, x=w – маршрут найден, алгоритм завершается x добавляется в очередь. Если w не найдена, то после обработки всех ребер (u,x) из очереди выбирается следующая текущая вершина u, и поиск продолжается. Если очередь закончилась, то маршрута из v в w нет.

Обход графа: поиск в ширину При поиске в ширину можно не только определить, существует ли маршрут из v в w, но и вычислить его минимальную длину (минимальное число пройденных ребер). Для этого нужно вычислять уровни просмотренных вершин (массив Lev[0…n-1]): вершина-источник v имеет уровень 1, начальные значения для остальных вершин Lev[i]=0 (это означает, что вершина i еще не рассмотрена), если Lev[u]=a, существует ребро (u,x) и Lev[x]=0, то для x устанавливается значение уровня Lev[x]=a+1, если Lev[w]>0, то существует, по крайней мере, один маршрут, и кратчайший маршрут содержит Lev[w]-1 ребро.

Обход графа: поиск в ширину Функции для поиска в ширину имеют 1 параметр – номер v (от 0) вершины-источника. Поиск закончится, когда будут просмотрены все вершины, достижимые из v. Для всех вершин графа будем формировать и возвращать массив уровней вершин Lev. Если в результате поиска Lev[w]=0 для некоторой вершины w, то w не достижима из v. Для организации очереди используем класс IQueue (очередь целых чисел) из раздела «Структуры и классы».

Метод MGraph для поиска в ширину int* MGraph::BFS(int v) { int u, x, *Lev = new int[vernum]; IQueue Que(vernum); for (u = 0; u < vernum; u++) Lev[u] = 0; Lev[v] = 1; Que.push(v); for (u = Que.pop(); u >= 0; u = Que.pop()) for (x = 0; x < vernum; x++) if (mat[u][x] && !Lev[x]) { Lev[x] = Lev[u] + 1; Que.push(x); } return Lev; }

Метод LGraph для поиска в ширину int* LGraph::BFS(int v) { int u, *px, *Lev = new int[vernum]; IQueue Que(vernum); for (u = 0; u < vernum; u++) Lev[u] = 0; Lev[v] = 1; Que.push(v); for (u = Que.pop(); u >= 0; u = Que.pop()) for (px = lst[u].get_first(); px != NULL; px = lst[u].get_next()) if (!Lev[*px]) { Lev[*px] = Lev[u] + 1; Que.push(*px); } return Lev; }

Выделение минимального остова Пусть – связный неориентированный граф, содержащий вершин и ребер. Остов (каркас) – это некоторый связный суграф , не содержащий циклов (дерево). В общем случае можно выделить множество каркасов (например, если – полный граф, то для него можно определить различных каркасов). Для любой пары вершин в существует единственный соединяющий их путь. Добавление к остову любого ребра всегда приводит к образованию цикла.

Выделение минимального остова Любой остов связного графа содержит ровно ребро. Доказательство (по мат. индукции): 1. Остов включает 0 ребер при и 1 ребро при . 2. Пусть остов связного графа с вершинами содержит ребро. Если к графу будет добавлена новая вершина , то достаточно включить только одно ребро вида , чтобы полученный граф стал связным. Добавление к графу еще одного ребра (любого) приведет к образованию цикла. В общем случае, если граф содержит компонент связности, то для него можно выделить каркасов (остовный лес), которые в сумме будут содержать ребер.

Выделение минимального остова Пусть – взвешенный граф (задана матрица весов ребер , если ). В этом случае можно поставить задачу выделения минимального по весу остова . Правила выделения ребер минимального остова определяет Лемма: Пусть – некоторые подграфы (поддеревья) с попарно непересекающимися множествами вершин . Тогда ребро с весом принадлежит минимальному остову.

Выделение минимального остова Доказательство (от противного): пусть и есть такое ребро , что , и . В минимальном остове есть пути из в и из в . Подграф связан с остальной частью графа ребром . Поэтому при добавлении образуется цикл. Если из этого цикла удалить ребро , то будет получен новый остов, вес которого меньше, чем у - противоречие.

Выделение минимального остова Пусть в остов добавлено ребро , причем . Тогда деревья и объединятся в одно, т.е. общее число построенных поддеревьев уменьшится на 1. Процесс построения закончится, когда останется одно дерево, содержащее ребро (или отдельных деревьев, если исходный граф содержит компонент). В алгоритмах выделения минимального остова в качестве начальных используются поддеревьев, содержащих по 1 вершине (и 0 ребер). Затем производится последовательный выбор минимальных по весу ребер, соединяющих текущие поддеревья, и объединение пар поддеревьев.

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

Алгоритм Прима Для снижения трудоемкости формируется дополнительный массив длины : , если вершина уже включена в остов, , если – ближайшая к уже включенная в остов вершина. За один просмотр массива ( элементарных шагов) можно выделить очередное ребро минимального остова – это минимальное по весу ребро вида , где . Пусть это ребро и его вес равен . Тогда если , то ребро действительно содержится в графе и его нужно добавить в остов (вместе с вершиной ).

Алгоритм Прима Если , то ребро действительно содержится в графе и его нужно добавить в остов (вместе с вершиной ). После этого необходимо перестроить массив (за один проход): для каждой пока не включенной в остов вершины проверить, не будет ли ребро легче, чем . Если , то это означает, что исходный граф несвязный, и было выделено одно из поддеревьев остова (для одной компоненты связности). Построение следующего поддерева можно начинать с любой вершины, входящей в следующую компоненту.

Метод WGraph для алгоритма Прима void WGraph::get_span_tree() { double wmin; int i, j, vm, *B = new int[vernum]; B[0] = -1; for (i = 1; i < vernum; i++) B[i] = 0; for (i = 1; i < vernum; i++) { wmin = MAX; vm = 0; for (j = 1; j < vernum; j++) if (B[j] != -1 && wmin > mat[j][B[j]]) { vm = j; wmin = mat[j][B[j]]; } if (!vm) return; add_edge(vm, B[vm]); B[vm] = -1; for (j = 1; j < vernum; j++) if (B[j]!=-1 && mat[j][B[j]]>mat[j][vm]) B[j] = vm; } }

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

Алгоритм Крускала Для проверки, приводит ли добавление ребра к образованию цикла, формируются (и последовательно объединяются) множества связных вершин: вершины и принадлежат одному множеству, если существует путь из в , состоящий из уже выделенных ребер остова. : ребро образует цикл в – недопустимое, : ребро соединяет точки из разных множеств. можно добавить к остову, при этом и объединятся в одно множество.

Быстрое объединение множеств Множества вершин удобно представлять в виде деревьев принадлежности вершин со ссылкой от «сына» к «отцу» и хранить ссылки в целочисленном массиве : начальные значения (отдельные корни деревьев), далее только для корней, иначе – это «отец» . По ссылкам можно пройти от вершины до корня, а корень однозначно определяет множество вершин. При проверке ребра необходимо: найти корни множеств, содержащих вершины и , если корень() = корень(), то обе вершины принадлежат одному множеству, т.е. ребро образует цикл, если корень() корень(), то ребро добавляется в остов, а 2 множества объединяются путем формирования в ссылки с одного корня на другой.

Быстрое объединение множеств Пример построения деревьев принадлежности (порядок выбора ребер (1,2), (6,7), (4,5), (3,6), (1,4), (2,4), (2,6)):

Быстрое объединение множеств Чтобы деревья при объединении не вырождались в линейный список, нужно меньшее дерево делать поддеревом большего. Для этого нужен дополнительный массив весов , в котором каждому корню приписывается либо число вершин, либо высота дерева (эти значения модифицируются при объединении множеств). При указанных выше условиях дерево высоты будет содержать не менее вершин (по матиндукции): 1. Для выполняется. 2. Пусть объединяются деревья высоты и , с числом вершин и , , и . Если , то объединенное дерево будет также иметь высоту . Если , то высота нового дерева будет , а число вершин .

Быстрое объединение множеств Если множество содержит вершин, то его корень можно найти не более, чем за шагов. Трудоемкость выделения всех ребер остова (после сортировки ребер графа) не превышает . Еще более эффективной будет проверка со сжатием путей, когда при поиске корня ссылки на «отца» заменяются на ссылки прямо на корень множества для всех пройденных вершин. Тогда трудоемкость выделения остова , где – «обратная» к частному случаю функции Аккермана . (это фактически ).

Алгоритм Крускала для массива ребер Алгоритм Крускала приводится в виде отдельной функции span_tree, которая выделяет минимальный остов графа, заданного массивом длины e взвешенных ребер R (число вершин равно n). Остов сохраняется в массиве W длины n-1, который также содержит взвешенные ребра и должен быть выделен заранее. span_tree выделяет остов и возвращает число его ребер (<= n-1). Взвешенное ребро представляется структурой struct Edge { int a, b; // номера двух вершин ребра double weight; // вес ребра (для сортировки) } Функция sort_edges производит сортировку массива R по возрастанию весов ребер.

Алгоритм Крускала для массива ребер int span_tree(Edge *R, int e, int n, Edge *W) { int k = 0, ra, rb, i, *A, *B; A = new int[n]; B = new int [n]; sort_edges(R, e); for (i=0; i < n; i++) { A[i] = i; B[i] = 1; } for (i = 0; k < n-1 && i < e; i++) { for (ra = R[i].a; ra != A[ra]; ra = A[ra]); for (rb = R[i].b; rb != A[rb]; rb = A[rb]); if (ra == rb) continue; W[k++] = R[i]; if (B[ra] >= B[rb]) { A[rb] = ra; B[ra] += B[rb]; } else { A[ra] = rb; B[rb] += B[ra]; } } return k; }

Жадные алгоритмы Алгоритмы Прима и Крускала – жадные: на каждом их шаге делается локально оптимальный (жадный) выбор, который никогда не отменяется на последующих шагах. Жадный алгоритм можно использовать, если для задачи выполняются 2 условия: оптимальное решение задачи содержит в себе оптимальные решения подзадач (свойство оптимальности подзадач); последовательность локально оптимальных выборов дает глобально оптимальное решение (т.е. жадный выбор на каждом шаге не закрывает путь к оптимальному решению).