logo
Алгоритмы решения некоторых теоретико-графовых задач

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

Определим расстояние между произвольной вершиной v взвешенного графа G=(V,E) и некоторым его подграфом G'G как минимальный вес ребра, одним из концов которого является v, а другой лежит в G': d(v,G')=min(v,w)E(G),wG'Weight(v,w).

  1. SST'=<граф, состоящий из одной произвольной вершины графа G>;

  2. если |E(SST')|=n-1, то SST=SST'; КОНЕЦ;

  3. среди множества I вершин графа G, не входящих в SST', но инцидентных хотя бы одной вершине из SST' (I={u | uV(G), uSST', (u,v)E(G), vSST'}), найти вершину wI, расстояние которой до SST' минимально: d(w,SST')=minvId(v,SST');

  4. добавить ребро (w,u), на котором достигается минимальное расстояние d(w,SST'), в SST';

  5. перейти на шаг 2.

(без доказательства - можно доказать по аналогии с АК)

~