Что такое взвешенный граф
Погружение в графы
Графы в большинстве своем представляют собой неупорядоченные деревья. В основном это утверждение касается ненаправленных и невзвешенных графов. Однако оно остается в силе и в отношении направленных или взвешенных графов, либо направленных и взвешенных одновременно, только при этом надо детализировать понятие “неупорядоченности”.
Направленные графы
Прежде, чем познакомиться с направленным графом, взгляните на ненаправленный граф, представленный ниже:
Ненаправленный граф позволяет свободно перемещаться между вершинами в любом направлении. Теперь посмотрите на направленную версию этого графа:
Тут все меняется. Вы можете перемещаться между вершинами только в направлении стрелки, прикрепленной к каждому ребру. Например, вы можете перейти из пункта А в пункт В, но не из пункта В в пункт А. Немного более строго, верно?
Взвешенные графы
Теперь подумаем о том, чтобы добавить веса ребрам графа. Представьте себе, что у каждого ребра есть цена; цена, которую нужно заплатить, чтобы пересечь ребро. Но перед этим представьте, что все ребра бесплатные, то есть имеют нулевую цену.
На самом деле это мало что меняет, так как с самого начала не было никакой цены, которую нужно было платить. Мы все еще можем пройти по графу без раздумий, если будем следовать указаниям стрелок. Даже если у каждого ребра есть цена, пока все они равны, поскольку каждое ребро имеет одинаковое значение, или вес.
Хорошо, но что, если бы цены были другими? Как бы это изменило способ прохождения по графу?
Поскольку цены теперь отличаются друг от друга, вводится новая динамика. Переход от вершины к вершине будет стоить разных сумм “денег”. Иногда есть только один путь, но в некоторых случаях можно выбрать маршрут, и цена обычно служит определяющим фактором в этом решении. В общем, при переходе из одной вершины графа в другую “самый дешевый” путь является желаемым. Например, если бы я хотел выбрать самый дешевый путь из пункта А в пункт Е, я бы пошел по маршруту АBDЕ. Хотя первоначальным решением мог бы стать маршрут ABE, на самом деле он вышел бы дороже. Подсчеты показывают: стоимость ABE составляет 11, в то время как АBDЕ — всего 9. Надеюсь, вы получили основное представление о взвешенных графах.
До этого момента я называл числа, представляющие каждое ребро, его “ценой”, имея в виду деньги. На самом деле эти цифры обозначают “вес” ребра. Аналогия с деньгами упрощает знакомство с этим видом графа, поскольку деньги — это то, с чем все мы знакомы. Есть и другие способы рассмотрения взвешенного графа. Вы можете представить числа как расстояние между двумя вершинами. Большинство иллюстраций графов не соотнеслись бы с таким представлением, но, тем не менее, такая аналогия тоже приемлема.
Представление графов в коде
Итак, вы уже знаете, что такое направленные и взвешенные графы. Теперь выясним, как представить графы в коде. До сих пор мы использовали только иллюстрации графов. Что ж, оказывается, существует множество способов их представления в коде. Рассмотрим некоторые из них в отношении направленного и невзвешенного графа, показанного ранее.
Список ребер
Список ребер — это именно то, на что похож приведенный ниже код; это список всех ребер на графе. Обратите внимание: каждое ребро представлено своими вершинами — начальной и конечной.
Список смежности
Список смежности — это что-то вроде словаря, в котором каждый ключ является вершиной в графе, а каждое значение — это все, к чему эта вершина примыкает. В направленном графе стрелки должны быть направлены так, чтобы вершина была ключом в списке.
Матрица смежности
Чтобы лучше понять матрицу смежности, изобразим ее в виде рисунка. Если у вас есть опыт работы с матрицами в исчислении, то вам это дастся довольно легко. Если нет, не стоит беспокоиться — всему свое время.
В матрице смежности “0” означает, что две вершины не являются смежными, а “1”, указывает на то, что они являются смежными. Существует множество способов манипулировать такой матрицей и работать с ней, но это выходит за рамки данного объяснения. Обратите внимание на то, что на диагонали есть только нули. Подумайте, почему это так…
Для кодирования матрицы смежности существует несколько способов. В следующих случаях используется ООП:
Когда следует использовать каждый метод
Каждый метод является допустимым представлением графа. Когда же предпочесть один из них всем остальным? Если коротко, то это зависит от того, что вы делаете и как собираетесь манипулировать данными. Например, матрица смежности великолепна и проста в использовании, но может занимать гораздо больше памяти, чем, скажем, список ребер. Обратите внимание и на то, что каждый метод годится для указания веса ребра в случае со взвешенным графом; эта информация была исключена из примеров для упрощения.
Заключение
Мир графов в компьютерных науках огромен. Возможно, для вас это было первое знакомство с ним. Надеемся, что теперь вы лучше сможете понять основы продвижения проектов.
Для дальнейшего погружения в тему рекомендуем изучить алгоритмы обхода, такие как DFS (поиск в глубину) и BFS (поиск в ширину).
Взвешенные графы. Алгоритм Дейкстры
Взвешенные графы
Алгоритм Дейкстры
Принцип работы алгоритма напоминает принцип работы BFS: на каждом шаге обрабатывается ближайшая ещё не обработанная вершина (расстояние до неё уже известно). При её обработке все ещё не посещённые соседи добавляются в очередь для посещения (расстояние до каждой из них рассчитывается как расстояние до текущей вершины + длина ребра). Главное отличие от BFS заключается в том, что вместо классической очереди используется очередь с приоритетом. Она позволяет нам выбирать ближайшую вершину за \(O(\log N)\).
Анимация выполнения алгоритма Дейкстры для поиска кратчайшего пути из вершины \(a\) в вершину \(b\):
С помощью псевдокода алгоритм Дейкстры описывается следующим образом:
Как видите, в очереди с приоритетом хранится не только номер вершины, но и вычисленное расстояние до неё, по которому и ведётся сортировка. Также возможна ситуация, при которой одна и та же вершина будет помещена в очередь несколько раз с разным расстоянием (так как она достижима по нескольким рёбрам). В такой ситуации обрабатываем её только один раз (с минимальным возможным расстоянием).
Реализация
В нашей очереди с приоритетом должны храниться пары (вершина, расстояние до неё), причём отсортированы они должны быть по уменьшению расстояния. Для этого нужно использовать тип std::priority_queue
Для хранения взвешенного графа в виде списка смежности для каждой вершины мы храним вектор пар (соседняя вершина, длина ребра до неё).
Реализация с восстановлением пути
Восстановление пути для алгоритма Дейкстры реализуется точно так же, как и для BFS: при успешном улучшении пути в вершину \(u\) через вершину \(v\), мы запоминаем, что \(prev[v] = u\). После окончания работы алгоритма используем массив \(prev\) для восстановления пути в обратном направлении.
Область применения алгоритма Дейкстры
Алгоритм Дейкстры является оптимальным для поиска пути практически в любых графах, но он имеет одно ограничение. Алгоритм Дейкстры неприменим для графов, содержащих рёбра с отрицательным весом. Для поиска кратчайшего пути в таких графах обычно используют алгоритм Форда-Беллмана.
brestprog
Олимпиадное программирование в Бресте и Беларуси
Теория графов. Часть третья (Представление графа с помощью матриц смежности, инцидентности и списков смежности)
Все, что познается, имеет число, ибо невозможно ни понять ничего, ни познать без него – Пифагор
Список смежности (инцидентности)
Взвешенный граф (коротко)
Итак, мы умеем задавать граф графическим способом. Но есть еще два способа как можно задавать граф, а точнее представлять его. Для экономии памяти в компьютере граф можно представлять с помощью матриц или с помощью списков.
Матрица является удобной для представления плотных графов, в которых число ребер близко к максимально возможному числу ребер (у полного графа).
Другой способ называется списком. Данный способ больше подходит для более разреженных графов, в котором число ребер намного меньше максимально возможного числа ребер (у полного графа).
Перед чтением материала рекомендуется ознакомится с предыдущей статьей, о смежности и инцидентности, где данные определения подробно разбираются.
Матрица смежности
Но тем кто знает, но чуть забыл, что такое смежность есть краткое определение.
Смежность – понятие, используемое только в отношении двух ребер или в отношении двух вершин: два ребра инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.
Матрица (назовем ее L) состоит из n строк и n столбцов и поэтому занимает n^2 места.
Каждая ячейка матрицы равна либо 1, либо 0;
Ячейка в позиции L (i, j) равна 1 тогда и только тогда, когда существует ребро (E) между вершинами (V) i и j. Если у нас положение (j, i), то мы также сможем использовать данное правило. Из этого следует, что число единиц в матрице равно удвоенному числу ребер в графе. (если граф неориентированный). Если ребра между вершинами i и j не существует, то ставится 0.
Для практического примера возьмем самый обыкновенный неориентированный граф:
А теперь представим его в виде матрицы:
Ячейки, расположенные на главной диагонали всегда равны нулю, потому что ни у одной вершины нет ребра, которое и начинается, и заканчивается в ней только если мы не используем петли. То есть наша матрица симметрична относительно главной диагонали. Благодаря этому мы можем уменьшить объем памяти, который нам нужен для хранения.
С одной стороны объем памяти будет:
Но используя вышеописанный подход получается:
Потому что нижнюю часть матрицы мы можем создать из верхней половины матрицы. Только при условии того, что у нас главная диагональ должна быть пустой, потому что при наличии петель данное правило не работает.
Если граф неориентированный, то, когда мы просуммируем строку или столбец мы узнаем степень рассматриваемой нами вершины.
Если мы используем ориентированный граф, то кое-что меняется.
Здесь отсутствует дублирование между вершинами, так как если вершина 1 соединена с вершиной 2, наоборот соединена она не может быть, так у нас есть направление у ребра.
Возьмем в этот раз ориентированный граф и сделаем матрицу смежности для него:
Если мы работаем со строкой матрицы, то мы имеем элемент из которого выходит ребро, в нашем случаи вершина 1 входит в вершину 2 и 8. Когда мы работаем со столбцом то мы рассматриваем те ребра, которые входят в данную вершину. В вершину 1 ничего не входит, значит матрица верна.
Если бы на главной диагонали была бы 1, то есть в графе присутствовала петля, то мы бы работали уже не с простым графом, с каким мы работали до сих пор.
Матрица инцидентности
Инцидентность – понятие, используемое только в отношении ребра и вершины: две вершины (или два ребра) инцидентными быть не могут.
Матрица (назовем ее I) состоит из n строк которое равно числу вершин графа, и m столбцов, которое равно числу ребер. Таким образом полная матрица имеет размерность n x m. То есть она может быть, как квадратной, так и отличной от нее.
Ячейка в позиции I (i, j) равна 1 тогда, когда вершина инцидентна ребру иначе мы записываем в ячейку 0, такой вариант представления верен для неориентированного графа.
Сразу же иллюстрируем данное правило:
Сумма элементов i-ой строки равна степени вершины.
Одной из особенностей данной матрицы является то, что в столбце может быть только две ненулевых ячейки. Так как у ребра два конца.
Список смежности (инцидентности)
Список смежности подразумевает под собой, то что мы работаем с некоторым списком (массивом). В нем указаны вершины нашего графа. И каждый из них имеет ссылку на смежные с ним вершины.
В виде списка это будет выглядеть так:
Неважно в каком порядке вы расположите ссылку так как вы рассматриваете смежность относительно первой ячейки, все остальные ссылки указывают лишь на связь с ней, а не между собой.
Так как здесь рассматривается смежность, то здесь не обойдется без дублирования вершин. Поэтому сумма длин всех списков считается как:
Когда мы работаем с ориентированным графом, то замечаем, что объем задействованной памяти будет меньше, чем при неориентированном (из-за отсутствия дублирования).
Сумма длин всех списков:
Со списком инцидентности все просто. Вместо вершин в список (массив) вы вставляете рёбра и потом делаете ссылки на те вершины, с которыми он связан.
К недостатку списка смежности (инцидентности) относится то что сложно определить наличие конкретного ребра (требуется поиск по списку). А если у вас большой список, то удачи вам и творческих успехов! Поэтому, чтобы работать максимальной отдачей в графе должно быть мало рёбер.
Взвешенность графа
К примеру, возьмем граф с весами на ребрах:
И сделаем матрицу смежности:
В ячейках просто указываем веса ребра, а в местах где отсутствует связь пишем 0 или -∞.
Более подробно данное определение будет рассмотрено при нахождении поиска кратчайшего пути в графе.
Итак, мы завершили разбор представления графа с помощью матрицы смежности и инцидентности и списка смежности (инцидентности). Это самые известные способы представления графа. В дальнейшем мы будем рассматривать и другие матрицы, и списки, которые в свою очередь будут удобны для представления графа с определёнными особенностями.
Если заметили ошибку или есть предложения пишите в комментарии.
Что такое взвешенный граф
Степень входа вершины – количество входящих в нее ребер, степень выхода – количество исходящих ребер.
Классификация графов
В связном графе между любой парой вершин существует как минимум один путь.
В несвязном графе существует хотя бы одна вершина, не связанная с другими.
Графы также подразделяются на
В ориентированном графе ребра являются направленными, т.е. существует только одно доступное направление между двумя связными вершинами.
В неориентированном графе по каждому из ребер можно осуществлять переход в обоих направлениях.
Частный случай двух этих видов – смешанный граф. Он характерен наличием как ориентированных, так и неориентированных ребер.
Способы представления графа
Граф может быть представлен (сохранен) несколькими способами:
Использование двух первых методов предполагает хранение графа в виде двумерного массива (матрицы). Размер массива зависит от количества вершин и/или ребер в конкретном графе.
Матрица смежности графа — это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1.
Число строк матрицы смежности равно числу столбцов и соответствует количеству вершин графа.
Когда из одной вершины в другую проход свободен (имеется ребро), в ячейку заносится 1, иначе – 0. Все элементы на главной диагонали равны 0 если граф не имеет петель.
Матрица инцидентности (инциденции) графа — это матрица, количество строк в которой соответствует числу вершин, а количество столбцов – числу рёбер. В ней указываются связи между инцидентными элементами графа (ребро(дуга) и вершина).
В неориентированном графе если вершина инцидентна ребру то соответствующий элемент равен 1, в противном случае элемент равен 0.
Матрица инцидентности для своего представления требует нумерации рёбер, что не всегда удобно. 
Список смежности (инцидентности)
Если количество ребер графа по сравнению с количеством вершин невелико, то значения большинства элементов матрицы смежности будут равны 0. При этом использование данного метода нецелесообразно. Для подобных графов имеются более оптимальные способы их представления.
По отношению к памяти списки смежности менее требовательны, чем матрицы смежности. Такой список можно представить в виде таблицы, столбцов в которой – 2, а строк — не больше, чем вершин в графе.
В каждой строке в первом столбце указана вершина выхода, а во втором столбце – список вершин, в которые входят ребра из текущей вершины.
Преимущества списка смежности:
Недостатки списка смежности:
Алгоритмы обхода графов
Основными алгоритмами обхода графов являются
Поиск в ширину подразумевает поуровневое исследование графа:
Вершины просматриваются в порядке возрастания их расстояния от корня.
Алгоритм прекращает свою работу после обхода всех вершин графа, либо в случае выполнения требуемого условия (например, найти кратчайший путь из вершины 1 в вершину 6).
Каждая вершина может находиться в одном из 3 состояний:
Фиолетовый – рассматриваемая вершина. 
Применения алгоритма поиска в ширину
Алгоритм поиска в ширину работает как на ориентированных, так и на неориентированных графах.
Для реализации алгоритма удобно использовать очередь.
Реализация на C++ (с использованием очереди STL)
Результат выполнения 
Задача поиска кратчайшего пути
Реализация на С++
Поиск в глубину – это алгоритм обхода вершин графа.
Поиск в ширину производится симметрично (вершины графа просматривались по уровням). Поиск в глубину предполагает продвижение вглубь до тех пор, пока это возможно. Невозможность продвижения означает, что следующим шагом будет переход на последний, имеющий несколько вариантов движения (один из которых исследован полностью), ранее посещенный узел (вершина).
Отсутствие последнего свидетельствует об одной из двух возможных ситуаций:
Каждая вершина может находиться в одном из 3 состояний:
Фиолетовый – рассматриваемая вершина. 
Применения алгоритма поиска в глубину
Алгоритм поиска в глубину работает как на ориентированных, так и на неориентированных графах. Применимость алгоритма зависит от конкретной задачи.
Для реализации алгоритма удобно использовать стек или рекурсию.
Реализация на C++ (с использованием стека STL)
Результат выполнения 
Задача поиска лексикографически первого пути на графе.
Реализация на C++
Результат выполнения 
Поиск в глубину также может быть реализован с использованием рекурсивного алгоритма.
Реализация обхода графа в глубину на C++ (с использованием рекурсии)
Что такое взвешенный граф
Теория графов представляет собой раздел математики, имеющий широкое практическое применение во многих областях человеческой деятельности. Математика, физика, химия, теория связи, электротехника, архитектура, исследование операций, генетика, психология – вот далеко не полный список областей ее применени я
Теория графов становится одной из существенных частей математического аппарата кибернетики, языком дискретной математики.
Граф G задается с помощью пары множеств G = (V, R ), где V есть множество вершин, а R – множество линий, соединяющих пары вершин. Линии со стрелками называются дугами, без стрелок – ребрами. Обычно граф представляют с помощью схемы, на которой некоторые вершины соединены ребрами (дугами).
Вершинами могут служить объекты любой природы: будь то населенные пункты, компьютерные сети, элементы блок- схем алгоритмов. Под ребром могут подразумеваться дороги между соседними городами, линии связи между компьютерами.
Ребро и любая из его двух вершин называются инцидентными. Под степенью вершин подразумевается количество инцидентных ей ребер. Так, степень вершин V1 равно 3, а степень вершин V 5 равна 4.
Последовательность чередующихся ребер и вершин графа называется маршрутом. В графах можно выделить различные маршруты. Маршрут называется замкнутым, если вершины начала и конца маршрута совпадают. Если ребра и вершины, образующие маршрут различны, то такой маршрут называется цепью. Путь в ориентированном графе — это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Длина маршрута равна количеству ребер, входящих в него.
Граф называется связным, если любые две его вершины можно соединить маршрутом (или путем).
Граф, в котором направление линий принципиально называется ориентированным (орграф). В орграфе каждое ребро имеет одно направление. Такие ребра называются дугами. Для орграфа вводятся такие понятия, как входящая и исходящая степени вершины. Это соответственно число входящих в вершину дуг и число исходящих из нее дуг.
Взвешенный граф – это граф, в котором с вершинами и линиями связана некоторая дополнительная информация. Эта информация называется весом вершины или линии. Вес позволяет отобразить на графе не только структуру системы, но и различные свойства компонент или связей, количественная характеристика. Вес сети равен сумме весов ее ребер.
Плоским графом называется граф, изображенный на плоскости так, что никакие два его ребра (или, вернее, представляющие их кривые) геометрически не пересекаются нигде, кроме инцидентной им обоим вершины. Граф, изоморфный плоскому графу, называется планарным. Планарный граф можно определить еще так: граф планарен, если его можно уложить на плоскости. Рисунок графа, в котором никакие два его ребра не пересекаются, если не считать точками пересечения общие вершины, называют плоским представлением графа. Ясно, что плоское представление имеет только плоский граф. Обратно, у всякого плоского графа непременно найдется плоское представление. Плоские графы — это простые циклы, деревья, лес, а также граф, содержащий цикл, из вершин которого «выходят» деревья.
Примером неплоского графа может служить полный граф с пятью вершинами. Любые попытки начертить его плоское представление обернутся неудачей.
В качестве характеристики плоского представления графа вводится понятие грани. Гранью в плоском представлении графа G называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов.
В данном графе часть плоскости, ограниченная простым циклом (1,2,3,4,1), является гранью, так как ребро (4,5), расположенное внутри грани, не образует цикла.
Не является гранью заштрихованная часть плоскости в данном примере, так как она содержит цикл, да к тому же эта часть плоскости не ограничена циклом. Ребро (1,2) является мостом, соединяющим циклы. Такие мосты называются перегородками.
В качестве грани можно рассматривать и часть плоскости, расположенную «вне» плоского представления графа. Она ограничена «изнутри» простым циклом и не содержит других циклов. Эту часть плоскости называют бесконечной гранью.
На рисунке часть бесконечной грани заштрихована. Всякое плоское представление графа либо не имеет бесконечной грани, либо имеет в точности одну бесконечную грань. Как особый случай вводится бесконечная грань в плоском представлении дерева и леса. В плоском представлении дерева и леса за грань принимают всю плоскость рисунка.
Два графа гомеоморфны (или тождественны с точностью до вершин степени 2), если они оба могут быть получены из одного и того же графа «включением» в его ребра новых вершин степени 2.
Для всякого плоского представления связного плоского графа без перегородок число вершин ( V ), число ребер ( Е ) и число граней с учетом бесконечной ( R ) связаны соотношением V –Е + R = 2 .
Пусть граф G — связный, плоский граф без перегородок. Определим значение алгебраической суммы V –Е + R для его произвольного плоского представления.
Рассмотрим плоский граф G с пятью вершинами.
Если добавить к нему ребра (1, 3) и (1,5) и, то полученный новый граф G тоже будет плоским.
К этому графу не удается добавить ни одного ребра так, чтобы новый граф тоже был плоским.
Плоский граф называется максимально плоским, если невозможно добавить к нему ни одного ребра так, чтобы полученный граф был плоским. Изображенный граф является максимально плоским.
Каждая грань в плоском представлении максимально плоского графа имеет 3 вершины. Поэтому максимально плоский граф называют триангулированным. Операция добавления новых ребер, в результате которой в плоском представлении каждая грань имеет ровно 3 вершины, называется триангуляцией графа.
Преобразование графа в остовное связное дерево минимального веса.
Введем понятие цикломатического числа y, показывающего, сколько ребер графа нужно удалить, чтобы в нем не осталось ни одного цикла. Цикломатическое число y равно увеличенной на единицу разности между количеством ребер и количеством вершин графа:
Для каждого графа обычно существует несколько осотвных связных деревьев, которые обладают различными весами.
Для построения остовного связного дерева минимального веса используют алгоритм Крускала:
а) обе вершины включаемого графа принадлежат одноэлементным подмножествам, тогда они объединяются в новое, связное подмножество.
б) одна из вершин принадлежит связному подмножеству, а другая нет, тогда включаем вторую в подмножество, которому принадлежит первая.
в) обе вершины принадлежат разным связным подмножествам, тогда объединяем подмножества.
г) обе вершины принадлежат одному связному подмножеству, тогда исключаем данное ребро.
4. Алгоритм заканчивает работу, когда все вершины будут объединены ы одно множество, при этом оставшиеся ребра не включаются в оставное дерево.