Алгоритм Прима

Задача

Дан неориентированный взвешенный граф $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 вершины */

  vector<bool> visited(n, false);
  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());
    visited[safe_edge_end] = true;

    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 (visited[to]) {
        continue;
      }

      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;
}

Корректность

Пусть в какой-то момент мы хотим добавить ребро $(u, v)$ в $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 InfiniteEdge() {
    return Edge(-1, -1, INF);
  }
};

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::InfiniteEdge());
  incoming_edge[start] = {-1, start, 0};

  vector<Edge> mst;
  for (int i = 0; i < n; ++i) {

    // ================== Выбираем минимальное ребро ============

    Edge safe_edge = Edge::InfiniteEdge();
    for (int v = 0; v < n; ++v) {
      if (is_visited[v]) {
        continue;
      }
      
      if (incoming_edge[v].w < safe_edge.w) {
        safe_edge = incoming_edge[v];
      }      
    }
       

    if (safe_edge.to != start_v) {
      mst.push_back(safe_edge);
    }

    for (int i = 0; i < adjacent[safe_edge.to].size(); ++i) {
      Edge cur_e = adjacent[safe_edge.to][i];
      Vertex to = cur_e.to;

      if (incoming_edge[to].w < cur_e.w) {
        incoming_edge[to] = cur_e;
      }
    }
  }

  return mst;
}

---

Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex