🗊Презентация Кратчайшие пути и остовные деревья в графах

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Кратчайшие пути и остовные деревья в графах, слайд №1Кратчайшие пути и остовные деревья в графах, слайд №2Кратчайшие пути и остовные деревья в графах, слайд №3Кратчайшие пути и остовные деревья в графах, слайд №4Кратчайшие пути и остовные деревья в графах, слайд №5Кратчайшие пути и остовные деревья в графах, слайд №6Кратчайшие пути и остовные деревья в графах, слайд №7Кратчайшие пути и остовные деревья в графах, слайд №8Кратчайшие пути и остовные деревья в графах, слайд №9Кратчайшие пути и остовные деревья в графах, слайд №10Кратчайшие пути и остовные деревья в графах, слайд №11Кратчайшие пути и остовные деревья в графах, слайд №12Кратчайшие пути и остовные деревья в графах, слайд №13Кратчайшие пути и остовные деревья в графах, слайд №14
Скачать
Вы можете ознакомиться и скачать презентацию на тему Кратчайшие пути и остовные деревья в графах. Доклад-сообщение содержит 14 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Кратчайшие пути и остовные деревья в графах Вопросы: 1) Поиск в глубину 2) Топологическая сортировка 3) Поиск в ширину 4) Алгоритм Дейкстры 5) Алгоритм Флойда-Уоршелла 6) Алгоритм Прима 7) Алгоритм Крускала
Описание слайда:
Кратчайшие пути и остовные деревья в графах Вопросы: 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)
Описание слайда:
Поиск в глубину Суть алгоритма: идем из каждой вершины графа «вглубь» насколько это возможно Реализация: 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); }
Описание слайда:
Реализация топологической сортировки Сложность: 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); } } }
Описание слайда:
Обход в ширину Суть алгоритма: идем «вширь» от каждой вершины насколько это возможно, то есть идем сразу во всех соседей. 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); } } }
Описание слайда:
Кратчайший путь в невзвешенном графе Модифицируем поиск в ширину 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)
Описание слайда:
Кратчайший путь во взвешенном графе. Алгоритм Дейкстры. Все вершины делятся на помеченные и непомеченные Для помеченных вершин известно точное минимальное расстояние от стартовой Для непомеченных известно расстояние, за которое точно сможем дойти, но, возможно, не минимальное Изначально все вершины непомечены На каждом шаге выбираем непомеченную вершину с минимальной гипотезой расстояния, помечаем ее и производим «релаксации»(пытаемся улучшить гипотезу для ее соседей) Сложность алгоритма: 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)); } }
Описание слайда:
Реализация алгоритма Дейкстры 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)
Описание слайда:
Алгоритм Флойда-Уоршелла Находит кратчайшие пути между всеми парами вершин 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; } } }
Описание слайда:
Остовное дерево. Алгоритм Прима 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]); } }
Описание слайда:
Остовное дерево. Алгоритм Крускала 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)
Описание слайда:
Спасибо за внимание! Домашнее задание: Тренировка 6 (проводит Peeka)

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию