Название: Алгоритмы - Учебное пособие ( Редактор )

Жанр: Экономика

Просмотров: 1730


1.2. представление графов в эвм

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

1.2.1. Матрица смежности графа

Матрицей смежности помеченного графа с n вершинами называется матрица A = [aij],  i, j = 1, 2, ..., n, в которой

     

Матрица смежности однозначно определяет граф (рис. 1.1, а–в, д–е). Для неориентированного графа матрица A является симметричной относительно главной диагонали. Число единиц в строке равно степени соответствующей вершины. Петля в матрице смежности может быть представлена соответствующим единичным диагональным элементом. Кратные ребра можно представить, позволив элементу матрицы быть больше 1.

Преимуществом такого представления является «прямой доступ» к ребрам графа, т.е. имеется возможность за один шаг получить ответ на вопрос «существует ли в графе ребро (x, y)?» Для небольших графов, когда места в памяти достаточно, с матрицей смежности часто проще работать. Недостаток заключается в том, что независимо от числа ребер объем занимаемой памяти составляет n ´ n или n ´ n/2 – n, если использовать симметрию и хранить только треугольную подматрицу матрицы смежности. Кроме того, каждый элемент матрицы достаточно представить одним двоичным разрядом.

1.2.2. Матрица инцидентности графа

Матрицей инцидентности называется матрица B = [bij], i =1, 2, ..., n, j = 1, 2, ..., m (где n – число вершин, а m – число ребер графа), строки которой соответствуют вершинам, а столбцы – ребрам. Элемент матрицы в неориентированном графе равен:

     

В случае ориентированного графа с n вершинами и m дугами элемент матрицы инцидентности равен:

     

Строки матрицы также соответствуют вершинам, а столбцы – дугам.

Матрица инцидентности однозначно определяет структуру графа (рис. 1.1, а–в, д–ж). В каждом столбце матрицы B ровно две единицы. Равных столбцов нет.

Недостаток данного представления состоит в том, что требуется n´ m единиц памяти, большинство из которых будет занято нулями. Не всегда удобен доступ к информации. Например, для ответа на вопросы «есть ли в графе дуга (x, y)?» или «к каким вершинам ведут ребра из вершины x?» может потребоваться перебор всех столбцов матрицы.

1.2.3. Матрица весов графа

Простой взвешенный граф может быть представлен своей матрицей весов W = [wij], где wij – вес ребра, соединяющего вершины i, j = 1,2, ..., m. Веса несуществующих ребер полагаются равными ∞ или 0 в зависимости от задачи. Матрица весов – простое обобщение матрицы смежности.

1.2.4. Список ребер графа

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

      x = (x0, x1, ..., xm )    и     y = (y0, y1, ..., ym ),

где m –– количество ребер в графе. Каждый элемент в массиве есть метка вершины, а i-е ребро графа выходит из вершины xi и входит в вершину yi. Объем занимаемой памяти составляет в этом случае 2m единиц памяти. Неудобством является большое число шагов, необходимое для получения множества вершин, к которым ведут ребра из данной вершины.

1.2.5. Списки смежных вершин графа

Граф может быть однозначно представлен структурой смежности своих вершин. Структура смежности состоит из списков Adj [x] вершин графа, смежных с вершиной x. Списки Adj [x] составляются для каждой вершины графа. Структура смежности удобно реализуется массивом из n (число вершин в графе)

линейно связанных списков (1.1, а–г). Каждый список содержит

 

                   

а    д

     

1

2

3

4

5

 

 

1

2

3

4

5

1

0

1

1

0

1

 

1

0

1

1

0

0

2

1

0

1

0

0

 

2

0

0

0

0

0

3

1

1

0

1

1

 

3

0

0

0

0

0

4

0

0

1

0

1

 

4

1

1

0

0

0

5

1

0

1

1

0

 

5

0

0

0

1

0

б    е

              

½

1/3

1/5

2/3

3/4

3/5

4/5

 

 

½

1/3

4/1

4/2

5/4

1

1

1

1

0

0

0

0

 

1

1

1

-1

0

0

2

1

0

0

1

0

0

0

 

2

-1

0

0

-1

0

3

0

1

0

1

1

1

0

 

3

0

-1

0

0

0

4

0

0

0

0

1

0

1

 

4

0

0

1

1

-1

5

0

0

1

0

0

1

1

 

5

0

0

0

0

1

в    ж

   

г    з

Рис. 1.1

вершины, смежные с вершиной, для которой составляется список. Список смежных вершин графа дает компактное представление для разреженных графов – тех, у которых множество ребер много меньше множества вершин. Недостаток этого представления таков: если мы хотим узнать, есть ли в графе ребро (x, y), приходится просматривать весь список Adj [x] в поисках y. Объем требуемой памяти составляет для ориентированных n+ m и n+2m для неориентированных графов единиц памяти, где n – число вершин графа, а m – число ребер (дуг) графа. Если в основе алгоритма решения задачи лежат операции добавления и удаления вершин из списков, то хранение списков смежности удобно реализовать, используя связанное представление списков (1.1, д–з).