Алгоритм Прима (Реализация на C++)

C++   13 декабря 2012  Автор статьи:  

Алгоритм Прима находит минимальное остовное дерево. Идея данного алгоритма заключается в добавление одной за другой вершин в дерево, таким образом, что расстояние от уже помеченных вершин до нее было минимальным. На вход алгоритм принимает n — количество вершин и m — количество ребер, а затем идет m троек, где первое число из какой вершины, второе число в какую, а третье вес ребра. Приведем пример реализации алгоритма Прима:

#include
#include
#include
#define forn(i,n) for(int i=0;i> g[500];//кроме вершин список смежности хранит и вес ребра
vector used(500,0);//вектор использованных вершин
int inf=10000000;
vector d(500,inf);//вектор расстояний
int main()
{
freopen("input.txt","rt",stdin);
freopen("output.txt","wt",stdout);
cin>>n>>m;
int x,y,l;
pair temp;
forn(i,m){
cin>>x>>y>>l;
x--;
y--;
temp.first=y;
temp.second=l;
g[x].push_back(temp);
temp.first=x;
g[y].push_back(temp);
}
vector > path(500);
d[0]=0;
while(true){
int v=-1;
int dist=inf;
forn(u,n)
if(!used[u] && dist>=d[u])
{
v=u;
dist=d[u];
}
if (v==-1) break;
used[v]=true;
forn(u,g[v].size())
if(!used[g[v][u].first]) {
if (d[g[v][u].first]>g[v][u].second) path[g[v][u].first]=make_pair(v,g[v][u].first);
d[g[v][u].first]=min(d[g[v][u].first],g[v][u].second);
}
}
long long sum=0;
forn(i,n) sum+=d[i];
cout<

  • lili

    спасибо огромное .очень помогло

  • worandix

    И от меня большое спасибо!

  • Виталий

    Спасибо!

  • Віталій

    а де і як записувати в той файл значення мас для програми?

Научиться программировать

  • на Delphi

  • на Java

  • на C++