Приведем сравнительную характеристику существующих способов представления графа в памяти ЭВМ, их достоинства и недостатки.
Рассмотрим конечный граф G = (V, E), где |V | = n, |E| = m.
Матрица инциденций. Ориентированный граф задается прямоугольной матрицей B(n´m), элементы которой определяются по правилу:
где a – любое натуральное число, отличное от 1. У неориентированного графа оба элемента матрицы, соответствующие вершинам, инцидентным ребру ej, равны 1.
Это представление графа является самым неудобным, так как объем занимаемой памяти равен n×m единиц, причем в каждом столбце только две ненулевые ячейки. Кроме нерационального использования памяти недостатком этого способа представления является неудобный доступ к информации. Например, для ответа на вопросы:
а) существует ли ребро (дуга) (vi, vj);
б) к каким вершинам ведут ребра (дуги) из вершины vi
требуется, в худшем случае, перебор n×m элементов, т.е. порядка n×m шагов алгоритма. От этого недостатка свободен следующий способ представления графа.
|
|
Матрица смежности. Элементы квадратной матрицы A(n´n) определяются следующим образом:
Такая форма эквивалентна матричному представлению бинарного отношения (см. тема “Отношения”). Проверка существования ребра (дуги) (vi, vj) осуществляется за один шаг, в отличие от матрицы инциденций, однако, проверка свойств графа на основе такого представления требует, в худшем случае, порядка n2 шагов алгоритма. При этом способе объем неиспользованной памяти по-прежнему велик.
При работе со взвешенными графами для хранения весов ребер (дуг) требуются дополнительные одномерные массивы размера m (для случая матрицы инциденций) или матрицы размера n´n (для случая матрицы смежности). Это обстоятельство делает неприемлемым использование матрицы смежности для взвешенных графов, так как количество неиспользованных единиц памяти увеличивается в k раз, гдеk – число весов ребер (дуг).
Таблица ребер. Она представляет собой матрицу размером m´2, каждая строка которой содержит вершины инцидентные i-му ребру (i-ой дуге). Для работы со взвешенными графами нужно добавить к матрице столбцы, соответствующие весам ребер (дуг). Такая форма эквивалентна табличному представлению бинарного отношения
Однако, этому способу представления графа присущ тот же недостаток, что и матрице инциденций, – неудобство доступа к информации, хотя число шагов при поиске ребра здесь значительно меньше (порядка m). Наиболее удобной и экономичной формой представления графа являются
Списки инцидентности. Для каждой вершины viÎV создается список записей, характеризующих ребра (дуги), инцидентные этой вершине. Таким образом, это представление использует объем памяти порядка n + m, поиск вершины смежной с данной требует порядка n + m шагов, проверка свойств графа осуществляется за число шагов порядка n. Такая форма эквивалентна представлению бинарного отношения в виде верхних срезов.