Презентация Основы программирования. Поиск на графах онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Основы программирования. Поиск на графах абсолютно бесплатно. Урок-презентация на эту тему содержит всего 31 слайд. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Основы программирования. Поиск на графах
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:31 слайд
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:1.85 MB
- Просмотров:50
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№2 слайд
![Обход графа поиск в глубину](/documents_6/229d2617d98610fc48742d2fa99fe500/img1.jpg)
Содержание слайда: Обход графа: поиск в глубину
Поиск в глубину позволяет обойти все вершины графа по одному разу, переходя от вершины к вершине по ребрам.
Поиск в глубину реализуется рекурсивным алгоритмом:
Пусть выбрана некоторая не рассмотренная ранее вершина A
Перебираем все исходящие из A ребра, при этом:
если ребро ведет в не рассмотренную ранее вершину B, то продолжаем поиск рекурсивно от B
после обработки B возвращаемся в A и продолжаем перебирать исходящие из A ребра
если все ребра из A проверены, то либо возвращаемся к вершине, из которой мы пришли в A (если такая есть), либо выбираем любую ранее не проверенную вершину и выполняем алгоритм от нее.
№3 слайд
![Обход графа поиск в глубину](/documents_6/229d2617d98610fc48742d2fa99fe500/img2.jpg)
Содержание слайда: Обход графа: поиск в глубину
Граф связный, если для любой пары вершин существует соединяющий их маршрут, проходящий по ребрам.
Поиск в глубину разбивает множество ребер на 2 подмножества: древесные (от текущей вершины к непроверенной) и обратные (к уже проверенной вершине). Древесные ребра образуют дерево (связный граф без циклов), для которого определен порядок обхода вершин при поиске в глубину.
f a b 5 1 2
c d e 4 3 6
№4 слайд
![Классы MGraph и LGraph Будем](/documents_6/229d2617d98610fc48742d2fa99fe500/img3.jpg)
Содержание слайда: Классы MGraph и LGraph
Будем добавлять методы к классам MGraph (матрица смежности) и LGraph (списки смежных вершин):
class MGraph
{
bool **mat; // матрица смежности
int vernum; // число вершин
…
};
class LGraph
{
List *lst; // списки смежных вершин
int vernum; // число вершин
…
};
№5 слайд
![Методы MGraph для поиска в](/documents_6/229d2617d98610fc48742d2fa99fe500/img4.jpg)
Содержание слайда: Методы MGraph для поиска в глубину
Формируется массив R[0…n-1], где R[i] – номер вершины i в порядке обхода в глубину (от 1).
void MGraph::deep(int cver, int *R, int &cnum)
{
R[cver] = ++cnum;
for (int i = 0; i < vernum; i++)
if (mat[cver][i] && !R[i]) deep(i, R, cnum);
}
int* MGraph::DFS()
{
int i, cnum, *R = new int[vernum];
for (i = 0; i < vernum; i++) R[i] = 0;
for (cnum = i = 0; i < vernum; i++)
if (!R[i]) deep(i, R, cnum);
return R;
}
№6 слайд
![Метод deep для LGraph void](/documents_6/229d2617d98610fc48742d2fa99fe500/img5.jpg)
Содержание слайда: Метод deep для LGraph
void LGraph::deep(int cver, int *R, int &cnum)
{
int *pv;
R[cver] = ++cnum;
for (pv = lst[cver].get_first();
pv != NULL;
pv = lst[cver].get_next())
if (!R[*pv]) deep(*pv, R, cnum);
}
Метод DFS точно такой же, как в классе MGraph.
Трудоемкость алгоритма DFS на списках смежных вершин составляет ).
№7 слайд
![Компоненты связности](/documents_6/229d2617d98610fc48742d2fa99fe500/img6.jpg)
Содержание слайда: Компоненты связности
Компоненты связности неориентированного графа это максимальные (по включению вершин) связные подграфы.
Для выделения компонент связности используем поиск в глубину, внеся следующие изменения:
добавим в класс MGraph целую переменную comptotal, в которой будет вычисляться число компонент
изменим процесс формирования массива R: R[i] будет хранить номер компоненты (от 1), включающую вершину i (R[i]=0, если вершина i еще не просмотрена).
Приводимые далее методы cdeep и get_comp – это модификации методов deep и DFS.
№8 слайд
![Методы MGraph для выделения](/documents_6/229d2617d98610fc48742d2fa99fe500/img7.jpg)
Содержание слайда: Методы MGraph для выделения компонент
void MGraph::сdeep(int cver, int *R)
{
R[cver] = comptotal;
for (int i = 0; i < vernum; i++)
if (mat[cver][i] && !R[i]) cdeep(i, R);
}
int* MGraph::get_comp()
{
int i, *R = new int[vernum];
comptotal = 0;
for (i = 0; i < vernum; i++) R[i] = 0;
for (i = 0; i < vernum; i++)
if (!R[i])
{ comptotal++; cdeep(i, R); }
return R;
}
№9 слайд
![Обход графа поиск в ширину](/documents_6/229d2617d98610fc48742d2fa99fe500/img8.jpg)
Содержание слайда: Обход графа: поиск в ширину
Поиск в ширину обычно используется для проверки, существует ли маршрут из некоторой вершины-источника v в целевую вершину w, проходящий по ребрам графа.
В процессе поиска вершины помещаются в очередь для просмотра. Начальная очередь содержит только v.
Пусть u – текущая извлекаемая из очереди вершина.
Рассмотрим все ребра (u,x), при этом возможны варианты:
x просмотрена или находится в очереди – изменений нет,
x=w – маршрут найден, алгоритм завершается
x добавляется в очередь.
Если w не найдена, то после обработки всех ребер (u,x) из очереди выбирается следующая текущая вершина u, и поиск продолжается.
Если очередь закончилась, то маршрута из v в w нет.
№10 слайд
![Обход графа поиск в ширину](/documents_6/229d2617d98610fc48742d2fa99fe500/img9.jpg)
Содержание слайда: Обход графа: поиск в ширину
При поиске в ширину можно не только определить, существует ли маршрут из v в w, но и вычислить его минимальную длину (минимальное число пройденных ребер). Для этого нужно вычислять уровни просмотренных вершин (массив Lev[0…n-1]):
вершина-источник v имеет уровень 1, начальные значения для остальных вершин Lev[i]=0 (это означает, что вершина i еще не рассмотрена),
если Lev[u]=a, существует ребро (u,x) и Lev[x]=0, то для x устанавливается значение уровня Lev[x]=a+1,
если Lev[w]>0, то существует, по крайней мере, один маршрут, и кратчайший маршрут содержит Lev[w]-1 ребро.
№11 слайд
![Обход графа поиск в ширину](/documents_6/229d2617d98610fc48742d2fa99fe500/img10.jpg)
Содержание слайда: Обход графа: поиск в ширину
Функции для поиска в ширину имеют 1 параметр – номер v (от 0) вершины-источника. Поиск закончится, когда будут просмотрены все вершины, достижимые из v.
Для всех вершин графа будем формировать и возвращать массив уровней вершин Lev.
Если в результате поиска Lev[w]=0 для некоторой вершины w, то w не достижима из v.
Для организации очереди используем класс IQueue (очередь целых чисел) из раздела «Структуры и классы».
№12 слайд
![Метод MGraph для поиска в](/documents_6/229d2617d98610fc48742d2fa99fe500/img11.jpg)
Содержание слайда: Метод MGraph для поиска в ширину
int* MGraph::BFS(int v)
{
int u, x, *Lev = new int[vernum];
IQueue Que(vernum);
for (u = 0; u < vernum; u++) Lev[u] = 0;
Lev[v] = 1; Que.push(v);
for (u = Que.pop(); u >= 0; u = Que.pop())
for (x = 0; x < vernum; x++)
if (mat[u][x] && !Lev[x])
{
Lev[x] = Lev[u] + 1;
Que.push(x);
}
return Lev;
}
№13 слайд
![Метод LGraph для поиска в](/documents_6/229d2617d98610fc48742d2fa99fe500/img12.jpg)
Содержание слайда: Метод LGraph для поиска в ширину
int* LGraph::BFS(int v)
{
int u, *px, *Lev = new int[vernum];
IQueue Que(vernum);
for (u = 0; u < vernum; u++) Lev[u] = 0;
Lev[v] = 1; Que.push(v);
for (u = Que.pop(); u >= 0; u = Que.pop())
for (px = lst[u].get_first();
px != NULL; px = lst[u].get_next())
if (!Lev[*px])
{
Lev[*px] = Lev[u] + 1;
Que.push(*px);
}
return Lev;
}
№14 слайд
![Выделение минимального остова](/documents_6/229d2617d98610fc48742d2fa99fe500/img13.jpg)
Содержание слайда: Выделение минимального остова
Пусть – связный неориентированный граф, содержащий вершин и ребер.
Остов (каркас) – это некоторый связный суграф , не содержащий циклов (дерево).
В общем случае можно выделить множество каркасов (например, если – полный граф, то для него можно определить различных каркасов).
Для любой пары вершин в существует единственный соединяющий их путь.
Добавление к остову любого ребра всегда приводит к образованию цикла.
№15 слайд
![Выделение минимального остова](/documents_6/229d2617d98610fc48742d2fa99fe500/img14.jpg)
Содержание слайда: Выделение минимального остова
Любой остов связного графа содержит ровно ребро.
Доказательство (по мат. индукции):
1. Остов включает 0 ребер при и 1 ребро при .
2. Пусть остов связного графа с вершинами содержит ребро. Если к графу будет добавлена новая вершина , то достаточно включить только одно ребро вида , чтобы полученный граф стал связным. Добавление к графу еще одного ребра (любого) приведет к образованию цикла.
В общем случае, если граф содержит компонент связности, то для него можно выделить каркасов (остовный лес), которые в сумме будут содержать ребер.
№16 слайд
![Выделение минимального остова](/documents_6/229d2617d98610fc48742d2fa99fe500/img15.jpg)
Содержание слайда: Выделение минимального остова
Пусть – взвешенный граф (задана матрица весов ребер , если ). В этом случае можно поставить задачу выделения минимального по весу остова .
Правила выделения ребер минимального остова определяет
Лемма:
Пусть – некоторые подграфы (поддеревья) с попарно непересекающимися множествами вершин .
Тогда ребро с весом принадлежит минимальному остову.
№17 слайд
![Выделение минимального остова](/documents_6/229d2617d98610fc48742d2fa99fe500/img16.jpg)
Содержание слайда: Выделение минимального остова
Доказательство (от противного): пусть и есть такое ребро , что , и .
В минимальном остове есть пути из в и из в . Подграф связан с остальной частью графа ребром . Поэтому при добавлении образуется цикл. Если из этого цикла удалить ребро , то будет получен новый остов, вес которого меньше, чем у - противоречие.
№18 слайд
![Выделение минимального остова](/documents_6/229d2617d98610fc48742d2fa99fe500/img17.jpg)
Содержание слайда: Выделение минимального остова
Пусть в остов добавлено ребро , причем . Тогда деревья и объединятся в одно, т.е. общее число построенных поддеревьев уменьшится на 1.
Процесс построения закончится, когда останется одно дерево, содержащее ребро (или отдельных деревьев, если исходный граф содержит компонент).
В алгоритмах выделения минимального остова в качестве начальных используются поддеревьев, содержащих по 1 вершине (и 0 ребер). Затем производится последовательный выбор минимальных по весу ребер, соединяющих текущие поддеревья, и объединение пар поддеревьев.
№19 слайд
![Алгоритм Прима Данный](/documents_6/229d2617d98610fc48742d2fa99fe500/img18.jpg)
Содержание слайда: Алгоритм Прима
Данный алгоритм выгодно использовать, если граф задан матрицей весов и содержит много ребер. Будем считать, что если в графе отсутствует ребро , то соответствующий элемент матрицы весов .
В алгоритме производится постоянное расширение только одного поддерева (). Вначале содержит только одну вершину, затем к последовательно добавляется по одному ребру и одной вершине, «ближайшей» к текущему поддереву.
Пусть на текущем шаге содержит вершин. Поиск очередного ребра остова с прямым перебором всех ребер потребует сравнений, и
общая трудоемкость алгоритма составит .
№20 слайд
![Алгоритм Прима Для снижения](/documents_6/229d2617d98610fc48742d2fa99fe500/img19.jpg)
Содержание слайда: Алгоритм Прима
Для снижения трудоемкости формируется дополнительный массив длины :
, если вершина уже включена в остов,
, если – ближайшая к уже включенная в остов вершина.
За один просмотр массива ( элементарных шагов) можно выделить очередное ребро минимального остова – это минимальное по весу ребро вида , где .
Пусть это ребро и его вес равен . Тогда если , то ребро действительно содержится в графе и его нужно добавить в остов (вместе с вершиной ).
№21 слайд
![Алгоритм Прима Если , то](/documents_6/229d2617d98610fc48742d2fa99fe500/img20.jpg)
Содержание слайда: Алгоритм Прима
Если , то ребро действительно содержится в графе и его нужно добавить в остов (вместе с вершиной ).
После этого необходимо перестроить массив (за один проход): для каждой пока не включенной в остов вершины проверить, не будет ли ребро легче, чем .
Если , то это означает, что исходный граф несвязный, и было выделено одно из поддеревьев остова (для одной компоненты связности). Построение следующего поддерева можно начинать с любой вершины, входящей в следующую компоненту.
№22 слайд
![Метод WGraph для алгоритма](/documents_6/229d2617d98610fc48742d2fa99fe500/img21.jpg)
Содержание слайда: Метод WGraph для алгоритма Прима
void WGraph::get_span_tree() {
double wmin;
int i, j, vm, *B = new int[vernum];
B[0] = -1;
for (i = 1; i < vernum; i++) B[i] = 0;
for (i = 1; i < vernum; i++) {
wmin = MAX; vm = 0;
for (j = 1; j < vernum; j++)
if (B[j] != -1 && wmin > mat[j][B[j]])
{ vm = j; wmin = mat[j][B[j]]; }
if (!vm) return;
add_edge(vm, B[vm]); B[vm] = -1;
for (j = 1; j < vernum; j++)
if (B[j]!=-1 && mat[j][B[j]]>mat[j][vm])
B[j] = vm;
}
}
№23 слайд
![Алгоритм Крускала Данный](/documents_6/229d2617d98610fc48742d2fa99fe500/img22.jpg)
Содержание слайда: Алгоритм Крускала
Данный алгоритм выгодно использовать, если исходный граф содержит относительно немного ребер, которые лучше задавать массивом троек .
Все ребра сортируются по весу и последовательно проверяются, начиная от самого легкого: если очередное ребро не образует цикла в уже построенной части остова, то оно добавляется в остов, иначе отбрасывается.
Процесс продолжается, пока не будет получено ребро (для связного графа), либо пока не будут просмотрены все ребра (для несвязного).
Сортировка требует элементарных шагов, поэтому если , то для выделения минимальных ребер выгоднее построить бинарную кучу.
№24 слайд
![Алгоритм Крускала Для](/documents_6/229d2617d98610fc48742d2fa99fe500/img23.jpg)
Содержание слайда: Алгоритм Крускала
Для проверки, приводит ли добавление ребра к образованию цикла, формируются (и последовательно объединяются) множества связных вершин: вершины и принадлежат одному множеству, если существует путь из в , состоящий из уже выделенных ребер остова.
: ребро образует цикл в – недопустимое,
: ребро соединяет точки из разных множеств. можно добавить к остову, при этом и объединятся в одно множество.
№25 слайд
![Быстрое объединение множеств](/documents_6/229d2617d98610fc48742d2fa99fe500/img24.jpg)
Содержание слайда: Быстрое объединение множеств
Множества вершин удобно представлять в виде деревьев принадлежности вершин со ссылкой от «сына» к «отцу» и хранить ссылки в целочисленном массиве :
начальные значения (отдельные корни деревьев),
далее только для корней, иначе – это «отец» .
По ссылкам можно пройти от вершины до корня, а корень однозначно определяет множество вершин.
При проверке ребра необходимо:
найти корни множеств, содержащих вершины и ,
если корень() = корень(), то обе вершины принадлежат одному множеству, т.е. ребро образует цикл,
если корень() корень(), то ребро добавляется в остов, а 2 множества объединяются путем формирования в ссылки с одного корня на другой.
№27 слайд
![Быстрое объединение множеств](/documents_6/229d2617d98610fc48742d2fa99fe500/img26.jpg)
Содержание слайда: Быстрое объединение множеств
Чтобы деревья при объединении не вырождались в линейный список, нужно меньшее дерево делать поддеревом большего.
Для этого нужен дополнительный массив весов , в котором каждому корню приписывается либо число вершин, либо высота дерева (эти значения модифицируются при объединении множеств).
При указанных выше условиях дерево высоты будет содержать не менее вершин (по матиндукции):
1. Для выполняется.
2. Пусть объединяются деревья высоты и , с числом вершин и , , и .
Если , то объединенное дерево будет также иметь высоту . Если , то высота нового дерева будет , а число вершин .
№28 слайд
![Быстрое объединение множеств](/documents_6/229d2617d98610fc48742d2fa99fe500/img27.jpg)
Содержание слайда: Быстрое объединение множеств
Если множество содержит вершин, то его корень можно найти не более, чем за шагов.
Трудоемкость выделения всех ребер остова (после сортировки ребер графа) не превышает .
Еще более эффективной будет проверка со сжатием путей, когда при поиске корня ссылки на «отца» заменяются на ссылки прямо на корень множества для всех пройденных вершин. Тогда трудоемкость выделения остова , где – «обратная» к частному случаю функции Аккермана .
(это фактически ).
№29 слайд
![Алгоритм Крускала для массива](/documents_6/229d2617d98610fc48742d2fa99fe500/img28.jpg)
Содержание слайда: Алгоритм Крускала для массива ребер
Алгоритм Крускала приводится в виде отдельной функции span_tree, которая выделяет минимальный остов графа, заданного массивом длины e взвешенных ребер R (число вершин равно n). Остов сохраняется в массиве W длины n-1, который также содержит взвешенные ребра и должен быть выделен заранее. span_tree выделяет остов и возвращает число его ребер (<= n-1).
Взвешенное ребро представляется структурой
struct Edge
{
int a, b; // номера двух вершин ребра
double weight; // вес ребра (для сортировки)
}
Функция sort_edges производит сортировку массива R по возрастанию весов ребер.
№30 слайд
![Алгоритм Крускала для массива](/documents_6/229d2617d98610fc48742d2fa99fe500/img29.jpg)
Содержание слайда: Алгоритм Крускала для массива ребер
int span_tree(Edge *R, int e, int n, Edge *W)
{
int k = 0, ra, rb, i, *A, *B;
A = new int[n]; B = new int [n];
sort_edges(R, e);
for (i=0; i < n; i++) { A[i] = i; B[i] = 1; }
for (i = 0; k < n-1 && i < e; i++) {
for (ra = R[i].a; ra != A[ra]; ra = A[ra]);
for (rb = R[i].b; rb != A[rb]; rb = A[rb]);
if (ra == rb) continue;
W[k++] = R[i];
if (B[ra] >= B[rb])
{ A[rb] = ra; B[ra] += B[rb]; }
else { A[ra] = rb; B[rb] += B[ra]; }
} return k;
}
№31 слайд
![Жадные алгоритмы Алгоритмы](/documents_6/229d2617d98610fc48742d2fa99fe500/img30.jpg)
Содержание слайда: Жадные алгоритмы
Алгоритмы Прима и Крускала – жадные: на каждом их шаге делается локально оптимальный (жадный) выбор, который никогда не отменяется на последующих шагах.
Жадный алгоритм можно использовать, если для задачи выполняются 2 условия:
оптимальное решение задачи содержит в себе оптимальные решения подзадач (свойство оптимальности подзадач);
последовательность локально оптимальных выборов дает глобально оптимальное решение (т.е. жадный выбор на каждом шаге не закрывает путь к оптимальному решению).
Скачать все slide презентации Основы программирования. Поиск на графах одним архивом:
Похожие презентации
-
Основы программирования. Пути на графах
-
Основы программирования. Простые алгоритмы поиска и сортировки
-
Язык программирования Паскаль. Основные понятия
-
Основные конструкции языка программирования. Турбо Паскаль (тестирование). 10 -11 класс
-
Кодирование основных типов алгоритмических структур на языках объектно — ориентированного и процедурного программирования
-
Основные понятия языка программирования. Структура ЯВУ
-
Основы программирование: Введение в Java. Коллекции
-
Обучающая программа «Основы языка программирования Java»
-
Основы программирования - Java ФИСТ 1 курс
-
Основы веб программирования