Алгоритм Прима: различия между версиями
(Новая страница: «===Задача=== Дан неориентированный взвешенный граф $G=(V, E)$. Остовным деревом в $G$ называетс...») |
|||
Строка 77: | Строка 77: | ||
Как и в [[Алгоритм Дейкстры#Как брать минимальную вершину?| алгоритме Дейкстры]] с кучей сложность алгоритма будет $O(\underbrace{ElogV}_\text{суммарно на всех шагах мы прорелаксируем все рёбра} + \underbrace{VlogV}_\text{на каждой итерации мы извлекаем вершину из set'а}) = O((V+E)logV)$ | Как и в [[Алгоритм Дейкстры#Как брать минимальную вершину?| алгоритме Дейкстры]] с кучей сложность алгоритма будет $O(\underbrace{ElogV}_\text{суммарно на всех шагах мы прорелаксируем все рёбра} + \underbrace{VlogV}_\text{на каждой итерации мы извлекаем вершину из set'а}) = O((V+E)logV)$ | ||
+ | ===Без $set$'а=== | ||
+ | |||
+ | Как и в [[Алгоритм Дейкстры#Как брать минимальную вершину?| алгоритме Дейкстры]], мы можем написать решение, которое будет выбирать очередную вершину не вытаскивая из $set'$а, а каждый раз просматривая все вершины заново. Асимптотика такого решения будет $O(\underbrace{V^2}_\text{на каждой из V итераций рассматриваем все вершины} + \underbrace{E}_\text{суммарно на всех шагах мы рассмотрим каждое ребро по 2 раза})$ | ||
+ | |||
+ | |||
+ | <syntaxhighlight lang="C++"> | ||
+ | typedef int Vertex; | ||
+ | |||
+ | struct Edge { | ||
+ | Vertex from, to; | ||
+ | int w; | ||
+ | |||
+ | Edge(Vertex from, Vertex to, int w) { | ||
+ | this->from = from; | ||
+ | this->to = to; | ||
+ | this->w = w; | ||
+ | } | ||
+ | |||
+ | static NoEdge() { | ||
+ | return Edge(-1, -1, -1); | ||
+ | } | ||
+ | }; | ||
+ | |||
+ | vector<Edge> MstPrimAlgorithm(vector<vector<Edge> >& adjacent) { | ||
+ | int n = adjacent.size(); | ||
+ | int start_v = 0; /* начнём строить дерево с 0 вершины */ | ||
+ | |||
+ | vector<bool> is_visited(n, false); | ||
+ | is_visited[start] = true; | ||
+ | |||
+ | vector<Edge> incoming_edge(n, Edge::NoEdge()); | ||
+ | |||
+ | vector<Edge> mst; | ||
+ | for (int i = 0; i < n; ++i) { | ||
+ | int min_edge_w = INF; | ||
+ | int safe_edge_end = -1; | ||
+ | |||
+ | for (int v = 0; v < n; ++v) { | ||
+ | if (is_visited[v]) { | ||
+ | continue; | ||
+ | } | ||
+ | |||
+ | // TODO | ||
+ | |||
+ | } | ||
+ | |||
+ | |||
+ | if (safe_edge_end != start_v) { | ||
+ | mst.push_back(incoming_edge[safe_edge_end]); | ||
+ | } | ||
+ | |||
+ | for (int i = 0; i < adjacent[safe_edge_end].size(); ++i) { | ||
+ | Edge cur_e = adjacent[safe_edge_end][i]; | ||
+ | Vertex to = cur_e.to; | ||
+ | |||
+ | if (incoming_edge[to].w < cur_e.w) { | ||
+ | shortest_edge.erase({incoming_edge[to].w, to}); | ||
+ | incoming_edge[to] = cur_e; | ||
+ | shortest_edge.insert({incoming_edge[to].w, to}); | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | |||
+ | return mst; | ||
+ | } | ||
+ | </syntaxhighlight> | ||
{{Автор|Александр Гришутин|rationalex}} | {{Автор|Александр Гришутин|rationalex}} |
Версия 12:02, 23 ноября 2019
Содержание
Задача
Дан неориентированный взвешенный граф $G=(V, E)$.
Остовным деревом в $G$ называется граф $ST=(V, E')$ такой что $E' \subset E$ и $ST$ является деревом. Говоря простым языком, мы оставляем в графе только некоторые рёбра, чтобы оставшийся граф был деревом (или, ещё говорят, скелетом).
Весом графа мы будем называть суммарный вес всех рёбер, входящих в него.
Наша задача состоит в том, чтобы найти MST $~-$ Minimal Spanning Tree $~-$ остовное дерево минимального веса.
Замечание
В графе может быть много минимальных остовных деревьев. Например, в полном графе на $n$ вершинах, с весами всех рёбер, равных $1$, их $n^{n-2}$.
Как и Алгоритм Краскала, алгоритм Прима основывается на лемме о безопасном ребре.
Алгоритм
Ход алгоритма очень напоминает алгоритм Дейкстры. Мы будем по очереди добавлять вершины в наш мин.остов, на каждом шаге выбирая наилучшую. Единственное отличие от алгоритма Дейкстры состоит в том, что после добавления вершины мы для её соседей будем релаксировать не длину пути, а длину минимального входящего в неё ребра из уже обработанных вершин.
typedef int Vertex;
struct Edge {
Vertex from, to;
int w;
Edge(Vertex from, Vertex to, int w) {
this->from = from;
this->to = to;
this->w = w;
}
static NoEdge() {
return Edge(-1, -1, -1);
}
};
vector<Edge> MstPrimAlgorithm(vector<vector<Edge> >& adjacent) {
int n = adjacent.size();
int start_v = 0; /* начнём строить дерево с 0 вершины */
set<pair<int, Vertex> > shortest_edge;
vector<Edge> incoming_edge(n, Edge::NoEdge());
shortest_edge.insert({0, start_v});
for (Vertex i = 1; i < n); ++i) {
shortest_edge.insert({INF, i));
}
vector<Edge> mst;
while (!shortest_edge.empty()) {
Vertex safe_edge_end = shortest_edge.begin()->second;
shortest_edge.erase(shortest_edge.begin());
if (safe_edge_end != start_v) {
mst.push_back(incoming_edge[safe_edge_end]);
}
for (int i = 0; i < adjacent[safe_edge_end].size(); ++i) {
Edge cur_e = adjacent[safe_edge_end][i];
Vertex to = cur_e.to;
if (incoming_edge[to].w < cur_e.w) {
shortest_edge.erase({incoming_edge[to].w, to});
incoming_edge[to] = cur_e;
shortest_edge.insert({incoming_edge[to].w, to});
}
}
}
return mst;
}
Сложность
Как и в алгоритме Дейкстры с кучей сложность алгоритма будет $O(\underbrace{ElogV}_\text{суммарно на всех шагах мы прорелаксируем все рёбра} + \underbrace{VlogV}_\text{на каждой итерации мы извлекаем вершину из set'а}) = O((V+E)logV)$
Без $set$'а
Как и в алгоритме Дейкстры, мы можем написать решение, которое будет выбирать очередную вершину не вытаскивая из $set'$а, а каждый раз просматривая все вершины заново. Асимптотика такого решения будет $O(\underbrace{V^2}_\text{на каждой из V итераций рассматриваем все вершины} + \underbrace{E}_\text{суммарно на всех шагах мы рассмотрим каждое ребро по 2 раза})$
typedef int Vertex;
struct Edge {
Vertex from, to;
int w;
Edge(Vertex from, Vertex to, int w) {
this->from = from;
this->to = to;
this->w = w;
}
static NoEdge() {
return Edge(-1, -1, -1);
}
};
vector<Edge> MstPrimAlgorithm(vector<vector<Edge> >& adjacent) {
int n = adjacent.size();
int start_v = 0; /* начнём строить дерево с 0 вершины */
vector<bool> is_visited(n, false);
is_visited[start] = true;
vector<Edge> incoming_edge(n, Edge::NoEdge());
vector<Edge> mst;
for (int i = 0; i < n; ++i) {
int min_edge_w = INF;
int safe_edge_end = -1;
for (int v = 0; v < n; ++v) {
if (is_visited[v]) {
continue;
}
// TODO
}
if (safe_edge_end != start_v) {
mst.push_back(incoming_edge[safe_edge_end]);
}
for (int i = 0; i < adjacent[safe_edge_end].size(); ++i) {
Edge cur_e = adjacent[safe_edge_end][i];
Vertex to = cur_e.to;
if (incoming_edge[to].w < cur_e.w) {
shortest_edge.erase({incoming_edge[to].w, to});
incoming_edge[to] = cur_e;
shortest_edge.insert({incoming_edge[to].w, to});
}
}
}
return mst;
}
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex