Презентация Кратчайшие пути и остовные деревья в графах онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Кратчайшие пути и остовные деревья в графах абсолютно бесплатно. Урок-презентация на эту тему содержит всего 14 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:14 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:121.50 kB
- Просмотров:58
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Кратчайшие пути и остовные деревья в графах
Вопросы:
1) Поиск в глубину
2) Топологическая сортировка
3) Поиск в ширину
4) Алгоритм Дейкстры
5) Алгоритм Флойда-Уоршелла
6) Алгоритм Прима
7) Алгоритм Крускала
№2 слайд
Содержание слайда: Поиск в глубину
Суть алгоритма: идем из каждой вершины графа «вглубь» насколько это возможно
Реализация:
void dfs(int u)
{
used[u]=true;
for(v - сосед u)
if(used[v]==false)
dfs(v);
}
Сложность: O(M)
№3 слайд
Содержание слайда: Топологическая сортировка
Перенумеровывание вершин таким образом, чтобы все ребра вели из вершины с меньшим номером в вершину с большим номером.
Условия: граф ориентированный связный(пни разрешаются) и ациклический.
Реализация основана на поиске в глубину и времени выхода из каждой вершины
Запускать необходимо из вершины, из которой достижимы все
Если такая вершина не задана, то добавляем новую вершину и из нее проводим ребра во все остальные
№4 слайд
Содержание слайда: Реализация топологической сортировки
Сложность: O(M)
void topSort()
{
g.resize(n + 1);
for (int i = 0; i < n; ++i)
g[n].push_back(i);
dfs(n);
reverse(order.begin(), order.end());
}
void dfs(int u)
{
used[u] = true;
for (v - сосед u)
if (!used[v])
dfs(v);
order.push_back(u);
}
№5 слайд
Содержание слайда: Обход в ширину
Суть алгоритма: идем «вширь» от каждой вершины насколько это возможно, то есть идем сразу во всех соседей.
void bfs(int s)
{
queue<int> q;
q.push(s);
used[s] = true;
while (!q.empty())
{
int u = q.front();
q.pop();
for (v - сосед u)
if (!used[v])
{
used[v] = true;
q.push(v);
}
}
}
№6 слайд
Содержание слайда: Кратчайший путь в невзвешенном графе
Модифицируем поиск в ширину
void bfs(int s)
{
queue<int> q;
q.push(s);
vector<int> d(n, INF);
d[s] = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
for (v - сосед u)
if (d[v]==INF)
{
d[v] = d[u] + 1;
q.push(v);
}
}
}
№7 слайд
Содержание слайда: Кратчайший путь во взвешенном графе. Алгоритм Дейкстры.
Все вершины делятся на помеченные и непомеченные
Для помеченных вершин известно точное минимальное расстояние от стартовой
Для непомеченных известно расстояние, за которое точно сможем дойти, но, возможно, не минимальное
Изначально все вершины непомечены
На каждом шаге выбираем непомеченную вершину с минимальной гипотезой расстояния, помечаем ее и производим «релаксации»(пытаемся улучшить гипотезу для ее соседей)
Сложность алгоритма: O(N2 + M)
Если использовать set, можно добиться сложности O(NlogN + M)
№8 слайд
Содержание слайда: Реализация алгоритма Дейкстры
void dijkstra(int s)
{
vector<bool> mark(n, false);
vector<int> d(n, INF);
d[s] = 0;
for (int i = 0; i < n; ++i)
{
int u = -1;
for (int j = 0; j < n; ++j)
if (!mark[j] && (u == -1 || d[j] < d[u]))
u = j;
mark[u] = true;
for (v - сосед u)
d[v] = min(d[v], d[u] + weight(uv));
}
}
№9 слайд
Содержание слайда: Алгоритм Флойда-Уоршелла
Находит кратчайшие пути между всеми парами вершин
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (d[i][k] < INF && d[k][j] < INF)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
Сложность: O(N3)
№10 слайд
Содержание слайда: Остовное дерево. Алгоритм Прима
Остов строится последовательным добавлением вершин в одно большое дерево.
На каждом шаге выбирается еще не помеченная вершина с минимальным расстоянием до уже построенного дерева
Выбранная вершина добавляется в остов вместе с минимальным ребром и производятся релаксации для ее соседей
№11 слайд
Содержание слайда: Остовное дерево. Алгоритм Прима
void prima()
{
vector<bool> mark(n, false);
vector<int> d(n, INF);
d[0] = 0;
vector<int> from(n, -1);
for (int i = 0; i < n; ++i)
{
int u = -1;
for (int j = 0; j < n; ++j)
if (!mark[j] && (u == -1 || d[u] > d[j]))
u = j;
mark[u] = true;
if (from[u]!=-1)
//Добавляем ребро uv в ответ
for (v - сосед u)
if (d[v]>w(uv))
{
d[v] = w(uv);
from[v] = u;
}
}
}
№12 слайд
Содержание слайда: Остовное дерево. Алгоритм Крускала
Остов строится из нескольких деревьев, которые постепенно объединяются в одно
Изначально каждая вершина содержится в своем дереве, а точнее каждая вершина — пень
На каждом шаге выбирается минимальное ребро, соединяющее разные деревья
№13 слайд
Содержание слайда: Остовное дерево. Алгоритм Крускала
void kruskal()
{
for (int i = 0; i < n; ++i)
color[i] = i;
sort(g.begin(), g.end());
for (int i = 0; i < m; ++i)
{
int v1 = g[i].second.first;
int v2 = g[i].second.second;
if (color[v1] != color[v2])
unionTrees(color[v1], color[v2]);
}
}
№14 слайд
Содержание слайда: Спасибо за внимание!
Домашнее задание: Тренировка 6 (проводит Peeka)
Скачать все slide презентации Кратчайшие пути и остовные деревья в графах одним архивом:
