Способы задания графов матрицы смежности для графа

Способы задания графов матрицы смежности для графа

Граф – совокупность точек, соединенных линиями. Точки называются вершинами , или узлами , а линии – ребрами , или дугами .

Степень входа вершины – количество входящих в нее ребер, степень выхода – количество исходящих ребер.

Граф, содержащий ребра между всеми парами вершин, является полным .

Встречаются такие графы, ребрам которых поставлено в соответствие конкретное числовое значение, они называются взвешенными графами , а это значение – весом ребра .

Когда у ребра оба конца совпадают, т.е. оно выходит из вершины и входит в нее, то такое ребро называется петлей .

Классификация графов

Графы делятся на

• связные
  
• несвязные
  

В связном графе между любой парой вершин существует как минимум один путь.

В несвязном графе существует хотя бы одна вершина, не связанная с другими.

Графы также подразделяются на

• ориентированные
  
• неориентированные
  
• смешанные.

В ориентированном графе ребра являются направленными, т.е. существует только одно доступное направление между двумя связными вершинами.

В неориентированном графе по каждому из ребер можно осуществлять переход в обоих направлениях.

Частный случай двух этих видов – смешанный граф. Он характерен наличием как ориентированных, так и неориентированных ребер.

Способы представления графа

Граф может быть представлен (сохранен) несколькими способами:

• матрица смежности;
• матрица инцидентности;
• список смежности (инцидентности);
• список ребер.

Использование двух первых методов предполагает хранение графа в виде двумерного массива (матрицы). Размер массива зависит от количества вершин и/или ребер в конкретном графе.

Матрица смежности графа — это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1.
Число строк матрицы смежности равно числу столбцов и соответствует количеству вершин графа.

• 0 – соответствует отсутствию ребра,
• 1 – соответствует наличию ребра.

Когда из одной вершины в другую проход свободен (имеется ребро), в ячейку заносится 1, иначе – 0. Все элементы на главной диагонали равны 0 если граф не имеет петель.

Матрица инцидентности (инциденции) графа — это матрица, количество строк в которой соответствует числу вершин, а количество столбцов – числу рёбер. В ней указываются связи между инцидентными элементами графа (ребро(дуга) и вершина).

В неориентированном графе если вершина инцидентна ребру то соответствующий элемент равен 1, в противном случае элемент равен 0.

В ориентированном графе если ребро выходит из вершины, то соответствующий элемент равен 1, если ребро входит в вершину, то соответствующий элемент равен -1, если ребро отсутствует, то элемент равен 0.

Матрица инцидентности для своего представления требует нумерации рёбер, что не всегда удобно.

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

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

Преимущества списка смежности:

• Рациональное использование памяти.
• Позволяет быстро перебирать соседей вершины.
• Позволяет проверять наличие ребра и удалять его.

Недостатки списка смежности:

• При работе с насыщенными графами (с большим количеством рёбер) скорости может не хватать.
• Нет быстрого способа проверить, существует ли ребро между двумя вершинами.
• Количество вершин графа должно быть известно заранее.
• Для взвешенных графов приходится хранить список, элементы которого должны содержать два значащих поля, что усложняет код:
  • номер вершины, с которой соединяется текущая;
  • вес ребра.

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

Какой способ представления графа лучше? Ответ зависит от отношения между числом вершин и числом рёбер. Число ребер может быть довольно малым (такого же порядка, как и количество вершин) или довольно большим (если граф является полным). Графы с большим числом рёбер называют плотными , с малым — разреженными . Плотные графы удобнее хранить в виде матрицы смежности, разреженные — в виде списка смежности.

Алгоритмы обхода графов

Основными алгоритмами обхода графов являются

Поиск в ширину подразумевает поуровневое исследование графа:

• вначале посещается корень – произвольно выбранный узел,
• затем – все потомки данного узла,
• после этого посещаются потомки потомков и т.д.

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

• 0 — оранжевый – необнаруженная вершина;
• 1 — зеленый – обнаруженная, но не посещенная вершина;
• 2 — серый – обработанная вершина.

Фиолетовый – рассматриваемая вершина.

Применения алгоритма поиска в ширину

• Поиск кратчайшего пути в невзвешенном графе (ориентированном или неориентированном).
• Поиск компонент связности.
• Нахождения решения какой-либо задачи (игры) с наименьшим числом ходов.
• Найти все рёбра, лежащие на каком-либо кратчайшем пути между заданной парой вершин.
• Найти все вершины, лежащие на каком-либо кратчайшем пути между заданной парой вершин.

Алгоритм поиска в ширину работает как на ориентированных, так и на неориентированных графах.
Для реализации алгоритма удобно использовать очередь.

Реализация на C++ (с использованием очереди STL)

Результат выполнения

Задача поиска кратчайшего пути
Реализация на С++

Поиск в глубину – это алгоритм обхода вершин графа.

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

Отсутствие последнего свидетельствует об одной из двух возможных ситуаций:

