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

Нажмите для полного просмотра!

Кратчайшие пути и остовные деревья в графах, слайд №1

Кратчайшие пути и остовные деревья в графах, слайд №2

Кратчайшие пути и остовные деревья в графах, слайд №3

Кратчайшие пути и остовные деревья в графах, слайд №4

Кратчайшие пути и остовные деревья в графах, слайд №5

Кратчайшие пути и остовные деревья в графах, слайд №6

Кратчайшие пути и остовные деревья в графах, слайд №7

Кратчайшие пути и остовные деревья в графах, слайд №8

Кратчайшие пути и остовные деревья в графах, слайд №9

Кратчайшие пути и остовные деревья в графах, слайд №10

Кратчайшие пути и остовные деревья в графах, слайд №11

Кратчайшие пути и остовные деревья в графах, слайд №12

Кратчайшие пути и остовные деревья в графах, слайд №13

Кратчайшие пути и остовные деревья в графах, слайд №14

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Кратчайшие пути и остовные деревья в графах. Доклад-сообщение содержит 14 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 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);...$

Описание слайда:

Реализация топологической сортировки Сложность: 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 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 q; q.push(s); vector 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 mark(n, false); vector 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 mark(n, false); vector d(n, INF); d[0] = 0; vector 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]); } }