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

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)