Как сделать матрицу смежности по графу

Обновлено: 07.07.2024

Java-структура данных-граф (смежная матрица и список смежности)

1. Введение и принцип действия схемы

1.1 Основные понятия графов

Граф состоит из набора вершин и набора ребер.Для графа G набор вершин и набор ребер обозначаются как V (G) и E (G) соответственно. В зависимости от того, является ли набор ребер графа направленным, граф можно разделить на ориентированные графы и неориентированные графы.В зависимости от того, имеет ли граф веса, его можно разделить на правильные графы и невесомые графы.

Основная терминология для диаграмм:

1: Соседние точки ---- В неориентированном графе, если существует ребро (Vi, Vj), то Vi, Vj - две конечные точки этого ребра, и они называются смежными точками;

2: Out / in edge ----- В ориентированном графе, если существует ребро , это ребро называется внешним ребром вершины Vi и ребром in вершины Vj;

3: Степень / In-deg / Out-Степень - Степень в неориентированном графе определяется как число ребер с вершиной в качестве конечной точки и обозначается как D (V). Степень направленности ориентированного графа определяется как количество ребер, указывающих на вершину, а степень наружности - это число внешних ребер вершины;

1.2 Матрица смежности представления графа

Существует два способа представления графиков: представление двумерного массива (смежная матрица) и представление связанного списка (смежный список).

Матрица смежности - это матрица, представляющая смежные отношения между вершинами графа. Для графа с n вершинами строки и столбцы матрицы представляют 1 . n точек. Для неориентированных графов, если вершины b1 и b2 соединены, то значения матрицы [b1, b2] и matrix [b2, b1] в двумерной матрице устанавливаются на 1. Если ориентированный граф b1 указывает на b2, то матрица [b1, b2] = 1, matrix [b2, b1] = 0. В следующем примере показана матрица смежности неориентированного графа и ориентированного графа;



Нет ориентированный граф ориентированный граф

Вышеуказанный неориентированный граф представлен матрицей смежности следующим образом: Если ориентированный граф представлен матрицей смежности:



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

1.3 список смежности представления графа

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


Значок таков, что узел, связанный с узлом 0, равен 1 2 3 4, узел, связанный с узлом 1, равен 0 4, а узел, связанный с узлом 2, равен 0. 4 5 .

2, реализация графа

2.1, представление матрицы смежности

Массив набора ребер используется для хранения информации о ребре, включая начало, конец и вес ребра. Краевые узлы определяются следующим образом:

Определяет интерфейс графа. Код выглядит следующим образом:

Создайте матрицу смежности графа на основе набора ребер графа.Есть четыре типа графиков: ориентированный взвешенный, направленный невзвешенный, ненаправленный взвешенный и ненаправленный невзвешенный. Есть четыре ситуации для рассмотрения. Возьмите информацию fromvex, endvex, weight для граничного узла. Если он не направленный и невесомый, то a [fromvex] [endvex] = a [endvex] [fromvex] = 1, если он ненаправленный, то a [fromvex] [endvex] = a [endvex] [fromvex] = вес; если он направлен невзвешенным, то a [fromvex] [endvex] = 1; если он направлен взвешенно, то [fromvex] [endvex] = вес; Код реализации конкретной схемы построения выглядит следующим образом:

Вставьте ребро в график. Если ребро не существует в текущем графе, вам следует изменить значение элемента данных e, представляющего число ребер в графе, чтобы увеличить его на 1, а затем завершить вставку. Если оно уже существует, вам нужно только изменить его. Вес края. Код выглядит следующим образом:

Удалите ребро из графика. Если ребро не существует, выйдите из функции напрямую. Если ребро существует, то для неориентированных графов удалите [fromvex] [endvex], а также удалите [endvex] [ fromvex], для ориентированного графа необходимо удалить только [fromvex] [endvex]. Реализация заключается в следующем:

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

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

Поиск по всему графику, поисковый график делится на глубокий поиск и поиск по ширине.

2.2 Граф представления списка смежности (потому что это не так уж сложно реализовать, поэтому код не объясняет слишком много)

Определение узла списка смежности хранит указанный узел, вес узла и следующий узел, указанный узлом. Конкретный код реализован следующим образом:

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

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

Вставьте код ребра в график:

Удалите код ребра из диаграммы:

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

Выходной код списка смежности в матрицу смежности выглядит следующим образом:

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

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

Исходный граф

Списки смежности:

Списки ребёр:

