Зважений граф

A weighted graph G = (V,E,W) is a graph where each edge e in E has a weight denoted by W(e)

Рис.4 Зважений граф

The weight of a Graph is the sum of the weights of the edges of the graph

2. Представлення графів

Рис. 5 Граф

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

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

Так граф, приведенный на рис. будет храниться так

V = {1,2,3,4,5}

E = {(1,2), (1,3), (1,4), (1,5), (2,3), (3,4), (4,5),(5,2)}

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

Далее рассматриваются более эффективные представления графов.

Матриця суміжності

Вершины графа со всей информацией о них можно хранить в массиве – это обеспечивает быстрый доступ и не вносит дополнительных сложностей. Пусть вся информация представления в виде полей некоторого класса Vertex. Тогда для хранения V вершин нам понадобится массив.

Vertex[] v = new Vertex[V];

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

Для этого можно использовать так называемую матрицу смежности. Эта матрица представляет из себя квадратный массив VxV чисел, где N – число вершин в графе.

int[][] m = new int[V][V];

Информация о ребрах хранится так (будем считать граф ориентированным): в ячейке m[i, j] хранится количество ребер из вершины v[i] в вершину v[j]. То есть для ориентированного графа с рис. 1 матрица будет такой:

1. Для неорієнтованого графа

2. Для орієнтованого графа

3. Для зваженого графа

Зручно:

· Добавляти і видаляти ребра

· Перевіряти суміжність вершин

Незручно

· Добавляти і видаляти вершини

· Працювати з розрідженими графами

Если необходимо хранить дополнительную информацию о ребрах (например, «пропускную способность» или что-то еще), можно хранить матрицу из указателей на объекты, в которых хранится соответствующая информация. Нет объекта – нет ребра.

Матриця інцидентності

1. Для неорієнтованого графа

	A	B	C	D	E	F	G	H

2. Для орієнтованого графа

3. Для зваженого графа

Зручно:

· Міняти навантаження на ребра

· Перевіряти інцидентність

Незручно

· Добавляти і видаляти вершини

· Працювати з розрідженими графами

Списки суміжності

Зручно:

· Шукати вершини суміжні з даною

· Добавляти ребра і вершини

· Працювати із розрідженими графами

Незручно

· Перевіряти присутність ребра

· Видаляти ребра і вершини

Дата добавления: 2015-10-13