Связное представление орграфов.

Орграф представляется связным нелинейным списком, если он часто изменяется или если полустепени захода и исхода его узлов велики. Рассмотрим два варианты представления орграфов связными нелинейными списковыми структурами.

В первом варианте используются два типа элементов: атомарный и узел связи. На Рис. 3.5 показана схема такого представления для графа Рис. 3.1. Скобочная запись связей этого графа:

(< A,B >, < B,C >, < C,D >, < B,D >, < D,C >)

Рис. 3.5. Машинное представление графа элементами двух типов

Более рационально представлять граф с использованием списков примыкания. При этом каждый узел содержит указатель на начало связного списка, содержащего указателями на узлы, непосредственно связанными с данным узлом:

struct ListNode

{

struct Graph *pVertex;

struct ListNode *pNext;

};

struct GraphNode

{

struct Data *pData;

struct ListNode *pVertexList;

};

Если с ребрами (или дугами) графа требуется связать некоторую информацию (длину пути, например), то список структур можно модифицировать следующим образом:

struct Arc

{

struct ArcData *pData;

struct Vertex *pBeginVertex;

struct Vertex *pEndVertex;

}

struct ListNode

{

struct Arc *pArc;

struct ListNode *pNext;

};

struct Vertex

{

struct VertextData *pData;

struct ListNode *pArcList;

};

 

Алгоритмы на графах

Алгоритмы обхода графов в глубину и по уровням

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

Обход в глубину

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

Рекурсивный алгоритм обхода в глубину приведен ниже:

DepthFirstTraversal(G,v)

G - граф

v - текущий узел

Visit(v)

Mark(v)

for каждого ребра vw графа G do

if вершина w непомечена then

DepthFirstTraversal(G,w)

end if

end for

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

Обход по уровням

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

BreadthFirstTraversal(G,v)

G граф

v текущий узел

Visit(v)

Mark(v)

Enqueue(v)

while очередь непуста do

Dequeue(x)

for каждого ребра xw в графе G do

if вершина w непомечена then

Visit(w)

Mark(w)

Enqueue(w)

end if

end for

end while

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