Что такое взвешенный граф кратко
Обновлено: 08.07.2024
Графы в большинстве своем представляют собой неупорядоченные деревья. В основном это утверждение касается ненаправленных и невзвешенных графов. Однако оно остается в силе и в отношении направленных или взвешенных графов, либо направленных и взвешенных одновременно, только при этом надо детализировать понятие “неупорядоченности”.
Направленные графы
Прежде, чем познакомиться с направленным графом, взгляните на ненаправленный граф, представленный ниже:
Ненаправленный граф позволяет свободно перемещаться между вершинами в любом направлении. Теперь посмотрите на направленную версию этого графа:
Тут все меняется. Вы можете перемещаться между вершинами только в направлении стрелки, прикрепленной к каждому ребру. Например, вы можете перейти из пункта А в пункт В, но не из пункта В в пункт А. Немного более строго, верно?
Взвешенные графы
Теперь подумаем о том, чтобы добавить веса ребрам графа. Представьте себе, что у каждого ребра есть цена; цена, которую нужно заплатить, чтобы пересечь ребро. Но перед этим представьте, что все ребра бесплатные, то есть имеют нулевую цену.
На самом деле это мало что меняет, так как с самого начала не было никакой цены, которую нужно было платить. Мы все еще можем пройти по графу без раздумий, если будем следовать указаниям стрелок. Даже если у каждого ребра есть цена, пока все они равны, поскольку каждое ребро имеет одинаковое значение, или вес.
Хорошо, но что, если бы цены были другими? Как бы это изменило способ прохождения по графу?
Поскольку цены теперь отличаются друг от друга, вводится новая динамика. Переход от вершины к вершине будет стоить разных сумм “денег”. Иногда есть только один путь, но в некоторых случаях можно выбрать маршрут, и цена обычно служит определяющим фактором в этом решении. В общем, при переходе из одной вершины графа в другую “самый дешевый” путь является желаемым. Например, если бы я хотел выбрать самый дешевый путь из пункта А в пункт Е, я бы пошел по маршруту АBDЕ. Хотя первоначальным решением мог бы стать маршрут ABE, на самом деле он вышел бы дороже. Подсчеты показывают: стоимость ABE составляет 11, в то время как АBDЕ — всего 9. Надеюсь, вы получили основное представление о взвешенных графах.
До этого момента я называл числа, представляющие каждое ребро, его “ценой”, имея в виду деньги. На самом деле эти цифры обозначают “вес” ребра. Аналогия с деньгами упрощает знакомство с этим видом графа, поскольку деньги — это то, с чем все мы знакомы. Есть и другие способы рассмотрения взвешенного графа. Вы можете представить числа как расстояние между двумя вершинами. Большинство иллюстраций графов не соотнеслись бы с таким представлением, но, тем не менее, такая аналогия тоже приемлема.
Представление графов в коде
Итак, вы уже знаете, что такое направленные и взвешенные графы. Теперь выясним, как представить графы в коде. До сих пор мы использовали только иллюстрации графов. Что ж, оказывается, существует множество способов их представления в коде. Рассмотрим некоторые из них в отношении направленного и невзвешенного графа, показанного ранее.
Список ребер
Список ребер — это именно то, на что похож приведенный ниже код; это список всех ребер на графе. Обратите внимание: каждое ребро представлено своими вершинами — начальной и конечной.
Список смежности
Список смежности — это что-то вроде словаря, в котором каждый ключ является вершиной в графе, а каждое значение — это все, к чему эта вершина примыкает. В направленном графе стрелки должны быть направлены так, чтобы вершина была ключом в списке.
Матрица смежности
Чтобы лучше понять матрицу смежности, изобразим ее в виде рисунка. Если у вас есть опыт работы с матрицами в исчислении, то вам это дастся довольно легко. Если нет, не стоит беспокоиться — всему свое время.
В матрице смежности “0” означает, что две вершины не являются смежными, а “1”, указывает на то, что они являются смежными. Существует множество способов манипулировать такой матрицей и работать с ней, но это выходит за рамки данного объяснения. Обратите внимание на то, что на диагонали есть только нули. Подумайте, почему это так…
Для кодирования матрицы смежности существует несколько способов. В следующих случаях используется ООП:
Когда следует использовать каждый метод
Каждый метод является допустимым представлением графа. Когда же предпочесть один из них всем остальным? Если коротко, то это зависит от того, что вы делаете и как собираетесь манипулировать данными. Например, матрица смежности великолепна и проста в использовании, но может занимать гораздо больше памяти, чем, скажем, список ребер. Обратите внимание и на то, что каждый метод годится для указания веса ребра в случае со взвешенным графом; эта информация была исключена из примеров для упрощения.
Заключение
Мир графов в компьютерных науках огромен. Возможно, для вас это было первое знакомство с ним. Надеемся, что теперь вы лучше сможете понять основы продвижения проектов.
Для дальнейшего погружения в тему рекомендуем изучить алгоритмы обхода, такие как DFS (поиск в глубину) и BFS (поиск в ширину).
Орграф - это граф , все ребра которого имеют направление. Такие направленные ребра называются дугами . На рисунках дуги изображаются стрелочками (см. рис. 11.6).
В отличие от ребер, дуги соединяют две неравноправные вершины : одна из них называется началом дуги ( дуга из нее исходит ), вторая - концом дуги ( дуга в нее входит ). Можно сказать, что любое ребро - это пара дуг , направленных навстречу друг другу.
Если в графе присутствуют и ребра , и дуги , то его называют смешанным .
Все основные понятия, определенные для неориентированных графов ( инцидентность , смежность , достижимость , длина пути и т.п.), остаются в силе и для орграфов - нужно лишь заменить слово " ребро " словом " дуга ". А немногие исключения связаны с различиями между ребрами и дугами .
Степень вершины в орграфе - это не одно число, а пара чисел: первое характеризует количество исходящих из вершины дуг , а второе - количество входящих дуг .
Путь в орграфе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны, причем каждая вершина является одновременно концом одной дуги и началом следующей дуги . Например, в орграфе на рис. 11.6 нет пути , ведущего из вершины 2 в вершину 5 . "Двигаться" по орграфу можно только в направлениях, заданных стрелками.
Взвешенные графы
Взвешенный (другое название: размеченный ) граф (или орграф ) - это граф ( орграф ), некоторым элементам которого ( вершинам , ребрам или дугам ) сопоставлены числа. Наиболее часто встречаются графы с помеченными ребрами . Числа-пометки носят различные названия: вес, длина , стоимость.
Замечание: Обычный (не взвешенный) граф можно интерпретировать как взвешенный, все ребра которого имеют одинаковый вес 1 .
Длина пути во взвешенном (связном) графе - это сумма длин (весов) тех ребер, из которых состоит путь . Расстояние между вершинами - это, как и прежде, длина кратчайшего пути . Например, расстояние от вершины a до вершины d во взвешенном графе , изображенном на рис. 11.7, равно 6 .
N - периферия вершины v - это множество вершин , расстояние до каждой из которых (от вершины v ) не меньше, чем N .
Способы представления графов
Существует довольно большое число разнообразных способов представления графов . Однако мы изложим здесь только самые полезные с точки зрения программирования.
Матрица смежности
Матрица смежности Sm - это квадратная матрица размером NxN ( N - количество вершин в графе ), заполненная единицами и нулями по следующему правилу:
Если в графе имеется ребро e , соединяющее вершины u и v , то Sm [u,v] = 1 , в противном случае Sm [u,v] = 0 .
Заметим, что данное определение подходит как ориентированным, так и неориентированным графам : матрица смежности для неориентированного графа будет симметричной относительно своей главной диагонали, а для орграфа - несимметричной.
Задать взвешенный граф при помощи матрицы смежности тоже возможно. Необходимо лишь внести небольшое изменение в определение:
Если в графе имеется ребро e , соединяющее вершины u и v , то Sm [u,v] = ves(e) , в противном случае Sm [u,v] = 0 .
Это хорошо согласуется с замечанием, сделанным в предыдущем пункте: невзвешенный граф можно интерпретировать как взвешенный, все ребра которого имеют одинаковый вес 1 .
Небольшое затруднение возникнет в том случае, если в графе разрешаются ребра с весом 0 . Тогда придется хранить два массива: один с нулями и единицами, которые служат показателем наличия ребер, а второй - с весами этих ребер.
В качестве примера приведем матрицы смежности для трех графов , изображенных на рис. 11.5, рис. 11.6 и рис. 11.7 (см. рис. 11.8).
Удобство матрицы смежности состоит в наглядности и прозрачности алгоритмов, основанных на ее использовании. А неудобство - в несколько завышенном требовании к памяти: если граф далек от полного, то в массиве, хранящем матрицу смежности , оказывается много "пустых мест" (нулей). Кроме того, для "общения" с пользователем этот способ представления графов не слишком удобен: его лучше применять только для внутреннего представления данных.
В классических графах все рёбра считаются равноценными и длина пути соответствует количеству рёбер, которые он содержит. Однако часто в задаче каждому ребру соответствует некоторый параметр - длина ребра или стоимость прохождения по нему. В терминологии графов такой параметр называется весом ребра, а граф, содержащий взвешенные рёбра, взвешенным.
Типичная задача для таких графов - поиск кратчайшего пути. Например, в этом графе кратчайший путь между вершинами \(1\) и \(5\): \(1 - 4 - 3 - 5\), так как его вес равен \(30 + 20 + 10 = 60\), а вес ребра \(1 - 5\) равен \(100\).
Алгоритм Дейкстры
Классический алгоритм для поиска кратчайших путей во взвешенном графе - алгоритм Дейкстры (по имени автора Эдгара Дейкстры). Он позволяет найти кратчайший путь от одной вершины графа до всех остальных за \(O(M \log N)\) (\(N, M\) - количество вершин и рёбер соответственно).
Принцип работы алгоритма напоминает принцип работы BFS: на каждом шаге обрабатывается ближайшая ещё не обработанная вершина (расстояние до неё уже известно). При её обработке все ещё не посещённые соседи добавляются в очередь для посещения (расстояние до каждой из них рассчитывается как расстояние до текущей вершины + длина ребра). Главное отличие от BFS заключается в том, что вместо классической очереди используется очередь с приоритетом. Она позволяет нам выбирать ближайшую вершину за \(O(\log N)\).
Анимация выполнения алгоритма Дейкстры для поиска кратчайшего пути из вершины \(a\) в вершину \(b\):
С помощью псевдокода алгоритм Дейкстры описывается следующим образом:
Как видите, в очереди с приоритетом хранится не только номер вершины, но и вычисленное расстояние до неё, по которому и ведётся сортировка. Также возможна ситуация, при которой одна и та же вершина будет помещена в очередь несколько раз с разным расстоянием (так как она достижима по нескольким рёбрам). В такой ситуации обрабатываем её только один раз (с минимальным возможным расстоянием).
Реализация
В нашей очереди с приоритетом должны храниться пары (вершина, расстояние до неё), причём отсортированы они должны быть по уменьшению расстояния. Для этого нужно использовать тип std::priority_queue
>> : первым элементом пары будет расстояние, а вторым - номер вершины.
Для хранения взвешенного графа в виде списка смежности для каждой вершины мы храним вектор пар (соседняя вершина, длина ребра до неё).
Реализация на C++:
Реализация с восстановлением пути
Восстановление пути для алгоритма Дейкстры реализуется точно так же, как и для BFS: при успешном улучшении пути в вершину \(u\) через вершину \(v\), мы запоминаем, что \(prev[v] = u\). После окончания работы алгоритма используем массив \(prev\) для восстановления пути в обратном направлении.
Реализация на C++:
Область применения алгоритма Дейкстры
Алгоритм Дейкстры является оптимальным для поиска пути практически в любых графах, но он имеет одно ограничение. Алгоритм Дейкстры неприменим для графов, содержащих рёбра с отрицательным весом. Для поиска кратчайшего пути в таких графах обычно используют алгоритм Форда-Беллмана.
Взвешенный граф в информатике — это граф с вершинами или рёбрами, несущими добавочную информацию, другими словами вес.
Взвешенный граф
Под взвешенным графом понимается граф, у которого рёбрам соответствуют некоторые весовые параметры. То есть каждому ребру (дуге) поставлено в соответствие некое числовое значение, которое называется длина дуги (или вес, стоимость). Обычные графы (не взвешенные) тоже возможно представить в виде взвешенных, если считать, что все их рёбра обладают весом равным единице. Под длиной пути во взвешенном графе понимается суммарная длина (вес) рёбер, составляющих данный путь. Расстоянием между вершинами считается дистанция самого короткого по весу пути. На рисунке один приведён пример взвешенного графа и там можно видеть, что расстояние между вершинами a и d равняется шести. То есть это путь с наименьшим суммарным весом (от вершины a и далее b, c, d).
Рисунок 1. Образец взвешенного графа. Автор24 — интернет-биржа студенческих работ
Эйлеровы и гамильтоновы графы
Если в составе графа есть цикл (возможно и не простой), который содержит каждое ребро графа один раз, то этот цикл носит название эйлеровый цикл, и, соответственно, такой граф именуется эйлеровым.
Если в составе графа существует цепь, которая содержит каждую вершину один раз, то эта цепь считается эйлеровой цепью, а граф называется полуэйлеровым.
Эти формулировки появились в 1735-ом году в работе Эйлера, где он искал решение задачи о Кёнигсбергских мостах и там первым привёл термин граф. На рисунке два изображена схема, где представлены семь мостов в городе Кёнигсберг (сегодня это Калининград). По условиям задачи требуется пересечь каждый из мостов только один раз и выполнить возврат в начальную точку С. Так как обход мостов завешается в начальной точке маршрута и есть условие однократного пересечения каждого моста, то такой маршрут можно считать простым циклом, который содержит все рёбра графа. Позже подобные циклы получили название эйлеровых, а графы, в составе которых есть такие циклы, назвали эйлеровыми графами.
Готовые работы на аналогичную тему
Рисунок 2. Задача Эйлера о Кёнигсбергских мостах. Автор24 — интернет-биржа студенческих работ
На этом рисунке а — схема местоположения семи мостов в Кёнигсберге (сегодня Калининграде); б — граф, изображающий семь мостов в Кёнигсберге. Мосты представляют собой ребра графа, вершины отображают районы города, которые соединяют мосты.
Цикл Эйлера возможно представить как след от пера, которое рисует данный граф без отрыва пера от листа. То есть, иначе говоря, эйлеровы графы представляют собой графы, которые возможно нарисовать одним движением пера. При этом сам процесс рисования имеет начало и окончание в одной точке.
Выяснив, что в этом графе нет циклических обходов, которые проходят по каждому ребру один раз, Эйлер решил поставить задачу в более общей формулировке: какие должны выполняться условия, чтобы такой цикл в графе мог быть обнаружен? Ответ на поставленный вопрос Эйлер дал в своей теореме. Теорема Эйлера: для существования в связанном неориентированном графе G эйлерова цикла, необходимо и достаточно, чтобы количество вершин с нечётной степенью не превышало две.
Цепью Гамильтона в графе считается простая цепь, проходящая через каждую вершину графа строго по одному разу. Цикл графа, который проходит через все его вершины, считается гамильтоновым циклом. Гамильтоновым называют граф, у которого есть гамильтонов цикл. Гамильтоновы графы возможно использовать для построения моделей большого числа задач практики. К примеру, такие графы могут моделировать движение поездов, и это поможет составить оптимальное расписание их движения. Базой подобных задач является классическая проблема коммивояжера, которому необходимо выполнить вояж по городам и возвратиться в исходную точку, посетив каждый город только один раз. Затраты на поездку должны быть минимальными.
Читайте также: