СТРУКТУРЫ ДАННЫХ Лектор Спиричева Наталия Рахматулловна Ст. преподаватель каф

Информационных технологий

компетенций:

знать методы представления древовидных структур в памяти ЭВМ
знать и уметь

применять алгоритмы поиска путей в графах

путей в графах

элементов, называемых узлами.

Корень - узел, не имеющий исходного. Все узлы,

кроме корня, имеют только один исходный. Есть деревья, состоящие из одного корня. Каждый узел может иметь несколько порождённых.

списков.

или более узлов, таких, что
а) имеется один специально обозначенный

узел, называемый корнем данного дерева,
б) остальные узлы (исключая корень) содержатся в m0 попарно непересекающихся множествах Т1, …, Тm, каждое из которых в свою очередь является деревом. Деревья Т1, …, Тm называются поддеревьями данного корня.

которое содержится в этом дереве.
Число поддеревьев данного узла называется

степенью этого узла.
Узел с нулевой степенью называется концевым узлом;
Неконцевые узлы часто называют узлами разветвления.
Уровень узла по отношению к дереву Т определяется следующим образом: говорят, что корень имеет уровень 1, а другие узлы имеют уровень на 1 выше их уровня относительно содержащего их поддерева Тj этого корня.

списка, в котором каждый указатель соответствует дуге. Это представление называется

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

списков.

состоящее из некоторого (быть может равного нулю) числа непересекающихся деревьев.

пустым или состоит из корня и двух непересекающихся бинарных деревьев,

называемых левым и правым поддеревьями данного корня.

встречается понятие обход дерева.

Для обхода бинарных деревьев можно применить
один из

трех принципиально разных способов:
в прямом порядке
в центрированном порядке
в обратном порядке

поддерево
Центрированный порядок обхода:
Пройти левое поддерево
Попасть в корень
Пройти правое поддерево
Обратный порядок

обхода:
Пройти левое поддерево
Пройти правое поддерево
Попасть в корень

связи с родителями, такие связи назвали нитями.

Отличие нормальных связей

от нитей: в каждом узле хранят две однобитовые переменные LTag и RTag. Эти переменные равны нулю, если соответствующие связи указывают на поддеревья, и единице, если связи являются нитями.

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

множество линий (называемых ребрами), соединяющих определенные пары вершин. Каждая пара

вершин соединяется не больше чем одним ребром.

Графы:
взвешенные и невзвешенные
ориентированные и неориентированные

не больше чем одним ребром. Дуга, соединенная с вершиной, называется

инцидентной этой вершине. Две вершины называются смежными, если существует ребро, соединяющее их. Две дуги называются смежными, если они инцидентны одной и той же вершине.

и пусть n0; говорят, что «V0, V1, …, Vn» -

путь длины n от V до V`, если V=V0, вершина Vk смежна с Vk+1 при 0kn, а Vn=V`. Путь прост, если вершины V0, V1, …, Vn-1 все различны между собой, а также различны все вершины V1, V2, …, Vn. Граф называется связным, если имеется путь между каждыми двумя вершинами этого графа. Циклом называется простой путь длины не менее 3 от какой-либо вершины до нее самой. Свободное дерево – это связный граф, не имеющий циклов.

вершинами этого графа.
Циклом называется простой путь длины не менее

