codice:
#ifndef grafo_h
#define grafo_h
#include<iostream>
#include<stdlib.h>
using namespace std;
template<class nodo, class tipoelem>
class grafo
{
public:
grafo();
virtual void creagrafo() = 0;
virtual bool grafovuoto() = 0;
virtual bool esistenodo(nodo &) = 0;
virtual bool esistearco(nodo, nodo) = 0;
virtual void insnodo(nodo &) = 0;
virtual void insarco(nodo &, nodo &) = 0;
virtual void cancnodo(nodo &) = 0;
virtual void cancarco(nodo &, nodo &) = 0;
virtual listap<nodo> adiacenti(nodo &) = 0;
virtual tipoelem legginodo(nodo) = 0;
virtual int leggiarco(nodo, nodo) = 0;
virtual void scrivinodo(nodo &, tipoelem) = 0;
virtual void scriviarco(nodo, nodo, int) = 0;
void test();
void dfs(nodo, listap<nodo> &);
protected:
int numnodi;
};
#endif
template<class nodo, class tipoelem>
grafo<nodo, tipoelem>::grafo()
{
numnodi = 0;
}
template<class nodo, class tipoelem>
void grafo<nodo, tipoelem>::test()
{
cout << "grafovuoto() = " << this->grafovuoto() << "\n\n";
cout << "inserimento di 5 nodi con le seguenti etichette:\n";
cout << "{1, 2, 3, 4, 5, 6,l 7, 8, 9, 10}\n\n";
for(int i = 1; i <= 10; i++)
{
nodo n;
this->insnodo(n);
}
cout << "\n\n";
cout << "controllo sull'esistenza dei nodi 4 e 11:\n";
nodo k;
k.setetichetta(4);
cout << "esistenodo(4) = " << this->esistenodo(k) << "\n";
k.setetichetta(11);
cout << "esistenodo(11) = " << this->esistenodo(k) << "\n\n";
cout << "inserimento dei seguenti due archi: (1, 2) e (1, 3):\n";
nodo j;
k.setetichetta(1);
j.setetichetta(2);
this->insarco(k, j);
j.setetichetta(3);
this->insarco(k, j);
cout << "\n\n";
cout << "controllo sull'esistenza degli archi (1, 3) e (2, 3):\n";
j.setetichetta(3);
cout << "esistearco(1, 3) = " << this->esistearco(k, j) << "\n";
k.setetichetta(2);
j.setetichetta(3);
cout << "esistearco(2, 3) = " << this->esistearco(k, j) << "\n\n";
cout << "cancellazione e verifica dell'esistenza del nodo 5:\n";
k.setetichetta(5);
cout << "esistenodo(5) = " << this->esistenodo(k) << "\n";
cout << "cancellazione...\n";
this->cancnodo(k);
cout << "esistenodo(5) = " << this->esistenodo(k) << "\n\n";
cout << "cancellazione e verifica dell'esistenza dell'arco (1, 3):\n";
k.setetichetta(1);
j.setetichetta(3);
cout << "esistearco(1, 3) = " << this->esistearco(k, j) << "\n";
cout << "cancellazione...\n";
this->cancarco(k, j);
cout << "esistearco(1, 3) = " << this->esistearco(k, j) << "\n\n";
cout << "creazione e stampa della lista degli adiacenti del nodo 1:\n";
k.setetichetta(1);
listap<nodo> L = this->adiacenti(k);
typename listap<nodo>::posizione p = L.primolista();
cout << "Ladiacenti = {";
while(p != L.predlista(L.primolista()))
{
cout << L.leggilista(p).getetichetta() << " ";
p = L.suclista(p);
}
cout << "}\n\n";
cout << "inserimento e visualizzazione dell' etichetta 11 nel nodo con etichetta 1:\n";
this->scrivinodo(k, 11);
cout << "valore del nodo = " << this->legginodo(k) << "\n";
this->scrivinodo(k, 1);
cout << "valore del nodo = " << this->legginodo(k) << "\n\n";
cout << "inserimento e visualizzazione del peso 11 nell'arco (1, 2):\n";
j.setetichetta(2);
esistenodo(j);
this->scriviarco(k, j, 11);
cout << "peso dell'arco (1, 2) = " << this->leggiarco(k, j) << "\n\n";
cout << "connessione del grafo, ai fini delle visite, con i seguenti archi:\n";
cout << "(1, 5), (1, 8), (2, 3), (4, 1), (4, 8), (5, 6), (6, 2), (6, 3), (6, 7),\n";
cout << "(6, 9), (8, 5), (8, 9), (9, 10), (10, 7)\n";
k.setetichetta(1);
this->esistenodo(k);
j.setetichetta(2);
this->esistenodo(j);
this->cancarco(k, j);
k.setetichetta(5);
cout << "\n";
this->insnodo(k);
bool fine = false;
while(!fine)
{
nodo m;
nodo n;
cout << "digitare l'etichetta del primo nodo dell'arco: ";
tipoelem etic;
cin >> etic;
m.setetichetta(etic);
this->esistenodo(m);
cout << "digitare l'etichetta del secondo nodo dell'arco: ";
etic;
cin >> etic;
n.setetichetta(etic);
this->esistenodo(n);
this->insarco(m, n);
cout << "fine (0. no, 1. si)? ";
cin >> fine;
}
}
template<class nodo, class tipoelem>
void grafo<nodo, tipoelem>::dfs(nodo n, listap<nodo> &visitati)
{
listap<nodo> adiacents = this->adiacenti(n);
typename listap<nodo>::posizione padiac = adiacents.primolista();
cout << "\nad(" << n.getetichetta() << ") = {";
while(padiac != adiacents.predlista(adiacents.primolista()))
{
cout << adiacents.leggilista(padiac).getetichetta() << " ";
padiac = adiacents.suclista(padiac);
}
cout << "}\n\n";
system("pause");
padiac = adiacents.primolista();
cout << n.getetichetta() << " ";
visitati.inslista(visitati.predlista(visitati.primolista()), n);
n = adiacents.leggilista(padiac);
this->esistenodo(n);
typename listap<nodo>::posizione pvisit;
while(padiac != adiacents.predlista(adiacents.primolista()))
{
pvisit = visitati.primolista();
bool presente = false;
while(!presente && (pvisit != visitati.predlista(visitati.primolista())))
{
if(n.getetichetta() == visitati.leggilista(pvisit).getetichetta())
presente = true;
else
pvisit = visitati.suclista(pvisit);
}
if(!presente)
dfs(n, visitati);
padiac = adiacents.suclista(padiac);
n = adiacents.leggilista(padiac);
this->esistenodo(n);
}
}
--->continua
Rispondi quotando