Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 108 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова .
Недостаток данного способа представления состоит в том, что требуется
m*n ячеек памяти, большинство из которых заполнены нулями.
2. Матрица смежности.
A(n, n)={ a
i j
},
где n – число вершин.
1, вершина i смежна вершине j
a
i j
=
0, вершины i и j не смежны
В случае взвешенного графа элементу a
ij
вместо 1 присваивается значе-
ние соответствующего веса, а вместо 0 – большое число, обозначающее бес-
конечность (в текстах программ большое число обозначается
MAX_INT = 10
6
). Эта матрица является симметричной с нулями на главной
диагонали. Число единиц в строке равно степени соответствующей вершины.
Приведем пример матрицы смежности для графа, изображенного на рис.
7.1.
1 2 3 4
1 0 1 1 0
A =
2 1 0 1 0
3 1 1 0 1
4 0 0 1 0
Преимуществом данного способа является легкость получения информа-
ции о существовании ребра между двумя вершинами. По сравнению с преды-
дущим способом требуется меньшее количество памяти для графа с большим
числом ребер. Недостатком считается постоянный размер матрицы, не завися-
щий от числа ребер графа.
3. Список ребер.
Граф представляется в виде списка (массива) элементов, хранящих ин-
формацию про одно ребро (номер начальной и конечной вершин, длина ребра
и пр.)
4. Динамический список смежности (хэш-таблица).
В данном случае создается массив списков по количеству вершин графа.
108
А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                    .
   Недостаток данного способа представления состоит в том, что требуется
m*n ячеек памяти, большинство из которых заполнены нулями.

    2. Матрица смежности.
    A(n, n)={ a i j },
    где n – число вершин.

             1, вершина i смежна вершине j
    a ij =
             0, вершины i и j не смежны

     В случае взвешенного графа элементу aij вместо 1 присваивается значе-
ние соответствующего веса, а вместо 0 – большое число, обозначающее бес-
конечность (в текстах программ большое число обозначается
MAX_INT = 106). Эта матрица является симметричной с нулями на главной
диагонали. Число единиц в строке равно степени соответствующей вершины.
     Приведем пример матрицы смежности для графа, изображенного на рис.
7.1.
                                          1         2   3   4
                               1          0         1   1   0
                               2          1         0   1   0
                        A=
                               3          1         1   0   1
                               4          0         0   1   0


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

    3. Список ребер.
    Граф представляется в виде списка (массива) элементов, хранящих ин-
формацию про одно ребро (номер начальной и конечной вершин, длина ребра
и пр.)

    4. Динамический список смежности (хэш-таблица).
    В данном случае создается массив списков по количеству вершин графа.

                                              108

Страницы