Опитвам се да внедря MST алгоритъма на Prim в C++, използвайки STL.
Но за следващата програма изглежда, че влиза в безкраен цикъл. И след това излиза с грешка.
Псевдокод за MST алгоритъма на Prim;
Моят код:
#include<algorithm>
#include<vector>
#include<iostream>
#include<queue>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
#define REP(i,a,b) for(int i=int(a);i<b;i++)
#define TRvii(c,it) for(vii::iterator it=(c).begin();it!=(c).end();it++)
#define INF 2000000000
void Prims(int V, int s, vector<vii> &AdjList)
{
vector<int> dist(V,INF);
dist[s] = 0;
priority_queue<ii,vector<ii>,greater<ii> > pq;
pq.push(ii(0,s));
REP(i,1,V) pq.push(ii(i,INF));
bool inPriorityQueue[V];
REP(i,0,V) inPriorityQueue[i] = true;
while(!pq.empty())
{
ii top = pq.top(); pq.pop();
int d = top.first,u = top.second;
inPriorityQueue[u] = false;
TRvii(AdjList[u],it)
{
int v = it->first, weight_u_v = it->second;
if(inPriorityQueue[v] && weight_u_v<dist[v])
{
dist[v] = weight_u_v;
}
}
}
cout << "The shortest distance from " << s << " to all the nodes is" << endl;
REP(i,0,V)
{
cout << i << " : " << dist[i] << endl;
}
}
int main()
{
int v,s,edges;
printf("Enter number of vertices : ");
scanf("%d",&v);
vector<vii> adjList(v+1);
printf("\nEnter source vertex : ");
scanf("%d",&s);
adjList[0].push_back(make_pair(1,4));
adjList[0].push_back(make_pair(7,8));
adjList[1].push_back(make_pair(0,4));
adjList[1].push_back(make_pair(2,8));
adjList[1].push_back(make_pair(7,11));
adjList[7].push_back(make_pair(0,8));
adjList[7].push_back(make_pair(1,11));
adjList[7].push_back(make_pair(8,7));
adjList[7].push_back(make_pair(6,1));
adjList[2].push_back(make_pair(1,8));
adjList[2].push_back(make_pair(3,7));
adjList[2].push_back(make_pair(8,2));
adjList[2].push_back(make_pair(5,4));
adjList[8].push_back(make_pair(2,2));
adjList[8].push_back(make_pair(7,7));
adjList[8].push_back(make_pair(6,6));
adjList[6].push_back(make_pair(7,1));
adjList[6].push_back(make_pair(5,2));
adjList[6].push_back(make_pair(8,2));
adjList[5].push_back(make_pair(6,2));
adjList[5].push_back(make_pair(2,4));
adjList[5].push_back(make_pair(3,14));
adjList[5].push_back(make_pair(4,10));
adjList[4].push_back(make_pair(3,9));
adjList[4].push_back(make_pair(5,10));
adjList[3].push_back(make_pair(2,7));
adjList[3].push_back(make_pair(5,14));
adjList[3].push_back(make_pair(4,9));
Prims(v, s, adjList);
return 0;
}
Графика, върху която е реализиран този алгоритъм:
std::numeric_limits<type>::max
< /a>. - person Some programmer dude   schedule 20.10.2014