Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Топ:
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Интересное:
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Дисциплины:
2018-01-05 | 103 |
5.00
из
|
Заказать работу |
|
|
Орграф представляется связным нелинейным списком, если он часто изменяется или если полустепени захода и исхода его узлов велики. Рассмотрим два варианты представления орграфов связными нелинейными списковыми структурами.
В первом варианте используются два типа элементов: атомарный и узел связи. На Рис. 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
Этот алгоритм заносит в очередь корень дерева обхода по уровням, но затем немедленно удаляет его из очереди. При просмотре соседних с корнем вершин он заносит их в очередь. После посещения всех соседних с корнем вершин происходит возвращение к очереди и обращение к первой вершине оттуда. Поскольку узлы добавляются к концу очереди, ни одна из вершин, находящихся на расстоянии двух ребер от корня, не будет рассмотрена повторно, пока не будут обработаны и удалены из очереди все вершины на расстоянии одного ребра от корня.
|
|
|
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!