Po przetestowaniu na algorytmie Prima działa mi to dobrze nawet na multi grafie także można powiedzieć że nie potrzebuje tego krawedzSortera. Ale mam kolejny problem. Przy robieniu algorytmu Kruskala. Nie wiem za bardzo jak porównywać ze sobą tam odpowiednie wagi. Bo cmp które używam do Prima nie działa mi przy Kruskalu bo sypie błędem. Stworzyłem nowe comp do porówynywania ,ale sypie tym samym błędem. Także proszę o jakąś podpowiedź/pomoc.
I też od razu nie wiem jak odnieść się z main'a do Kruskala. Bo kruskal na wejściu w mainie musi dostać 3 zmienne (które to są w liscie_sasiedztwa czyli a,b,c) ale nie wiem wlasnie tez jak do tego sie odwolac. Oto caly kod:
#include<cstdio>
#include<vector>
#include<set>
#include<time.h>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,rodzic[10000],ranga[10000]; //n-l.wierzcholkow, m-liczba krawedzi
vector< vector< pair<int,int> > > graf;
vector<bool> vis;
vector<int> waga, pi;
void lista_sasiedztwa()
{
int a,b,c;
graf.resize(n);
for (int i=0; i<m; i++)
{
a=rand()%n+1;
b=rand()%n+1;
c=rand()%n/2+1;
a--; b--;
cout<<a<<"--"<<b<<":"<<c<<endl;
graf[a].push_back( make_pair(b,c) );
graf[b].push_back( make_pair(a,c) );
}
cout<<endl;
for(int k=1; k<n; k++) // wypisujemy graf
{
cout << "Sasiedzi wierzcholka " << k << ": ";
sort(graf[k].begin(),graf[k].end());
graf[k].erase (unique(graf[k].begin(), graf[k].end()), graf[k].end());
for( vector <pair <int,int> >::iterator dx = graf[k].begin(); dx != graf[k].end(); dx++ )
{
cout << dx->first << "->" << dx->second << " ," ;
}
cout<<endl;
}
}
struct cmp
{
// czy a jest mniejsze od b
bool operator() (const int &a, const int &b)
{
if (waga[a] < waga[b]) return true;
if (waga[a] > waga[b]) return false;
return a<b;
}
};
struct comp
{
bool operator() (const int &w1, const int &w2)
{
sort(waga.begin(),waga.end());
for(int i=0;i<waga.size();i++)
{
if (waga[i] < waga[i+1])
return true;
if (waga[i] > waga[i+1])
return false;
return waga[i]<waga[i+1];
}
}
};
set<int, cmp> kopiec;
void algorytm_prima(int s)
{
cout<<"--ALGORYTM PRIMA--"<<endl;
int v, u, c;
waga.clear();
waga.resize(n, 10000000);
vis.clear();
vis.resize(n,false);
pi.resize(n);
waga[s] = 0;
pi[s]=s;
kopiec.clear();
for (int i=0; i<n; i++)
kopiec.insert(i);
while( !kopiec.empty() )
{
u = *(kopiec.begin());
kopiec.erase(kopiec.begin());
vis[u]=true;
// a dodał go wierzchołek pi[u]
for (int i=0; i<graf[u].size(); i++)
{
v = graf[u][i].first;
if (!vis[v])
{
c = graf[u][i].second;
if (c < waga[v])
{
kopiec.erase(kopiec.find(v));
waga[v] = c; //
kopiec.insert(v);
pi[v] = u;
}
}
}
}
int suma = 0;
for (int i=1; i<n; i++)
suma += waga[i];
cout<<endl<<"Koszt minimalnego drzewa spinajacego wynosi : "<< suma<<endl;
cout<<"Drzewo zlozone jest z nastepujacych krawedzi:"<<endl;
for (int i=1; i<n; i++)
cout<< i <<"--"<<pi[i]<<":"<<waga[i]<<endl;
}
int znajdz(int x)
{
if(x!=rodzic[x])
{
rodzic[x]=znajdz(rodzic[x]);
}
return rodzic[x];
}
void polacz(int x,int y)
{
int px=znajdz(x),py=znajdz(y);
if(ranga[px]>ranga[py])
{
rodzic[py]=px;
}
else
{
rodzic[px]=py;
}
if(ranga[px]==ranga[py])
{
++ranga[py];
}
}
void algorytm_kruskala(int v1,int v2,int w1)
{
int total=0;
cout<<"--ALGORYTM KRUSKALA--"<<endl;
for(int i=1;i<=n;i++)
{
rodzic[i]=i;
ranga[i]=0;
}
sort(graf.begin(),graf.end(),comp());
for(int i=0;i<m;i++)
{
int s1=znajdz(v1);
int s2=znajdz(v2);
if(s1!=s2)
{
polacz(s1,s2);
total+=w1;
}
}
cout<<"Koszt minimalnego drzewa spinajacego wynosi"<<total<<endl;
}
void main()
{
cout<<"....::::PROGRAM START::::...."<<endl;
srand(time(NULL));
n=5;
m=2*n;
lista_sasiedztwa();
algorytm_prima(0); // zaczynamy algorytm w wierzchołku nr 0
algorytm_kruskala();
cout<<endl<<"....::::PROGRAM KONIEC::::...."<<endl;
system("pause");
}