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à
codice:#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; }
Rispondi quotando