Матрица смежности и матрица инцидентности

Матрица смежности:

Матрица инцидентности:

Алгоритм Дейкстры

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

Введем также матрицы смежности и инцидентности для неориентированных графов. Пусть G = (V, X) – граф, где V=v1, v2, …,vn>, X=x1, x2, …, xm>.

Определение. Матрицей смежности графа G называется квадратная матрица A(G)=[aij] порядка n, у которой

Определение. Матрицей инцидентности графа G называется (n m) –матрица B(G)=[bij], у которой

С помощью введенных матриц удобно задавать графы для обработки на ЭВМ. Используя матрицу смежности легко определить локальные степени вершин графа: сумма элементов матрицы по строке равна локальной степени соответствующей вершины.


Для орграфов по строке определяются полустепени исхода, по столбцам – полустепени захода.

Пример 72.

Построить матрицы смежности и инцидентности для графа G = (V, X) (рис. 3.7).

Рис. 3.7. Граф для примера 72

Матрица смежности имеет вид

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

Для того, чтобы построить матрицу инцидентности необходимо пронумеровать ребра графа (рис. 3.8). Матрица инцидентности имеет вид:

Рис. 3.8. Граф с нумерованными ребрами для примера 72

Напомним, что в строках указываются вершины, в столбцах – ребра. Матрица инцидентности может быть как квадратной, так и прямоугольной.

Пример 73.

Построить матрицы смежности и инцидентности для орграфа D= (V, X) (рис. 3.9).

Рис. 3.9. Орграф для примера 73

Матрица смежности имеет вид

Матрица инцидентности имеет вид

Срочно?
Закажи у профессионала, через форму заявки
8 (800) 100-77-13 с 7.00 до 22.00


Материал представлен на сайте исключительно в ознакомительных целях.
Все права принадлежат авторам этих материалов.

Пусть G — граф (ориентированный граф). Пусть В — матрица, строки которой соответствуют вершинам графа и столбцы соответствуют тем же вершинам в том же самом порядке. Элемент /-й строки и j-го столбца матрицы В, обозначаемый Ь^, равен:

  • • 1, если имеется ребро (ориентированное ребро) из /-й вершины в j-ю вершину;
  • • 0 в противном случае.

Матрица В называется матрицей смежности графа G.

Рассмотрим еще раз граф С:


Его матрица смежности имеет вид


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

Важным применением матрицы смежности является возможность находить пути фиксированной длины к.

Сформулируем свойства графа. Пусть С — граф (ориентированный граф) с вершинами v,, v2. v и матрицей смежности А.

  • 1. Путь длиной к, или A-путь, из v. в v. для 1 2 vА° 3 v. vА° т . Тогда atj = 1 тогда и только тогда, когда существует путь из v(. В Vj.
  • 4. Пусть А 1 = 1 v Av A° 2 v A^v..^ А° т , где / — мультипликативная единичная матрица. Тогда at = 1 для всех i и j тогда и только тогда, когда граф G сильно связный.

Правила построения кода Грея для к + 1 состоят в следующем.

  • 1. Поместить 1 перед каждой вершиной в ^-списке ^-мерного куба. Вершины, смежные в /с-мерном кубе, с приставленной впереди 1 остаются смежными в (к + 1)-мерном кубе.
  • 2. Поместить 0 перед каждой вершиной в реверсированном ^-списке ^-мерного куба. Вершины, смежные в ^-мерном кубе, с приставленным впереди 0 остаются смежными в (к + 1)-мерном кубе.
  • 3. Разместить последовательность, сформированную в пункте 2, после последовательности, сформированной в пункте 1.
  • 4. Каждая последовательная пара вершин в (к + 1)-мерном списке (к + 1)-мерного куба является смежной. Первая вершина (к + 1)-списка также является смежной с последней вершиной списка.

Под сеткой понимают граф, вершины которого заданы массивом размера т х п и для которого две вершины, соседствующие в одной и той же строке или столбце массива, являются смежными как вершины графа. Возможно ли для т к и п 1 построить подграф (к + /)-мерного куба,

т.е. сетку размера т х п! Это уже делалось при построении карт Карно. Указанное легко сделать, обозначая строки согласно первым т элементам кода Грея для к, а столбцы согласно первым п элементам кода Грея для /. Элемент на позиции (/',у) сетки есть метка /-й строки, за которой следует метка у-го столбца. Таким образом, если необходимо построить сетку 3x7, она будет иметь вид

Читайте также: