Typedef struct CVertex2_

{

CAdjVertex *AdjacentVerticesList_Head; // голова списка смежных вершин int i; // номер текущей вершины

} CVertex2;

CVertex2 vertices[NMax];

Т.о. в каждой вершине графа будет храниться вектор или список смежных вершин к данной вершине.

Имеем следующие времена выполнения интересующих нас операций

· перечисление всех ребер, инцидентных вершине i -------

· перечисление вершин, инцидентных ребру j -------

· перечисление всех вершин, смежных с вершиной i T=O(N)

· проверка смежности двух вершин T=O(N)

· проверка смежности двух ребер -------

Реберный список с двойными связями (РСДС) (для плоской укладки планарных графов)

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

Typedef struct SEdge_

{

Int vertex0, vertex1;

Int edge0,edge1;

Int face0,face1;

}SEdge;

здесь vertex0, vertex1 – номера первой и второй вершины ребра. Порядок вершин задает ориентацию. edge0 – номер первого ребра (в массиве элементов Sedge), выходящего из вершины vertex0, взятого против часовой стрелки (при обходе ребер из вершины vertex0), edge1 – первое ребро, выходящее из вершины vertex1, взятое против часовой стрелки (при обходе ребер из вершины vertex1). face0 – номер грани, находящейся слева от направленного отрезка (vertex0, vertex1), face1 – номер грани, находящейся справа от направленного отрезка (vertex0, vertex1).

Вместо структуры можно использовать массив из шести целых чисел.

На следующем рисунке показан пример графа. Стрелками на ребрах указан порядок вершин в узлах РСДС, соответствующих ребрам. Стрелками между ребрами указаны ссылки на ребра из соответствующих узлов РСДС.

Для данного графа РСДС будет представлен следующим массивом улов:

{

{1,2, 5,2, 1,4},

{2,4, 1,7, 1,4},

{1,3, 1,4, 4,2},

{3,4, 6,5, 3,2},

{1,4, 3,2, 2,1},

{5,3, 7,3, 3,4},

{4,5, 4,6, 3,4}

}

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

Лекция 8

Структуры данных. Графы.

---

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