PDA

Visualizza la versione completa : [C++]Algoritmo di Prim


tonyno92
09-01-2013, 21:59
Raga sono giorni che provo ad implementare l'algoritmo di prim ma non ci riesco
non riesco a capire quando nello pseudo codice indica w(u,v) < key[v] .

se w(u,v) rappresenta il peso dell'arco u --> v e key[v] il peso del vertice non sono la stessa cosa?

raga perfavore sto cercando di capire come funziona illuminatemi con un po di codice c++ please nel fratempo vi posto il mio

ho utilizzato un stl map per memorizzare L'MST

Raga aiutatemi e per un progetto dell'universitÓ




#include <iostream>
#include <list>
#include <cstdio>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <cstdio>
#define INFINITO 100


using namespace std;

class MENU
{
public:
MENU(){scelta =0;}
public:
short scelta;
public:
short show_menu();
short show_option(){return scelta;}
};
short MENU::show_menu()
{
cout<<"\t\t _______________________"<<endl;
cout<<"\t\t | |"<<endl;
cout<<"\t\t | 1) Inserisci Vertici |"<<endl;
cout<<"\t\t | 2) Inserisci Adiacenza|"<<endl;
cout<<"\t\t | 3) Resetta Grafo |"<<endl;
cout<<"\t\t | 4) Stampa Grafo |"<<endl;
cout<<"\t\t | 5) Algorith Of Prim |"<<endl;
cout<<"\t\t | 0) Shut Down |"<<endl;
cout<<"\t\t |_______________________|"<<endl;
cout<<"\n\n Scelta : "; cin>>scelta;
return scelta;
}





//-----------------------------------------------------------
class Vertex
{
public :
Vertex(){peso = 0;key = "";prec="";}
public :
int peso;
string key;
string prec;
//list<NODO>::iterator padre;
public :
void insert_peso();
void insert_prec(string);
void set_prec(string X) {prec = X;}
};
void Vertex::insert_prec(string X)
{
prec = X;
}
void Vertex::insert_peso()
{
cout<<"Peso Del Cammino : "; cin>>peso;
}

bool operator< (const Vertex& structstudent1, const Vertex &structstudent2)
{
return structstudent1.peso > structstudent2.peso;
}
//Overload the > operator.
bool operator> (const Vertex& structstudent1, const Vertex &structstudent2)
{
return structstudent1.peso < structstudent2.peso;
}


//------------------------------------------------------------
class NODO
{

public:
NODO (){}
public:
string key;
int peso;
string prec;
list<Vertex> head_of_adj;
public:
void insert_key();
void set_peso();
void set_prec(string precc);
};

void NODO::set_prec(string X)
{
prec = X;
}
void NODO::insert_key()
{

cout<<"Nome Vertice : "; cin>> key;
}
void NODO::set_peso()
{
peso = INFINITO;
}
bool operator< (const NODO& structstudent1, const NODO &structstudent2)
{
return structstudent1.peso > structstudent2.peso;
}
//Overload the > operator.
bool operator> (const NODO& structstudent1, const NODO &structstudent2)
{
return structstudent1.peso < structstudent2.peso;
}





//------------------------------------------------------------
list<NODO> riempi_lista_of_nodes(list<NODO> head,int vertici)
{
NODO vertex; //Creiamo Il Vertice
for(int i=0;i<vertici;i++)
{
cout<<"Vertice "<<(i+1)<<"\t"; vertex.insert_key();
//cout<<vertex.key;
head.push_back(vertex); //Aggiungiamo il vertice sempre all'ultima posizione
}
return head;
}

bool verifica(string chp,list<NODO> head) //Verifica l'esistenza dei noi da collegare
{
bool q = false;
list<NODO>::iterator cerca; cerca = head.begin();
while(cerca != head.end())
{
if(chp == cerca->key) q = true;
cerca++;
}
return q;
}


list<NODO> riempi_adj(list<NODO> head,short vertex)
{

cout<<"Selezionare Il Nodo Di Partenza ";
string chp; cin>>chp;
if(verifica(chp,head)==true)
{
cout<<"Selezionare Il Nodo Di Destinazione";
string chd; cin>>chd;
if(verifica(chd,head)==true)
{
list<NODO>::iterator cerca; cerca = head.begin();//Mettiamoci Nella Prima Posozione Della Lista di Nodi
while(cerca != head.end() && cerca->key != chp )
{
//cout<<cerca->key;
cerca++;
}//Siamo Nel Nodo in Cui Aggiungere L'adiacenza

Vertex adj; adj.key = chd; //inseriamo la key del nodo di destinazione
adj.insert_peso();
adj.insert_prec(chp); //il nodo di partenza chp corrisponde al vertice da cui parte l'arco chp to chd
cerca->head_of_adj.push_back(adj); //AGGIUNGIAMO ALLA FINE DELLE LISTE DI ADIACENZE LA NOSTRA ADIACENZA
list<Vertex>::iterator it; //Crei un iteratore alla lista di adiacenze per poter accedere alle sue componenti e funzioni
it = cerca->head_of_adj.begin(); //Faccio Puntare L'iteratore Al Primo Nodo Della Lista Delle Adiacenze

while(it != cerca->head_of_adj.end() ) it++; //Scorro la lista delle adiacenze per trovare l'ultima adiacenza inserita
cout<<"Collegamento riuscito Tra i Nodi "<<cerca->key<<" - "<<(--it)->key<<"\n\n"<<endl;
}
else{cout<<"Nodo Di Destinazione Errato...Riavviare La Procedura\n\n"; return head;}
}
else{cout<<"Nodo Di Partenza Errato...Riavviare La Procedura\n\n"; return head;}


return head;
}