• все вершины графа уже просмотрены,
• просмотрены вершины доступные из вершины, взятой в качестве начальной, но не все (несвязные и ориентированные графы допускают последний вариант).

Каждая вершина может находиться в одном из 3 состояний:

• 0 — оранжевый – необнаруженная вершина;
• 1 — зеленый – обнаруженная, но не посещенная вершина;
• 2 — серый – обработанная вершина;

Фиолетовый – рассматриваемая вершина.

Применения алгоритма поиска в глубину

• Поиск любого пути в графе.
• Поиск лексикографически первого пути в графе.
• Проверка, является ли одна вершина дерева предком другой.
• Поиск наименьшего общего предка.
• Топологическая сортировка.
• Поиск компонент связности.

Алгоритм поиска в глубину работает как на ориентированных, так и на неориентированных графах. Применимость алгоритма зависит от конкретной задачи.
Для реализации алгоритма удобно использовать стек или рекурсию.

Реализация на C++ (с использованием стека STL)

Результат выполнения

Задача поиска лексикографически первого пути на графе.
Реализация на C++

Результат выполнения

Поиск в глубину также может быть реализован с использованием рекурсивного алгоритма.

Реализация обхода графа в глубину на C++ (с использованием рекурсии)

Источник

3.2. Матричные способы задания графов

Для алгебраического задания графов используются матри­цы смежности и инцидентности.

Матрица смежности A = (a_ij) определяется одинаково для ориентиро­ванного и неориентированного графов. Это квадратная матрица порядкаn, гдеn — число вершин, у которой

a_ij=

Матрица смежности графа, изображенного на рис. 3.1, имеет вид:

A =

Матрица смежности ориентированного графа, изображенного на рис. 3.2, имеет вид:

A =

Матрица смежности полностью задает граф.

Матрицей инцидентности B = (b_ij) ориентированного графа называет­ся прямоугольная матрица (n ´ m), где n – число вершин,m – число ребер, у которой

b_i=

Для неориентированного графа матрица инцидентности B задается следующим образом:

b_i=

Матрица инцидентности графа, изображенного на рис. 3.1, имеет вид:

B =

Матрица инцидентности ориентированного графа, изображенного на рис. 3.2, имеет вид:

B =

Матрица инцидентности, также, как и матрица смежности, полностью задает граф.

Матрицы смежности и инцидентности удобны для задания графов на ЭВМ.

3.3 Основные свойства матриц смежности и инцидентности

1. Матрица смежности неориентированного графа является симметричной. Для ориентированного графа это, вообще говоря, неверно.

2. Сумма элементов i — ой строки илиi -го столбца матрицы смежности неориентированного графа равна степени вершиныx_i.

3. Сумма элементов i — ой строки матрицы смежности ориентированного графа равна числу дуг, исходящих изx_i.4. Сумма элементовi — го столбца матрицы смежности ориентиро­ванного графа равна числу дуг, входящих в вершинуx_i.

5. Сумма строк матрицы инцидентности ориентированного графа является нулевой строкой.

Итак, возможны следующие различные способы задания графа:

а) посредством графического изображения;

б) указанием множества вершин и множества ребер (дуг);

в) матрицей смежности;

г) матрицей инцидентности.

3.4. Маршруты, циклы в неориентированном графе

Пусть G — неориентированный граф.Маршрутом илицепью вG называется такая последовательность (конечная или бесконечная) реберa₁,a₂. a_n. что каждые соседние два ребраa_i иa_i+1 имеют общую инцидентную верши­ну. Одно и то же ребро может встречаться в маршруте несколько раз. В конечном маршруте (a₁,a₂. a_n) имеется первое реброa₁ и последнее реброa_n. Вершинаx₁, инцидентная ребруa₁, но не инцидентная ребруa₂, называется началом маршрута, а вершинаx_n, инцидентная ребруa_n, но не инцидентная ребру a_n-1, называется концом маршрута.

Длиной (илимощностью) маршрута называется число ребер, входящих в маршрут, причем каждое ребро считается столько раз, сколько оно вхо­дит в данный маршрут.

Замкнутый маршрут называется циклом.

Маршрут (цикл), в которой все ребра различны, называется простой цепью(циклом). Маршрут (цикл), в которой все вершины, (кроме первой и последней), различны, называетсяэлементарной цепью(циклом).

В приведенном на рис 3.6 графе выделим следующие маршруты:

(a₁,a₃,a₄) – простая элементарная цепь длины 3, т.к. все ребра и вершины попарно различны;

(a₂,a₄,a₃) – простой элементарный цикл, т.к. это замкнутый маршрут, у которого все ребра и верши­ны, кроме первой и последней, различны;

(a₁,a₂,a₄,a₃) – цепь, которая является простой, но не элементарной, т.к. все ребра различны, но вершинаx₂встречается дважды;

(a₁,a₂,a₂) –маршрут длины 3, не являющийся ни простой, ни элементарной цепью, т.к. реброa₂ и вершинаx₂встречаются дважды.

Источник