PDA

Visualizza la versione completa : [C++] Visita BFS in grafi con lista


hopeway
22-02-2018, 13:34
Salve, dovrei implementare la visita BFS di un grafo implementato come una lista ma il professore non ha fornito l'implementazione solo della matrice di adiacenza. Infatti ho notato che non esistono funzioni che controllano se esistono degli archi tra i nodi. Qualcuno potrebbe aiutarmi?


#include <iostream>
#include <ctime>
#include <math.h>
#include "List.cpp"
#include "Queue.cpp" //ha i metodi push e pop
using namespace std;


#define W 0
#define G 1
#define B 2
#define inf len+1


template <class H> class LGraph {
private:


// colore, posizione, tempoinizio, fine
int *c, *p, *d, *f;
// lenght, n, m
int len, n, m;
int t;
H **K;
LinkedList<int> **Adj;
int lastBFSSource;


// funziona trova indice
int findIndex(H x) {
for(int i=0; i<n; i++)
if(*K[i] == x) return i;
return -1;
}

public:


void printPath(int x){
if(x==-1) return;
if(p[x]==1) cout << x;
else{
printPath(p[x]);
cout << "->" << x;
}
}


void BFS(int s){
int c[len];
Queue *Q = new Queue(len);
for(int i=0; i<n; i++){
c[i] = W;
p[i] = -1;
d[i] = inf;
}
Q->push(s);
c[s] = G;
d[s] = 0;
while(!Q->isEmpty()){
int x = Q->pop();
for(int i=0; i<n; i++){
if(M[x][i]==1){ //COME FACCIO AD ADATTARE QUESTO CONTROLLO A LIST?
if(c[i]==W){
c[i] = G;
Q->push(i);
p[i] = x;
d[i] = d[x]+1;
}
}
}
c[x] = B;
}
lastBFSSource = s;
for(int i=0; i<n; i++){
cout << "[" << i << "]->";
if(d[i]==inf) cout << "infinito" << endl;
else cout << d[i] << endl;
}
cout << endl;
}


// il costruttore istanzia i vari array in base alla lunghezza
LGraph(int len) {
this->len = len;
n = m = 0; //m il numero di archi !!!!!
K = new H*[len]; //elementi inseriti ??
c = new int[len]; //color
p = new int[len]; //posizione
d = new int[len]; //tempo di inizio
f = new int[len]; //tempo di fine
for(int i=0; i<len; i++) K[i] = NULL;
Adj = new LinkedList<int>*[len];
for(int i=0; i<len; i++)
Adj[i] = new LinkedList<int>();
}


// k l'elemento che stai inserendo adesso
LGraph<H>* addNode(H k) {
if(n==len) return this; //se n uguale alla lunghezza di n non fa niente
if(findIndex(k)>=0) return this; //se il risultato di findIndex >=0 ritorna il v
K[n] = new H(k);
n++;
return this;
}

LGraph<H>* addEdge(H x, H y) { //operazione aggiungi archi
int i = findIndex(x); //trova l'indice di x
int j = findIndex(y); //trova l'indice di y
if(i<0 || j<0) return this; //se i e j sono < 0, cio uno dei due non esiste ritorna
if(!Adj[i]->search(j)) { //tramite la funzione ricerca della ListaLinkata ricerco j, se non c'
Adj[i]->insert(j); //inserisco j nella posizione i (cio, aggiungo al nodo x l'arco y)
m++; //aumento la dimensione di m
}
return this;
}

void print() {
for(int i=0; i<n; i++) {
cout << "(" << i << ", " << *K[i] << ")" << " : ";
Adj[i]->print();
cout << endl;
}
}



};


int main() {
LGraph<int> *A = new LGraph<int>(10);
A->addNode(8)->addNode(11)->addNode(2);


A->addEdge(8,11)->addEdge(11,2);
A->addEdge(8,2);
A->print();
A->printPath(8);


return 0;
}

Loading