3 от какой-либо вершины до нее самой. Свободное дерево – это связный граф, не имеющий циклов.
Формально направленный граф определяется как некое множество вершин и множество дуг, причем каждая дуга ведет от некоторой вершины V к некоторой вершине V`. Если e – дуга, идущая от V к V`, то говорят, что V – начальная вершина дуги e, а V` - конечная вершина.

вершин и m дуг, то матрица инциденции А(Г)=[aij]mxn определяется так:

следующим образом:




Во взвешенном графе каждая единица заменяется на вес соответствующего

ребра

промежуточных вершин


Алгоритм просматривает вершины графа в таком порядке:
соединённые

с исходной вершиной
соединённые с уже просмотренными, но ещё не просмотренные.

- временная метка и Previous [i] - метка предыдущей вершины

пути (начальное значение Times[i]=0, Previous [i]=0 для всех i).
Заводятся два списка "фронта волны" NewFront и OldFront, а также переменная Time (текущее время).
OldFront:={ver1}; NewFront:={}; Time:=1.
Для каждой из вершин i, входящих в OldFront, просматриваются соседние вершины j, и если Times [j] = 0, то Times [j]=Time, NewFront := NewFront + {j}; в переменную Previous [j] заносится номер i.
Если NewFront = {}, то путь не существует, переход к шагу 8.
Если одна из веpшин совпадает с ver2, то найден кратчайший путь длины Time, переход к шагу 8.
OldFront:= NewFront; NewFront:={}; Time:=Time+1; возврат к шагу 4.
Восстанавливаем путь, проходя массив P.

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

во взвешенном графе с неотрицательными весами (алгоритм Дейкстры)
    Функция находит путь

минимального веса в графе G=(V,E), заданном весовой матрицей w, у которой элемент wi j равен весу ребра, соединяющего i-ю и j-ю вершины. При этом предполагается, что все элементы wi j неотрицательны. Путь ищется из вершины номер u1 к вершине номер u2. Функция использует алгоритм Дейкстры. Для бесконечности используется число GM, его можно задавать в зависимости от конкретной задачи.

поиск, заключается в следующем:
всем веpшинам пpиписывается вес - вещественное число,

d(i)=GM для всех вершин кроме вершины с номером u1, а d(u1)=0;
всем веpшинам пpиписывается метка m(i)=0;
вершина u1 объявляется текущей - t=u1;
для всех вершин у которых m(i)=0, пересчитываем вес по формуле: d(i):=min{d(i), d(t)+W[t,i]};
среди вершин для которых выполнено m(i)=0, ищем ту, для которой d(i) минимальна, если минимум не найден, т.е. вес всех “непомеченных” вершин равен бесконечности (GM), то путь не существует; ВЫХОД;
иначе найденную вершину c минимальным весом полагаем текущей и помечаем (m(t)=1);
если t = u2, то найден путь веса d(t),ВЫХОД;
переходим на шаг 4.

найти расстояния от 1-й вершины до всех остальных.

вершины, линиями — пути между ними (ребра графа). В кружках

обозначены номера вершин, над ребрами обозначена их «цена» — длина пути. Рядом с каждой вершиной красным обозначена метка — длина кратчайшего пути в эту вершину из вершины 1.

Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет

вершина 1. Её соседями являются вершины 2, 3 и 6.

очереди сосед вершины 1 — вершина 2, потому что длина

пути до неё минимальна. Длина пути в неё через вершину 1 равна кратчайшему расстоянию до вершины 1 + длина ребра, идущего из 1 в 2, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, поэтому новая метка 2-й вершины равна 7.

проделываем с двумя другими соседями 1-й вершины — 3-й и

6-й.

вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается

окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это

вершина 2 с меткой 7.

уменьшить метки соседей выбранной вершины, пытаясь пройти в них через

2-ю. Соседями вершины 2 являются 1, 3, 4.
Первый (по порядку) сосед вершины 2 — вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.
Следующий сосед вершины 2 — вершина 3. Если идти в неё через 2, то длина такого пути будет = 7 + 10 = 17. Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.

сосед вершины 2 — вершина 4. Если идти в неё

через 2-ю, то длина такого пути будет = кратчайшее расстояние до 2 + расстояние между вершинами 2 и 4 = 7 + 15 = 22. Поскольку 22< , устанавливаем метку вершины 4 равной 22.

вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её

как посещенную.

Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим

такие результаты:

Повторяем шаг алгоритма для оставшихся вершин (Это будут по порядку

6, 4 и 5).

Завершение выполнения алгоритма. Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11.

во взвешенном графе с произвольными весами для всех пар вершин

(алгоритм Флойда)      Функция находит пути минимального веса в графе G=(V,E), заданном весовой матрицей w, у которой элемент wi j равен весу ребра, соединяющего i-ю и j-ю вершины. При этом полагаем, что W[i,i]=0 для всех i. Путь ищется для всех пар вершин графа. Для бесконечности используется число GM, его можно задавать в зависимости от конкретной задачи.
Алгоритм Флойда предполагает последовательное преобразование матрицы весов W. В конечном итоге получаем матрицу, элементы d[i,j] которой представляют из себя вес минимального пути соединяющего i и j вершины. 

суммарной длины во взвешенном графе с неотрицательными весами (алгоритм Йена)

    Алгоритм предназначен для нахождения К путей минимальной длины во взвешенном графе между вершинами u1,u2. Ищутся пути, которые не содержат петель.
Работа алгоритма начинается с нахождения кратчайшего пути, для этого будем использовать уже описанный алгоритм Дейкстры. Второй путь ищем, перебирая кратчайшие отклонения от первого, третий - кратчайшие отклонения от второго, и т.д.

P1=(v11,...,v1L[1]). Положить k = 2. Включить P1 в результирующий список.
2.

Положить MinW равным бесконечности. Найти отклонение минимального веса от (k–1)-го кратчайшего пути Pk-1 для всех i=1,2,...,L[k-1], выполняя для каждого i шаги с 3-го по 6-й.
3. Проверить, совпадает ли подпуть, образованный первыми i вершинами пути Pk-1, с подпутем, образованным первыми i вершинами любого из путей j=1,2,...,k–1). Если да, положить W[vk-1i,vji+1] равным бесконечности, в противном случае ничего не изменять (чтобы в дальнейшем исключить получение в результате одних и тех же путей).4. Используя алгоритм нахождения кратчайшего пути, найти пути от vk-1i к u2, исключая из рассмотрения корни (vk-11,...,vk-1i) (чтобы исключить петли), для этого достаточно положить равными бесконечности элементы столбцов и строк матрицы W, соответствующие вершинам, входящим в корень.
5. Построить путь, объединяя корень и найденное кратчайшее ответвление; если его вес меньше MinW, то запомнить его.
6. Восстановить исходную матрицу весов W и возвратиться к шагу 3.
7. Поместить путь минимального веса (MinW), найденный в результате выполнения шагов с 3 по 6, в результирующий список. Если k = K, то алгоритм заканчивает работу, иначе увеличить k на единицу и вернуться к шагу 2.

Перечислите основные алгоритмы поиска путей в графах?

3. Какие основные классами

матриц предствляются графы в памяти компьютера?

Контрольные вопросы