9) Представление графов в эвм

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

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

3. ^

Матрица инциденций

Представление графа с помощью матрицы Н: array [l..p, l..q] of 0..1 (для оргра­фов Н: array [l..p, l..q] of -1..1), отражающей инцидентность вершин и ребер, называется матрицей инциденций, где для неориентированного графа: а для ориентированного графа Пример

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

10 ) По своей сути алгоритм поиска пути ищет на графе, начиная с одной (стартовой) точки и исследуя смежные узлы до тех пор, пока не будет достигнут узел назначения (конечный узел). Кроме того, в алгоритмы поиска пути в большинстве случаев заложена также цель найти самый короткий путь. Некоторые методы поиска на графе, такие как поиск в ширину, могут найти путь, если дано достаточно времени. Другие методы, которые «исследуют» граф, могут достичь точки назначения намного быстрее. Здесь можно привести аналогию с человеком, идущим через комнату. Человек может перед началом пути заранее исследовать все характеристики и препятствия в пространстве, вычислить оптимальный маршрут и только тогда начать непосредственное движение. В другом случае человек может сразу пойти в приблизительном или предполагаемом направлении цели и потом, уже во время пути, делать корректировки своего движения для избегания столкновений с препятствиями.

11) Топологическая сортировка — упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин.

Для графа 

существует несколько согласованных последовательностей его вершин, которые могут быть получены при помощи топологической сортировки, например:

• 

• 

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

12) Алгоритм Дейкстры Вход:

G= (V, E) – ориентированный граф,

v₀ ÎV – источник,

c : E ®R⁺ – функция стоимости ребер графа G.

Полагаем , что

c(v_i, v_j ) = +∞, если (v_i, v_j ) ÏЕ

c (v, v) = 0.

Выход:

для всех вершин v Î V наименьшая сумма стоимостей ребер из E, взятая по всем путям, идущим из v₀ в v.

Метод:

Строим такое множество S Í V, что кратчайший путь из источника в каждый узел v ÎS целиком лежит в S.

Массив D[v] содержит стоимость текущего кратчайшего пути из v₀ в v.

13 ) Пусть l(v) — длина кратчайшего пути из вершины a в вершину v. Докажем по индукции, что в момент посещения любой вершины z, d(z)=l(z). База. Первой посещается вершина a. В этот момент d(a)=l(a)=0. Шаг. Пускай мы выбрали для посещения вершину  . Докажем, что в этот момент d(z)=l(z). Для начала отметим, что для любой вершины v, всегда выполняется  (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть P — кратчайший путь из a в z, y — первая непосещённая вершина на P, x — предшествующая ей (следовательно, посещённая). Поскольку путь P кратчайший, его часть, ведущая из a через x в y, тоже кратчайшая, следовательно l(y)=l(x)+w(xy). По предположению индукции, в момент посещения вершины x выполнялось d(x)=l(x), следовательно, вершина y тогда получила метку не больше чем d(x)+w(xy)=l(x)+w(xy)=l(y). Следовательно, d(y)=l(y). С другой стороны, поскольку сейчас мы выбрали вершину z, её метка минимальна среди непосещённых, то есть  . Комбинируя это с  , имеем d(z)=l(z), что и требовалось доказать.

Поскольку алгоритм заканчивает работу, когда все вершины посещены, в этот момент d=l для всех вершин.

Алгоритм флойда

Пусть вершины графа   пронумерованы от 1 до   и введено обозначение   для длины кратчайшего пути от   до  , который кроме самих вершин   проходит только через вершины  . Очевидно, что   — длина (вес) ребра  , если таковое существует (в противном случае его длина может быть обозначена как  ).

Существует два варианта значения  :

1. Кратчайший путь между   не проходит через вершину  , тогда 

2. Существует более короткий путь между  , проходящий через  , тогда он сначала идёт от   до  , а потом от   до  . В этом случае, очевидно, 

Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений.

Тогда рекуррентная формула для   имеет вид:

 — длина ребра 

Алгоритм Флойда-Уоршелла последовательно вычисляет все значения     для   от 1 до  . Полученные значения   являются длинами кратчайших путей между вершинами 

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

Обходы : в глубину ,в ширину

1. Прямой (префиксный ) обход:

   • посетить корень r;

   • посетить в прямом порядке поддеревья с корнями v₁, v₂,…, v_n .

2. Обратный (постфиксный) обход:

   • посетить в обратном порядке поддеревья с корнями v₁, v₂,…, v_n;

   • посетить корень r.

3. Внутренний ( инфиксный) обход для бинарных деревьев:

   • посетить во внутреннем порядке левое поддерево корня r (если существует);

   • посетить корень r;

   • посетить во внутреннем порядке правое поддерево корня r (если существует).

Рекурсивная реализация

#include <stdio.h>

#include<stdlib.h>

//структура для описания узла дерева

struct tree

{

int data;

struct tree *lchild, *mchild, *rchild;

};

struct tree *my_insert(struct tree *p,int n, int dir);

void inorder(struct tree *p);

void preorder(struct tree *p);

void postorder(struct tree *p);