Графы: основные понятия; способы реализации графов

Дисциплина «Алгоритмы и структуры данных» Лекция 9. Графы: основные понятия. Способы реализации графов. Филатов Вячеслав Валерьевич к.т.н., доцент кафедры КБ-2 «Прикладные информационные технологии» Графы: основные понятия и определения Граф G = (V, Е) состоит из множества вершин V и множества дуг Е. Вершины также называют узлами, а дуги — ребрами. Графы широко используются в различных областях науки и техники для моделирования отношений между объектами. Объекты соответствуют вершинам графа, а ребра — отношениям между объектами. Если дуга представима в виде упорядоченной пары вершин (v, w), где вершина v называется началом, a w — концом дуги, то граф является ориентированным (или сокращенно орграфом). Ориентированную дугу (v, w) записывают как v  w и изображают в виде Неориентированный граф G = (V, Е) состоит из конечного множества вершин V и множества ребер Е. В отличие от ориентированного графа, здесь каждое ребро (v, w) соответствует неупорядоченной паре вершин: если (v, w) — неориентированное ребро, то (v, w) = (w, v). Далее неориентированный граф мы будем называть просто графом. Говорят, что дуга v  w ведет от вершины v к вершине w, а вершина w смежная с вершиной v, причем ребро (v, w) инцидентно вершинам v и w. Графы: основные понятия и определения Путем называется такая последовательность вершин v1, v2,.., vn, что для всех i, 1 < i < n , существуют дуги/ребра (vi, vi+1), n = |V|. Длина пути равна количеству ребер, составляющих путь, т.е. длина равна n - 1 для пути из n вершин, а ребра образуют цепь. Цепь (маршрут) – это последовательность ребер, соединяющих две вершины (в орграфе – путь). Как особый случай рассмотрим одну вершину v и путь длины 0 от вершины и к этой же вершине – в этом случае имеем петлю. В неориентированном графе, если для вершин vi и vj существует путь vi, vi+1,.., vj, то эти вершины называются связанными. Граф называется связным, если в нем любая пара вершин связанная. Пусть есть граф G = (V, Е) с множеством вершин V и множеством ребер Е. Граф G' = (V’, Е') называется подграфом графа G, если 1. множество V’ является подмножеством множества V; 2. множество Е' состоит из ребер (v, w) множества Е таких, что обе вершины v и w принадлежат V ’. Если множество Е' состоит из всех ребер (v, w) множества Е таких, что обе вершины v и w принадлежат V’, то в этом случае граф G' называется индуцированным подграфом графа G. Графы: основные понятия и определения Путь между вершинами v1 и vn называется простым, если все вершины пути различны, за исключением, возможно, вершин v1 и vn. Цикл — это простой путь длины не менее 1, который начинается и заканчивается в одной и той же вершине. На практике удобно вершинам и/или дугам графа (орграфа) сопоставить какую-либо информацию. Граф называется взвешенным, если каждой дуге поставлено в соответствие какое-либо вещественное число и помеченным - если значение (или метка) соответствует узлу. Для этих целей используется помеченный граф, т.е. граф, у которого каждая дуга и/или каждая вершина имеет соответствующие метки. Вообще, меткой может быть имя, вес или стоимость (дуги), или значение данных какого-либо заданного типа, в т.ч. и символьного. Реализация АТД «Граф»: структура и операторы • • • • • 1. 2. 3. 4. Способы представления множества узлов и дуг Матрица смежности Список смежности Матрица инцидентности Список дуг Операторы АТД «Граф» Добавить узел Добавить дугу Удалить узел Удалить дугу Инициализация структуры Способы реализации графов 1. Матрица смежности Матрица смежности: A Матрица цен: С Способы реализации графов 1. Матрица смежности Матрица смежности: A Матрица цен: СС -- 1133 7 - 7 3 3 2 5 - 9 8 Достоинство представления графа в виде матрицы смежности является простота и возможность реализации и представления операций над графами в матричном виде Способы реализации графов 1. Матрица смежности Матрица смежности: A Матрица цен: СС -- 1133 77 - 7 3 3 2 5 - 9 8 - Способы реализации графов 1. Матрица смежности Матрица смежности: A Матрица цен: С - 13 7 - 7 3 3 2 5 - 9 8 - Есть ошибки в матрице смежности? Способы реализации графов 1. Матрица смежности Матрица смежности: A Матрица цен: С - 13 7 - 7 3 3 8 2 5 - 9 8 - lVl – мощность множества Способы реализации графов 2. Список смежности V he0ad 1 2 3 4 Информационная Служебная части e Способы реализации графов 2. Список смежности V 1 2 3 4 info : {name, mark, label и т.п.} Способы реализации графов 2. Список смежности V а b c d e info (name, mark, label и т.п.) Способы реализации графов 2. Список смежности V head info (name, mark, label и т.п.) Способы реализации графов. 2. Список смежности V head 13 Способы реализации графов. 2. Список смежности V head 7 13 Подумайте, почему узлы расположены именно в такой последовательности? Способы реализации графов. 2. Список смежности V head 7 13 Очередная дуга (смежная вершина) добавляется в голову линейного связанного списка, что обеспечивает трудоемкость добавления очередной дуги O(1) Способы реализации графов. 2. Список смежности V head Поле связи (указатель на следующий смежный узел) Вес (цена) дуги Имя, индекс, адрес смежного узла (ссылка на узел) Способы реализации графов. 2. Список смежности V head 7 13 2 3 3 2 5 9 8 Достоинство представления графа в виде списка смежности является эффективность реализации и представления (сильно)разреженных графов. Способы реализации графов. 2. Список смежности V 7 13 2 3 3 2 5 8 9 Способы реализации графов. 2. Список смежности V 7 13 2 3 3 2 5 8 9 Способы реализации графов. 2. Список смежности V 7 13 2 3 3 2 5 8 9 Способы реализации графов. 2. Список смежности V 7 13 2 3 3 2 5 8 9 Способы реализации графов. 3. Матрица инцидентности Размерность: B[ |V| ] [ |E| ] |Е| (a,d) (a,b) (b,c) (c,a) a b |V| c d e (c,e) (d,c) (d,e) (d,a) (d,b) (e,a) Способы реализации графов. 3. Матрица инцидентности vi 𝑏𝑖,𝑗 В a b c d e 1, если вершина 𝑖 является концом дуги 𝑗 0, если вершина 𝑖 не инцидентна дуге 𝑗 = −1, если вершина 𝑖 является началом дуги 𝑗 2, если дуга 𝑗 является петлей узла 𝑖 (a,d) (a,b) (b,c) (c,a) (c,e) (d,c) (d,e) (d,a) (d,b) (e,a) Способы реализации графов. 3. Матрица инцидентности -1 𝑏𝑖,𝑗 В a b c d e +1 vi 1, если вершина 𝑖 является концом дуги 𝑗 0, если вершина 𝑖 не инцидентна дуге 𝑗 = −1, если вершина 𝑖 является началом дуги 𝑗 2, если дуга 𝑗 является петлей узла 𝑖 (a,d) (a,b) (b,c) (c,a) (c,e) (d,c) (d,e) (d,a) (d,b) (e,a) Способы реализации графов. 3. Матрица инцидентности -1 В a (a,d) (a,b) (b,c) +1 b -1 c d e +1 (c,a) +1 v (c,e) (d,c) (d,e) (d,a) (d,b) (e,a) -1 -1 +1 -1 -1 -1 +1 +1 -1 -1 +1 -1 +1 -1 +1 +1 +1 Способы реализации графов. 3. Матрица инцидентности -1 В (a,d) (a,b) (b,c) +1 v (c,a) (c,e) (d,c) (d,e) (d,a) (d,b) (e,a) a +1 +1 -1 -1 -1 b -1 +1 -1 c -1 +1 +1 -1 d -1 +1 +1 +1 +1 e -1 -1 +1 Способы реализации графов. 3. Матрица инцидентности -1 В (a,d) (a,b) (b,c) +1 v (c,a) (c,e) (d,c) (d,e) (d,a) (d,b) (e,a) a +1 +1 -1 -1 -1 b -1 +1 -1 c -1 +1 +1 -1 d -1 +1 +1 +1 +1 e -1 -1 +1 Способы реализации графов. 4. Список дуг info E v w c a Visited / Unvisited 1 1 4 7 2 1 2 13 2 b True/False 3 2 3 2 3 c {0,1} … 4 d {0,1,2} 5 e {…} V name mark 1 label Особенность реализации в том, что списки узлов и дуг фактически являются массивом представленных структур или таблицами (в реляционных базах данных) соответствующей структуры и не зависит от фактической структуры графа, поэтому могут быть использованы для хранения произвольных графов в реляционной БД. Способы реализации графов. 4. Список дуг V Name mark 1 a Visited / Unvisited 2 b True/False 3 c {0,1} 4 d {0,1,2} 5 e {…} label E v w c 1 1 4 7 2 1 2 13 3 2 3 2 … Способы реализации графов. 4. Список дуг V Name mark 1 a Visited / Unvisited 2 b True/False 3 c {0,1} 4 d {0,1,2} 5 e {…} label E v w c 1 1 4 7 2 1 2 13 3 2 3 2 … Методы (операции) АТД «Граф» 1. ADD_V(<имя>,<метка, mark>) - добавить УЗЕЛ 2. ADD_Е(v, w, c) - добавить ДУГУ (здесь c — вес, цена дуги (v,w)) 3. DEL_V(<имя>) - удалить УЗЕЛ 4. DEL_Е(v, w) - удалить ДУГУ 5. EDIT_V(<имя>, <новое значение метки или маркировки>) - изменить метку (маркировку) УЗЛА 6. EDIT_Е(v, w, <новый вес дуги>) - изменить вес ДУГИ 7. Конструктор, деструктор (при необходимости) узла 8. … а также … Методы АТД «Граф» Часто в программах встречаются операторы, которые неформально можно описать подобно следующему псевдокоду: for каждая вершина w, смежная с вершиной v do { некоторые действия с вершиной w } АТД «Граф» Используя приведенные операторы (функции), процесс просмотра списка смежных с вершиной v всех вершин w будет следующим: for(i=FIRST(v);i>=0;i= NEXT(v,i)) {w=VERTEX(v,i); } // получение адреса // переход к узлу Для просмотра множества смежных вершин необходимы следующие три оператора (операции). 1. FIRST(v) возвращает индекс первой вершины, смежной с вершиной v. Если вершина v не имеет смежных вершин, то возвращается "нулевая" вершина . 2. NEXT(v, i) возвращает индекс вершины, смежной с вершиной v, следующий за индексом i. Если i — это индекс последней вершины, смежной с вершиной v, то возвращается . 3. VERTEX(v, i) возвращает вершину с индексом i из множества вершин, смежных с v. АТД «Граф» АТД «Граф» Используя итераторы можно получить еще более понятный код: for(iterator w = MyG.begin(v); w != MyG.end(v); w++) { // использование узла (*w) } Реализовать самостоятельно! Пример построение матрицы и списка смежности Неориентированный матрица смежности список смежности 2 1 4 3 Ориентированный 2 1 3 4 2 3 0 1 2 3 4 5 4 1 1 2 2 3 3 4 4 1 1 2 3 4 0 1 2 3 4 5 1 1 2 2 3 3 4 4 Пример построение матрицы и списка смежности Неориентированный матрица смежности список смежности 2 1 4 3 Ориентированный 2 1 3 4 1 2 3 4 1 1 1 1 2 3 1 1 1 1 1 0 3 4 2 1 2 3 1 1 1 3 0 1 4 4 1 1 4 1 3 1 2 3 4 1 1 1 1 2 3 1 1 1 1 3 4 2 2 3 1 3 4 4 4 Пример построение матрицы и списка смежности ? Неориентированный 2 1 4 3 Ориентированный 2 1 3 4 Какматрица реализовать такую «матрицу»? смежности список смежности 1 2 3 4 1 1 1 1 2 3 1 1 1 1 1 3 4 2 1 2 3 1 1 1 3 1 4 4 1 1 4 1 3 1 2 3 4 1 1 1 1 2 1 1 1 1 3 4 2 2 3 1 3 4 4 4 3 Пример построение матрицы и списка смежности Неориентированный матрица смежности список смежности 2 1 4 3 ! Симметрия! Ориентированный 2 1 3 4 1 2 3 4 1 1 1 1 2 3 1 1 1 1 1 3 4 2 1 2 3 1 1 1 3 1 4 4 1 1 4 1 3 1 2 3 4 1 1 1 1 2 1 1 1 1 3 4 2 2 3 1 3 4 4 4 3 Вопросы для самопроверки: построение матрицы по графу 1 4 2 3 4 3 1 1 2 2 3 3 4 4 1 2 1 2 3 4 1 1 2 2 3 3 4 4 Вопросы для самопроверки: построение графа по матрице смежности 1 2 3 4 1 1 4 1 1 1 1 2 1 1 1 2 3 1 1 3 4 1 1 1 2 3 4 1 1 1 1 1 1 2 1 1 2 3 1 1 3 4 1 1 3 4 2 1 4 3 2 1 4 Спасибо за внимание!