Методы обхода (просмотра) вершин графов. Алгоритмы расчета кратчайших путей между вершинами графа

Методы обхода (просмотра) вершин графов. При решении некоторых задач на графах возникает потребность прохода по всем его вершинам (например, для выполнения в них каких-то действий). Существует два основных способа такого прохода по вершинам, которые называются, соответственно, поиском в глубину и поиском в ширину. В качестве примера возьмем граф на 10 вершинах, заданный следующим списком смежности: 1) 3,4,9; 2) 4,5,7; 3) 1,7; 4) 1,2,6,10; 5) 2,6; 6) 4,5,7,8; 7) 2,3,6,8; 8) 6,7,10; 9) 1,10; 10) 4,8,9. Начинаем обход графа всегда с первой по номеру вершины. В процессе прохода будем составлять список S просмотренных вершин. Поиск в глубину. Шаг 0. Включаем в список просмотренных вершин первую вершину, поскольку мы в ней находимся: S={1}. Шаг 1. Берем из списка смежности последней просмотренной вершины первую, в которой еще не были, и включаем ее в список. Если все вершины включены в список, конец. Если не все вершины просмотрены, а в списке смежности последней просмотренной вершины не просмотренных нет, переходим к шагу 2. Шаг 2. Возвращаемся назад через те вершины, по которым пришли в последнюю, пока в списке смежности очередной вершины не нашлась еще не просмотренная. Если нашлась, включаем ее в список S и переходим к шагу 1. Для нашего примера поиск в глубину будет выглядеть так. Выполняем шаг 1, пока это возможно: S={1 3 7 2 4 6 5 }. Из вершины 5 перейти никуда нельзя, поскольку все вершины из ее списка смежности уже просмотрены. Поэтому переходим к шагу 2, то есть возвращаемся в вершину 6. Из вершины 6 переходим в не просмотренную вершину 8. Имеем S={1 3 7 2 4 6 5 8 10 9}. Процесс просмотра завершен. Поиск в ширину. Шаг 0. Включаем в список просмотренных первую вершину, поскольку мы в ней находимся: S={1}. Шаг 1. Берем все не просмотренные вершины, смежные с последней включенной, и добавляем их в список: S={1, 3, 4, 9}. Шаг 2. Для каждой вершины, включенной на предыдущем шаге, включаем в список все не включенные вершины из ее списка смежности. Повторяем шаг 2, пока все вершины не будут включены в список. Для нашего примера после первого выполнения шага 2 имеем: S={1, 3, 4, 9, 7, 2, 6, 10}. Поскольку остались не просмотренными вершины 5 и 8, повторяем шаг 2. В результате имеем: S={1, 3, 4, 9, 7, 2, 6, 10, 8, 5}. В среднем поиск в глубину – более быстрый процесс, так как для включения еще не просмотренной вершины при поиске в ширину нам приходится перебирать все вершины, включенные на очередном шаге, а таких вершин может оказаться много. Однако в целом выбор метода обхода зависит от типа графа и самой постановки задачи Маршруты, цепи, циклы. Связность и достижимость. Маршрутом в графе называется любая последовательность попарно смежных (в орграфе – непосредственно достижимых) вершин {v0,v1,…,vk}. В маршруте как вершины, так и ребра могут повторяться. Если v0 = vk, то маршрут называется замкнутым, в противном случае – открытым. Если в маршруте каждое ребро встречается ровно один раз, то такой маршрут называется цепью. Если при этом в цепи каждая вершина встречается только один раз, то такая цепь называется простой цепью. Замкнутая цепь называется циклом (в орграфе – контуром), соответственно, замкнутая простая цепь называется простым циклом. Связным называется граф, любые две вершины которого соединены простой цепью. При большом количестве ребер таких цепей можно построить много. Какие-то из них будут короче, какие-то длиннее. Самая короткая из цепей, соединяющих две вершины графа, называется геодезической, а ее длина – расстоянием между вершинами. Самая длинная геодезическая называется диаметром графа. Компонента связности графа (или просто компонента графа максимальный (по включению) связный подграф графа )— . Алгоритмы расчета кратчайших путей между вершинами графа. Таких алгоритмов и их модификаций существует довольно много. Мы рассмотрим два наиболее известных. В практических задачах поиска кратчайших путей обычно предполагается, что на дугах (ребрах) графа заданы некоторые веса. Под весом может, например, подразумеваться, стоимость проезда между пунктами или еще что-то, что требуется в сумме минимизировать. В общем случае веса дуг могут быть произвольными действительными числами, как положительными, так и отрицательными, хотя, конечно, в большинстве задач веса бывают положительны. Результатом работы данных алгоритмов является матрица кратчайших путей между всеми парами вершин. В ней ненулевыми будут те же элементы, что и в матрице достижимости (транзитивного замыкания), а значениями этих элементов будут величины кратчайших (по стоимости или по длине, в зависимости от задачи) путей. Итак, вместо обычной матрицы смежности (или в дополнение к ней), для графа задается матрица весов. Рассмотрим в качестве примера неориентированный граф, диаграмма которого представлена на рис. 3.15. Присвоим ребрам этого графа определенные веса и будем искать кратчайшие пути между его вершинами Алгоритм Форда-Беллмана. В данном алгоритме предполагается, что веса могут быть произвольными действительными числами. Введем для графа, изображенного на рис.3.15, следующую матрицу весов. Знак ∞ здесь означает, что соответствующего ребра в графе нет. Поскольку процесс расчета всей матрицы кратчайших путей довольно трудоемок, мы рассмотрим его только на примере первой строки, то есть найдем кратчайшие пути между первой вершиной и всеми остальными. Шаг 1. Рассматриваем все пути между первой и остальными вершинами, состоящие ровно из одного ребра. Такими путями будут все элементы первой строки матрицы весов. Шаг 2. Теперь сравним веса путей, полученные на предыдущем шаге, со всеми существующими путями между первой и остальными вершинами, состоящими из двух ребер. Например, в вершину 2 из вершины 1 мы можем попасть за 2 шага через вершины 3 и 5. Выполним такое сравнение для всех вершин. Возможно, веса каких-то путей нам в результате удастся уменьшить. Тем более что до вершины 6 вообще нет пути, состоящего из одного ребра. Верхним индексом будем обозначать номер шага, что соответствует числу ребер в путях, которые мы рассматриваем, нижние – номера пары вершин, для которых выполняется сравнение В результате имеем новую строку весов: Шаг 3. Повторяем операцию сравнения полученных весов путей с путями из трех ребер После третьего шага имеем: Шаг 4. Повторяем операцию для всех путей из четырех ребер После четвертого шага имеем: Шаг 5. Повторяем операцию для всех путей из пяти ребер Поскольку более длинных простых цепей в графе на шести вершинах не существует, на этом процесс заканчивается. На последнем шаге нам ничего не удалось улучшить, и конечным является результат, полученный на четвертом шаге: Несмотря на то, что алгоритм Форда-Беллмана позволяет работать с произвольными действительными числами, он требует порядка p3 операций, то есть достаточно трудоемок. В этом мы имели возможность убедиться сами. Поэтому в тех случаях, когда задача позволяет преобразовать веса к положительному виду, можно применить более быстрый алгоритм. Алгоритм Дейкстры. В алгоритме Дейкстры предполагается, что все веса ребер положительны. Из этого предположения следуют два вывода, на которых и основывается алгоритм Дейкстры. 1. Добавление лишнего ребра в путь никогда не уменьшит веса пути. 2. Если кратчайший путь из вершины u в вершину v проходит через вершины i,j, то он включает в себя кратчайший путь между i,j. То есть любая часть кратчайшего пути также является кратчайшим путем. Рассмотрим тот же граф, что и в предыдущем примере, только в матрице весов заменим отрицательные веса на положительные. Шаг 1. Как и в предыдущем алгоритме, за первое приближение кратчайших путей принимаем пути, состоящие из одного ребра Поскольку при добавлении ребра в данном случае вес пути не станет меньше, то самый минимальный вес из этой строки и будет соответствовать кратчайшему пути до соответствующей вершины. В данном случае это вершина 5. Фиксируем этот элемент (выделяем жирным шрифтом) и больше его не пересчитываем: Из второго введенного соображения следует, что теперь мы можем сократить остальные пути, только проходя через вершину 5, поскольку до нее самый короткий путь. Для всех вершин, куда можно дойти через вершину 5, сравним эти пути, как и в предыдущем алгоритме. После пересчета имеем: Шаг 2. Как и на шаге 1, фиксируем минимальные значения, как кратчайшие пути, поскольку добавление нового ребра их не уменьшит Теперь все остальные пути будем пропускать через те вершины, которые дали нам кратчайшие пути на последнем шаге - со значениями 2. То есть, строить пути из трех ребер имеет смысл только для тех из оставшихся вершин, которые смежны с вершинами 2 и 6. Но в данном примере мы явно не получим результата лучшего, чем на шаге 2. Поэтому задача решена. Алгоритм Дейкстры требует порядка p2 операций, поскольку сразу отсекает те пути, которые не имеет смысла рассматривать. В качестве самостоятельного упражнения попробуйте рассчитать кратчайшие пути по данной матрице весов с помощью алгоритма Форда-Беллмана и сравните количество выполненных операций. Деревья Деревья – самый простой вид графов, но очень интересный для практических Задач. Определение 1. Деревом или свободным деревом называется связный граф без циклов. Произвольный граф, у которого все компоненты связности являются деревьями, называется лесом. Свойства свободного дерева. 1. Если G(V,E) – дерево, то любые две вершины в нем соединены единственной простой цепью. Если бы это было не так, то существовал бы цикл, что противоречит самому определению дерева. 2. Любое ребро в дереве является мостом. Опять же, если бы это было не так, то между какими-то вершинами существовала бы еще одна простая цепь, в результате чего получился бы цикл 3. В дереве число ребер q=p-1. 4. Если G(V,E) – лес, состоящий из k компонент связности, то q=p-k. 5. Соединение в дереве двух несмежных вершин одним ребром приводит к образованию ровно одного простого цикла. Если бы добавление одного ребра приводило к образованию более чем одного цикла, то его удаление не приводило бы к нарушению связности. А это противоречит тому, что каждое ребро в дереве является мостом 6. В любом нетривиальном дереве имеются, по меньшей мере, две висячие вершины, для которых d(v)=1. 7. Любое дерево является двудольным графом. Теперь перейдем к тем самым графам, которые обычно ассоциируются с понятием «дерево» (рис.3.17) Определение 2. Ориентированным или корневым деревом является орграф со следующими свойствами. 1. Существует единственный узел v0, называемый корнем дерева, полустепень захода которого равна нулю. 2. Полустепень захода остальных узлов равна 1. 3. Каждый узел достижим из корня. Свойства ориентированных деревьев. 1. Если в корневом дереве отменить ориентацию ребер, то получится свободное дерево. 2. q=p-1. Следует из первого свойства. вершине. 5. Любой подграф на множестве вершин, достижимых из некоторой вершины 6. Если в свободном дереве любую вершину назначить корнем, то получится ориентированное дерево Итак, теперь мы видим, что между ориентированными и неориентированными деревьями есть и разница, и сходство. И мы всегда имеем возможность превратить одно в другое. Что касается задач о деревьях, то первыми в теории графов появились как раз задачи о свободных деревьях. А именно задача о минимальном соединении. Она возникла при строительстве железных дорог в середине XIX века. Требовалось соединить n городов железнодорожным сообщением и, естественно, хотелось, чтобы затраты при этом были минимальны. Ясно, что нет смысла соединять города так, чтобы при этом возникали циклы. Достаточно, чтобы любые два города были соединены каким-то одним путем. То есть получается свободное дерево на n вершинах. Задача о минимальном соединении. Первым взялся за рассмотрение этой задачи английский математик Кэли. Он показал, что число различных деревьев, которые можно построить на n вершинах tn=nn-2. Этот результат получил название теоремы Кэли. Предполагается, что вершины занумерованы определенным образом. Необходимо найти соединение минимального веса. Как и в задаче поиска кратчайших путей, мы здесь имеем матрицу весов, которая задает стоимость всех возможных соединений. Требуется найти соединение минимальной суммарной стоимости, то есть минимального веса. Задача в такой постановке называется задачей Штейнера. Как мы уже выяснили, такое соединение представляет собой свободное дерево. С другой стороны, это дерево является подграфом некоторого взвешенного графа G на том же количестве вершин, который описывает все возможные соединения и их стоимости. Вспомним, что подграф графа G, включающий все его вершины, называется остовным подграфом. То есть в математической постановке мы имеем задачу о построении остовного дерева минимального веса. Мы рассмотрим два алгоритма построения такого дерева. Алгоритм Краскала. В качестве примера возьмем неориентированный взвешенный граф со следующей матрицей весов. Диаграмма графа показана на рис.3.18 Шаг 1. Упорядочим все ребра по возрастанию весов. Имеем следующую последовательность: (1,2), (3,6), (4,5), (4,8), (1,8), (2,3), (2,4), (4,7), (7,8), (1,5), (3,4), (3,7), (5,6), (2,5), (3,8), (6,7). Шаг 2. Берем первое слева (самое дешевое) ребро в списке и образуем первую компоненту связности: G1={V1={1,2},E1={(1,2)}}. Шаг 3 (общий). Предположим, что на текущем шаге алгоритма у нас есть уже какое-то количество компонент связности G1,…,Gk. Берем очередное ребро в списке и поступаем с ним следующим образом. 1. Если обе концевые вершины ребра принадлежат какой-то из компонент Gi , то пропускаем его и переходим к следующему. 2. Если одна концевая вершина ребра (u,v), например, u принадлежит компоненте Gi, то включаем в эту компоненту ребро и новую вершину v – вторую концевую точку ребра. 3. Если обе концевые вершины не принадлежат ни одной из существующих k связных компонент, образуем компоненту Gk+1 из этого ребра и его концевых вершин. 4. Если концевые вершины ребра принадлежат разным компонентам связности, например, Gs и Gt, то объединяем эти компоненты в одну и добавляем ребро, их соединяющее. Теперь имеем k=k-1 компоненту связности. Если k=1 и все вершины графа в нее включены, то процесс завершен. Продолжим теперь процесс построения для нашего графа. В соответствии с условием 3 общего шага выбираем ребра (3,6), (4,5) и образуем две новые компоненты связности: G2={V2={3,6},E2={(3,6)}}, G3={V3={4,5},E3={(4,5)}}. (рис.3.19 а). Следующее ребро (4,8) удовлетворяет условию 2, поэтому присоединяем его к третьей компоненте: G3={V3={4,5,8},E1={(4,5),(4,8)}} (рис. 3.19 б) Ребро (1,8) удовлетворяет условию 4, то есть объединяет две компоненты связности: G1=G1G3 (1,8)={V1={1,2,4,5,8},E1={(1,2),(4,5),(4,8),(1,8)}} (рис.3.19 в) Ребро (2,3) также удовлетворяет условию 4, в результате чего объединяются все уже построенные компоненты связности: G1=G1G2 (2,3)={V1={1,2,3,4,5,6,8}, E1={(1,2),(4,5),(4,8),(1,8),(3,6),(2,3)}} (рис.3.19 г). Ребро (2,4) пропускаем согласно условию 1 общего шага. Следующее ребро (4,7) позволяет включить в остовное дерево последнюю вершину. G1=G1 (4,7)={V1={1,2,3,4,5,6,7,8}, E1={(1,2),(4,5),(4,8),(1,8),(3,6),(2,3),(4,7)}} (рис.3.19 д). Процесс построения завершен. Вес полученного дерева P=1+1+1+2+1+2+2=10. Алгоритм Прима. Некоторым больше нравится именно этот алгоритм. Компонента связности G здесь одна, но нам придется постоянно хранить список «запасных» ребер. Сама работа алгоритма напоминает «поиск в ширину». Шаг 1. Берем первую вершину v0 и все смежные с ней, то есть рассматриваем все инцидентные вершине v0 ребра. Выбираем ребро минимального веса (v0,v) включаем его в G и переходим в вершину v. Остальные ребра вносим в рабочий список E0. Можно сразу упорядочивать ребра в E0 по возрастанию весов. Шаг 2(общий). 2.1. Добавляем в список E0 все ребра, инцидентные последней включенной в G вершине v. 2.2. Из полученного списка выбираем ребро минимального веса, содержащее хотя бы одну еще не включенную в G вершину u. Добавляем его в G вместе с вершиной u и переходим в эту вершину, то есть к шагу 2.1. 2.3. Если все вершины включены, то процесс завершен. Давайте выполним такое построение для нашего графа с рис.3.18. 1. На первом шаге компонента связности та же: G={V={1,2},E={(1,2)}}. Создаем рабочий список из оставшихся ребер, инцидентных вершине 1: E0={(1,8),(1,5)}. Будем упорядочивать ребра в рабочем списке по возрастанию весов слева направо. 2. Последней включенной вершиной является вершина 2. Добавляем инцидентные ей ребра в рабочий список, упорядочивая список по возрастания весов: E0={(1,8),(2,3),(1,5),(2,5)}. Теперь из этого списка выбираем ребро минимального веса, содержащее еще не включенную вершину 8: G={V={1,2,8},E={(1,2),(1,8)}} 3. Исключаем ребро (1,8) из списка, а в список добавляем ребра, инцидентные вершине 8: E0={(4,8),(2,3),(7,8),(1,5),(2,5),(3,8)}. Из него выбираем очередное ребро, содержащее не включенную вершину 4: G={V={1,2,4,8},E={(1,2),(1,8),(4,8)}} Продолжаем процесс по той же схеме. 4. E0={(4,5),(2,3),(7,8),(4,7),(1,5),(2,5),(3,8)}; G={V={1,2,4,5,8}, E={(1,2),(1,8), (4,8), (4,5)}}. 5. E0={(2,3),(7,8),(4,7),(1,5),(5,6),(2,5),(3,8)}; G={V={1,2,3,4,5,8}, E={(1,2), (1,8),(4,8), (4,5),(2,3)}}. 6. E0={(3,6),(7,8),(4,7),(1,5),(3,4),(5,6),(2,5),(3,8)}; G={V={1,2,3,4,5,6,8}, E={(1,2), (1,8), (4,8), (4,5),(2,3),(3,6)}}. 7. E0={(7,8),(4,7),(1,5),(3,4),(5,6),(2,5),(3,8),(6,7)}; G={V={1,2,3,4,5,6,7,8}, E={(1,2), (1,8), (4,8), (4,5),(2,3),(3,6),(7,8)}} Вес полученного дерева P=1+2+1+1+2+1+2=10, как и в предыдущем построении, хотя порядок включения ребер другой. И последнее ребро было выбрано другое, но аналогичного веса. Следовательно, полученные остовные деревья равносильны. В целом алгоритм Прима, хотя и кажется многим более понятным, в вычислительном плане менее эффективен, поскольку нам приходится просматривать список ребер по нескольку раз.