Programación Específica > Diseño de Algoritmos

 Transformar busqueda en anchura en uno de profundidad

(1/1)

mankalov:
Hola, resulta que tengo el siguiente codigo, que realiza una busqueda en anchura para cualquier arbol ingresado, mi pregunta es ¿Como puedo transformar el programa a uno que realice una busqueda en profundidad?

de antemano muchas gracias.

--- Código: C ---#include <iostream>#include <cstdlib>using namespace std;class nodo {public:    char nombre;    int status;    int grado;    nodo *next;};void muestra_lista(nodo *);nodo *agrega_adyacente(nodo *,char,int);nodo *anchura (char,nodo *); int main() {    int Nnodo,    g=0,i,j,k,z,sum=0,ppeso;    bool c=false;    char Nini;    cout << "Ingrese cantidad de nodos: ";    cin >> Nnodo;    nodo *milista = new nodo[Nnodo];    int *grado = new int[Nnodo];    int **madj = new int*[Nnodo];    for(j=0;j<Nnodo;j++){        madj[j]= new int[Nnodo];    }    for(i=0;i<Nnodo;i++) {        milista[i].nombre = 'A'+i;        milista[i].next = NULL;    }    if(Nnodo!=1) cout << "nSI=1 y NO=0n";    for(i=0;i<Nnodo;i++) {        for (j=0;j<Nnodo;j++) {madj[i][j]=0;}}     for(i=0;i<Nnodo;i++) {        g=0;        for(j=0;j<Nnodo;j++) {            if(i!=j) {               int es_adj;               cout << "nNodo " << char('A'+i) << " adyacente al nodo " << char('A'+j) << " :";               cin >> es_adj;               if(es_adj) {                  madj[i][j]=1;                  if(Nnodo==1) {cout << "Peso del arco (" << i+1 << "," << j+1 <<") : ";                  cin >> ppeso;}                  agrega_adyacente(&milista[i],'A'+j,ppeso);                  g++;                }}}       milista[i].grado=g;       sum=sum+g;    }    cout << "nnNodo | Adyacentes...n";    for(i=0;i<Nnodo;i++) {        cout << char('A'+i) << "    |";        muestra_lista(milista[i].next);        cout << endl;    }    cout << "nBUSQUEDA EN ANCHURAn";    cout<<"Nodo inicial: ";    cin>>Nini;    cout << "nCola: ";    nodo *cola=NULL,*aux;    for(i=0;i<Nnodo;i++) {milista[i].status=1;}    for(i=0;i<Nnodo;i++) {        if(milista[i].nombre==Nini) {           milista[i].status=2;           cola=anchura(milista[i].nombre,cola);        }}    while(cola!=NULL) {   //        for(i=0;i<Nnodo;i++) {            if(milista[i].nombre==cola->nombre) {                milista[i].status=3;                cout<<milista[i].nombre << "   ";                aux=&milista[i];                aux=aux->next;                z=milista[i].grado;            }}        for(i=0;i<z;i++) {   //trabaja con los adyacentes de A            for(j=0;j<Nnodo;j++) {  //revisa los 5 para ver si son adyacentes                 if(aux->nombre==milista[j].nombre) {   //pregunta si B (y luego E) coincide con el puntero aux                    if(milista[j].status==1) {   // pregunta si es estado 1, 2 o 3 para...                       cola=anchura(milista[j].nombre,cola);   //vuelve a cambiar el puntero cola para q apunte a lo q apunta B (y luego E)                       milista[j].status=2;   //...cambiar el estado de 1 a 2                }}}            aux=aux->next;        }        cola=cola->next;    }    cout << endl;    cin.get();    system("pause");    return 0; //}void muestra_lista(nodo *lista) {    while(lista != NULL) {          cout << " -> " << lista->nombre;          lista = lista->next;    }}nodo *agrega_adyacente(nodo *lista,char nombre,int ppeso) {    nodo *aux = lista;    nodo *nuevo = new nodo;    nuevo->nombre = nombre;    nuevo->next = NULL;    if(lista == NULL)  {        lista = nuevo;    } else {        while(aux->next != NULL) {            aux = aux->next;        }        aux->next = nuevo;    }    return lista;}nodo *anchura (char nombre,nodo *lista) {    nodo *aux = lista;    nodo *nuevo = new nodo;    nuevo->nombre = nombre;    nuevo->next = NULL;    if(lista == NULL)  {       lista = nuevo;    } else {        while(aux->next != NULL) {              aux = aux->next;        }        aux->next = nuevo;    }    return lista;}  

Navegación

[0] Índice de Mensajes