void stampa_grafo(list<NODO> head,short vertex)
{
list<NODO>::iterator print_nodes;
list<Vertex>::iterator print_adj;
if(head.begin() != head.end()) //Verifico se Ŕ piena
{
print_nodes = head.begin();
while(print_nodes != head.end())
{
cout<<print_nodes->key<<"->";
//cout<<print_nodes->prec<<"->";
print_adj = print_nodes->head_of_adj.begin(); //Per poter accedere alla lista di adj devo utilizzare l'iteratore della lista dei nodi come se fosse un puntatore alla testa della seconda lista
while(print_adj != print_nodes->head_of_adj.end()) // il quale verra incrementato dal primo while che fa si che mi trovi per ogni nodo della prima lista nella posizione prima della lista delle adiacenze
{
cout<<" "<<print_adj->key<<"-> ";
//cout<<" "<<print_adj->prec<<"-> ";
print_adj++;
}
cout<<endl;
print_nodes++;
}
}else
cout<<"\t\tGrafo Vuoto\n"<<endl;

}

priority_queue<NODO> riempi_coda(list<NODO> head)
{
list<NODO>::iterator list; //creo l'iteratore alla lista
priority_queue<NODO> codap;
list = head.begin(); //iteratore alla lista di vertici "nodi"
list->peso = 0;
list->set_prec("");
codap.push(*list); //Inserimento della radice con peso zero
list++;
while(list != head.end())
{
list->peso = INFINITO;
codap.push(*list); //In questo Caso *list punta al mio vertice
list++;
}
return codap;
}


bool appartiene (list<Vertex>::iterator v,priority_queue<NODO> q)
{
bool appartiene = false;
short cnt = q.size();
while(q.empty()!= true)
{
if(v->key == q.top().key)
appartiene = true;
q.pop();
cnt--;
}
return appartiene;
}

void algorithm_of_prim(list<NODO> head , short vertex)
{
map<NODO,int> MST; //Albero
priority_queue<NODO> codap; //Coda Prioritaria
list<Vertex>::iterator p; //iteratore alle adiacenze
short i=0;
NODO u;
NODO v,radice;
codap = riempi_coda(head); //Inseriamo Tutti i Vertici Nella Coda Con Priorita --- u sono i vertici della cosa
//radice.key = codap.top().key; radice.peso = codap.top().peso; radice.set_prec("");
MST.insert(pair<NODO, int>(radice,0)); //inseriamo la radice nell'MST
cout<<;
while(codap.empty() != true) //Mentre la coda a priorita non e vuota
{
//Estrarre un arco leggere cioe l'adiacenza di peso minimo
u = codap.top(); //Preleviamo il nodo con peso minimo dalla coda
//cout<<u.key;
codap.pop(); //lo elimino dalla cosa
//puntialo al vertice u
//cout<<u.key;
p = u.head_of_adj.begin(); //Posizioniamoci alla prima adiacenza del vertice
Vertex uv = *p;
while(p != u.head_of_adj.end())
{
if(appartiene(p,codap)==true && (uv.peso) < p->peso)
{
//cout<<codap.top().key;
//uv = *p;
p->set_prec(u.key); v.prec = p->prec; v.key = p->key;
p->peso = uv.peso; v.peso = p->peso ;

}//if
p++;

}//while
cout<<"ho inserito nodo "<<v.key<<"\n";
//L'inserimento nell'albero si fa quando abbiamo trovato il vertice adiacente di peso minimo da u;
MST.insert(pair<NODO, int>(v,v.peso));

}//while

map<NODO,int>::iterator print; print = MST.begin();
if(MST.begin()==MST.end()) cout<<"Albero MST Vuoto";
else
while(print != MST.end())
{
cout<<print->first.key<<" "<<print->second<<" -> ";
print++;
}
//cout<<print->key<<" "<<print->peso<<" -> ";
cout<<" [ null ] "<< endl;
// HO MODIFICAO LA STAMPA
}


int main()
{
list<NODO> head_of_nodes;
MENU menu;
short vertex = 0;
do{
switch(menu.show_menu())
{
case 1:
cout<<"Numero Vertici Del Grafo : "; cin>>vertex;
head_of_nodes = riempi_lista_of_nodes(head_of_nodes,vertex);
break;
case 2:
head_of_nodes = riempi_adj(head_of_nodes,vertex);
break;
case 3:
break;
case 4: stampa_grafo(head_of_nodes,vertex);
break;
case 5: algorithm_of_prim(head_of_nodes,vertex);
break;
default :
cout<<"\t\tScelta Errata\n"<<endl;
break;
case 0:
cout<<"Uscita In Corso...";
}
}while(menu.show_option() != 0);
return 0;
}

Loading