Файл: Лекции СД.doc

V0 v1 v2 v5 v6 v3 v4 v7 v8 v9 v10 (v0) (v1) (v7) (v8) (v9) (v10) (v3) (v2) (v4) (v5) (v6)

а). б).

V0

V0

V8

в). г).

Рис. 7.2. Представление дерева: а) исходное дерево,

б) оглавление книг, в) граф, г) диаграмма Венна.

2. 7.2. Машинное представление графов

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

При представлении в виде списочной структуры, используется два типа списков – список вершин и список ребер. Элемент списка вершин содержит поле данных и два указателя. Один указатель связывает данный элемент с элементом другой вершины. Второй указатель связывает элемент списка вершин со списком ребер, связанных с данной вершиной.

Для ориентированного графа используют список дуг, исходящих из вершины (рис. 7.3). Элемент списка дуг состоит только из двух указателей. Первый указатель используется для того, чтобы показать в какую вершину дуга входит, а второй – для связи элементов в списке дуг вершины.

а).

(c,d)

б).

Рис. 7.3. Представление графа (а) в виде списочной структуры (б).

Распространенным способом представления графов является матричный способ (рис. 7.4). Для ненаправленных графов обычно используют матрицы смежности, а для ориентированных графов – матрицы инцидентности. Обе матрицы имеют размерность n², где n – число вершин в графе.

При использовании матриц смежности их элементы представляются в памяти элементами массива. Элемент матрицы имеет ноль в позиции m(i,j), если не существует ребра, связывающего вершину i с вершиной j, или единичное значение в позиции m(i,j), если такое ребро существует:

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

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

Правила построения матрицы инцидентности аналогичны правилам построения матрицы смежности. Разница состоит в том, что единица в позиции m(i,j) означает выход дуги из вершины i и вход дуги в вершину j.

В некоторых матричных алгоритмах обработки графов используются матрицы путей. Под путем длиной k из вершины i в вершину j будем понимать возможность попасть из вершины i в вершину j за k переходов, каждому из которых соответствует одна дуга. Одна матрица путей m_k содержит сведения о наличии всех путей одной длины k в графе. Единичное значение в позиции (i,j) означает наличие пути длины k из вершины i в вершину j:

Например, при k=2 имеем (<A,B>,<B,C>).

Примеры построения матриц смежности и инцидентности показаны на рис. 7.14. В первой матрице не отражены направления, поэтому a(i,j) = a(j,i), т.е. матрица симметрична относительно главной диагонали.

Рис. 7.4. Граф и его матричное представление.

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

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

Матрица m₁ полностью совпадает с матрицей инцидентности. По матрице m₁ можно построить m₂ , а по матрице m₂ можно построить m₃ и т.д. Если граф является ациклическим, то число матриц путей ограничено. В противном случае матрицы будут повторяться до бесконечности с некоторым периодом, связанным с длиной циклов. Матрицы путей не имеет смысла вычислять до бесконечности. Достаточно остановиться в случае повторения матриц.

Матрица путей m1.

Матрица путей m2.