• Author / Uploaded
• Ronny Mallma Trujillo

Citation preview

#include #include//para uso de cola #include//para uso de lista #include//para uso de pila using namespace std; class vertice; class arista{ public: arista *sig; vertice *ady; int peso; friend class grafo; }; class vertice{ public: vertice *sig; arista *ady; string nombre; friend class grafo; }; class grafo{ vertice *h; public: void inicializa(); bool vacio(); int tamanio(); vertice *Getvertice(string nombre);//retornar direccion del vertice deseado void insertar_arista(vertice *origen,vertice *destino,int peso); void insertar_vertice(string nombre); void lista_adyacencia(); void anular(); void eliminar_arista(vertice *origen,vertice *destino); void eliminar_vertice(vertice *vert);// void recorrido_anchura(vertice *origen); void recorrido_profundidad(vertice *origen); }; void grafo::inicializa(){ h=NULL; } bool grafo::vacio(){ if(h==NULL) return true; else return false; } int grafo::tamanio(){ int cont=0; vertice *aux; while(aux!=NULL) { cont++; aux=aux->sig; } return cont; }

vertice *grafo::Getvertice(string nombre){ vertice *aux; aux=h; while(aux!=NULL) { if(aux->nombre==nombre) { return aux; } aux=aux->sig; } return NULL;

} void grafo::insertar_vertice(string nombre){ vertice *nuevo=new vertice; nuevo->nombre=nombre; nuevo->ady=NULL; nuevo->sig=NULL; if(vacio()) { h=nuevo; } else { vertice *aux; aux=h; while(aux->sig!=NULL) { aux=aux->sig; } aux->sig=nuevo; } } void grafo::insertar_arista(vertice *origen,vertice *destino,int peso){ arista *nuevo=new arista; nuevo->peso=peso; nuevo->ady=NULL; nuevo->sig=NULL; arista *aux; aux=origen->ady; if(aux==NULL) { origen->ady=nuevo; nuevo->ady=destino; } else { while(aux->sig!=NULL) { aux=aux->sig; } aux->sig=nuevo; nuevo->ady=destino; }

} void grafo::lista_adyacencia(){

vertice *vertAux; arista *arisAux; vertAux=h; while(vertAux!=NULL) { coutnombresig; } vertAux=vertAux->sig; coutady; if(actual==NULL) { coutady!=NULL) { if(actual->ady==destino) { aux=1; anterior->sig=actual->sig; delete(actual); break; } anterior=actual; actual=actual->sig; } if(aux==0) { coutsig; delete(actual); } else { while(actual!=vert) { anterior=actual; actual=actual->sig; } anterior->sig=actual->sig; delete(actual); }

} void grafo::recorrido_anchura(vertice *origen){ int aux,aux2; vertice *actual; queue cola; list lista; list::iterator i; cola.push(origen); while(!cola.empty())//boleano si esta vacio { aux=0; actual=cola.front();//frente de la cola for(i=lista.begin();i!=lista.end();i++) { if(*i==actual) aux=1; } if(aux==1) { coutady); } aux=aux->sig; }

}

} } void grafo::recorrido_profundidad(vertice *origen){ int aux,aux2; vertice *actual; stack pila; list lista; list::iterator i; pila.push(origen); while(!pila.empty()) { aux=0; actual=pila.top(); pila.pop(); for(i=lista.begin();i!=lista.end();i++) { if(*i==actual) { aux=1; } } if (aux==0) { coutady); } aux=aux->sig; } } } } int main() { Grafo G; G.Inicializa(); int opc;

G.InsertaVertice("TIJ"); G.InsertaVertice("MTY"); G.InsertaVertice("MZT"); G.InsertaVertice("BJX"); G.InsertaVertice("GDL"); G.InsertaVertice("SAN"); G.InsertaVertice("TAM"); G.InsertaVertice("MEX"); G.InsertaVertice("CUN"); G.InsertaVertice("MID"); G.InsertaArista(G.GetVertice("TIJ"), G.InsertaArista(G.GetVertice("MZT"), G.InsertaArista(G.GetVertice("MZT"), G.InsertaArista(G.GetVertice("MTY"), G.InsertaArista(G.GetVertice("BJX"), G.InsertaArista(G.GetVertice("BJX"), G.InsertaArista(G.GetVertice("BJX"), G.InsertaArista(G.GetVertice("GDL"), G.InsertaArista(G.GetVertice("GDL"), G.InsertaArista(G.GetVertice("GDL"), G.InsertaArista(G.GetVertice("GDL"), G.InsertaArista(G.GetVertice("SAN"), G.InsertaArista(G.GetVertice("TAM"), G.InsertaArista(G.GetVertice("MEX"), G.InsertaArista(G.GetVertice("MEX"), G.InsertaArista(G.GetVertice("CUN"),

G.GetVertice("MTY"), G.GetVertice("TIJ"), G.GetVertice("BJX"), G.GetVertice("BJX"), G.GetVertice("SAN"), G.GetVertice("TAM"), G.GetVertice("MEX"), G.GetVertice("MZT"), G.GetVertice("MTY"), G.GetVertice("BJX"), G.GetVertice("MEX"), G.GetVertice("MID"), G.GetVertice("MID"), G.GetVertice("MID"), G.GetVertice("CUN"), G.GetVertice("GDL"),

do { system("cls"); cout