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

Июль 30, 2022

Главная
Информатика
Кратчайшие пути и остовные деревья в графах

Содержание

2. Поиск в глубину Суть алгоритма: идем из каждой вершины графа «вглубь» насколько это возможно Реализация: void
3. Топологическая сортировка Перенумеровывание вершин таким образом, чтобы все ребра вели из вершины с меньшим номером в
4. Реализация топологической сортировки Сложность: O(M) void topSort() { g.resize(n + 1); for (int i = 0;
5. Обход в ширину Суть алгоритма: идем «вширь» от каждой вершины насколько это возможно, то есть идем
6. Кратчайший путь в невзвешенном графе Модифицируем поиск в ширину void bfs(int s) { queue q; q.push(s);
7. Кратчайший путь во взвешенном графе. Алгоритм Дейкстры. Все вершины делятся на помеченные и непомеченные Для помеченных
8. Реализация алгоритма Дейкстры void dijkstra(int s) { vector mark(n, false); vector d(n, INF); d[s] = 0;
9. Алгоритм Флойда-Уоршелла Находит кратчайшие пути между всеми парами вершин for (int k = 0; k for
10. Остовное дерево. Алгоритм Прима Остов строится последовательным добавлением вершин в одно большое дерево. На каждом шаге
11. Остовное дерево. Алгоритм Прима void prima() { vector mark(n, false); vector d(n, INF); d[0] = 0;
12. Остовное дерево. Алгоритм Крускала Остов строится из нескольких деревьев, которые постепенно объединяются в одно Изначально каждая
13. Остовное дерево. Алгоритм Крускала void kruskal() { for (int i = 0; i color[i] = i;
15. Скачать презентацию

Слайд 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 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]);
}
}

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

Содержание

Поиск в глубинуСуть алгоритма: идем из каждой вершины графа «вглубь» насколько

Топологическая сортировкаПеренумеровывание вершин таким образом, чтобы все ребра вели из вершины

Реализация топологической сортировки Сложность: O(M)void topSort(){g.resize(n + 1);for (int i = 0;

Обход в ширинуСуть алгоритма: идем «вширь» от каждой вершины насколько это

Кратчайший путь в невзвешенном графеМодифицируем поиск в ширинуvoid bfs(int s){queue

Кратчайший путь во взвешенном графе. Алгоритм Дейкстры.Все вершины делятся на помеченные

Реализация алгоритма Дейкстрыvoid dijkstra(int s){vector mark(n, false);vector d(n, INF);d[s] = 0;for

Алгоритм Флойда-УоршеллаНаходит кратчайшие пути между всеми парами вершинfor (int k =

Остовное дерево. Алгоритм ПримаОстов строится последовательным добавлением вершин в одно большое

Остовное дерево. Алгоритм Примаvoid prima(){vector mark(n, false);vector d(n, INF);d[0] = 0;vector

Остовное дерево. Алгоритм КрускалаОстов строится из нескольких деревьев, которые постепенно объединяются

Остовное дерево. Алгоритм Крускалаvoid kruskal(){for (int i = 0; i <

Похожие презентации