|
Titlul: clasa graf orientat Scris de: Visan Marius Alexandru din Mai 18, 2013, 16:18:17 Salutare ! Sunt nou in domeniul programarii orientate pe obiecte si, totodata, foarte varza...Sunt unele chestii pe care le pricep, iar din altele nu inteleg absolut nimic:|
Am de realizat proiectul urmator, dar nu prea ma pot descurca.... Mai jos , am postat si fisierul header si sursa al clasei(ce am putut realiza pana acum)... Daca cineva m-ar putea ajuta i-as fi recunoscator ! Citat 1.Sa se realizeze o clasa graf orientat ponderat care implementeaza urmatoarele operatii pt un graf orientat reprezentat prin matricea costurilor . Clasa contine : - date membre private : nr de noduri si matricea costurilor - metode publice : constructor implicit, constructor de copiere destructor citire graf din fisierul graf.in (nr. noduri, nr arce,sir de arce si costurile lor) afisare graf : nr. noduri si matricea costurilor afisarea componentelor tare conexe din graf si a numarului de componente tare conexe determinarea drumurilor de cost minim de la un nod x la toate celelalte noduri (alg. Dijkstra) supraincarcarea operatorului < pentru 2 grafuri g1 si g2 , pentru a a verifica daca graful g1 este graf partial al grafului g2 determinarea unui drum de cost minim intre oricare doua noduri distincte din graf(alg. Roy-Floyd) Graf_ponderat.h Citat #include <iostream> #include <fstream> using namespace std; class graf { int n,c[50][50],m; public: graf() { n=0; } graf(graf & a) { n=a.n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) c[j]=a.c[j]; } ~graf() { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) c[j]=0; n=0; } void citire(); void afisare(); friend graf roy_warshall(); friend graf succesor(int x); friend graf dijkstra(); }; Graf_ponderat.cpp Citat #include "graf_ponderat.h" #define inf 50000 int nrs,nrp,nrc,sel[50],comp[50],s[50],p[50],d[50]; void graf::citire() { int i,x,y,j,t,cost; fin>>n>>m>>t; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i!=j) c[j]=inf; for(i=1;i<=n;i++) if(t!=i) d=inf; for(i=1;i<=m;i++) { fin>>x>>y>>cost; c
{ d[y]=cost; p[y]=x; } } } void graf::afisare() { int i,j; fout<<"nr. noduri: "<<n; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) if(c[j]==inf) fout<<"&"<<' '; else fout<<a[j]<<' '; fout<<'\n'; } } void graf::roy_warshall() { int i,j,k; for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(k=1;k<=n;k++) if(a[j]==inf) a[j]=a[k]*a[k][j]; } void graf::succesor(int x) { int i; nrs=0; for(i=1;i<=n;i++) if(i!=x&&a
nrs++; s[nrs]=i; } } void graf::predecesor(int x) { int i; nrc=0; for(i=1;i<=n;i++) if(i!=x&&a
nrp++; p[nrp]=i; } } void graf::componenta(int x) { int i,j,ok; nrc=0; for(i=1;i<=nrs;i++) for(j=1;j<=nrp;j++) if(S==P[j]) { nrc++; sel[S]=1; comp[nrc]=S; } nrc++; comp[nrc]=x; for(i=1;i<=nrc;i++) fout<<comp<<' '; fout<<'\n'; } void graf::determinare() { int x,i,ok; do { ok=0; for(i=1;i<=n;i++) if(sel==0) { sel=1; succesor(i); predecesor(i); componenta(i); ok=1;break; } } while(ok==1); } void graf ::val_min(int &min , int &k) { int i; min=inf; for(i=1;i<=n;i++) if(d<min&&s==0) { min=d; k=i; } } void graf::dijkstra() { int i,ok,min,k,nr=0; s[t]=1; nr=1; do { ok=0; val_min(min,k); if(min!=inf) { s[k]=1; nr++; for(i=1;i<=n;i++) if(s==0) if(d[k]+a[k]<d) { d=d[k]+a[k]; p=k; } ok=1; } if(nr==n) break; } while(ok==1); } |