Как реализовать алгоритм Прима на графе?

Question

[Mikhail Tchervonnko]

Нужна реализация алгоритма Прима на графе, представленном списком смежности с помощью C++ с STL-овской priority_queue очередью. Собственно, суть вопроса именно в том, как реализовать, просто кусок кода или пошаговый алгоритм без вырвиглазного псевдокода и мат. абстракций. Или другими словами есть граф, реализованный в виде списка смежных вершин. Вопрос: как с помощью очереди с приоритетом из STL (C++) реализовать Алгоритм Прима для поиска минимального остовного дерева (MST)?
Спасибо

Answer 1

[vans239]

По сути:

set {int} used; 
vector {list {Edge}} edges; 
vector {Edge} ans;
pr_queue {Edge} next_edges;
used.add(0);
edges.addAll(edges[0]);
while(!next_edges.empty()){
  Edge edge = next_edges.front();
  next_edges.pop();
  if(!used.contains(edges.to)){
    used.add(edges.to);
    ans.add(edge);
    next_edges.addAll(edges[edges.to]);
  }
}

Для pr_queue добавить компаратор по весу ребра.
Данный алгоритм делает много лишних действий, зато простой

Answer 2

[Nerazumovskiy]

Гляньте еще сюда http://e-maxx.ru/algo/mst_prim. Там приведены очень полезный оптимизации алгоритма, они существенно ускорят тривиальное решение.

Answer 3

[Mikhail Tchervonnko]

vans239: 1
Nerazumovskiy:
Спасибо.