SoloCodigo

Programación Específica => Diseño de Algoritmos => Mensaje iniciado por: mankalov en Viernes 12 de Noviembre de 2010, 20:03

Título: Transformar busqueda en anchura en uno de profundidad
Publicado por: mankalov en Viernes 12 de Noviembre de 2010, 20:03
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
  1. #include <iostream>
  2. #include <cstdlib>
  3. using namespace std;
  4. class nodo {
  5. public:
  6.     char nombre;
  7.     int status;
  8.     int grado;
  9.     nodo *next;
  10. };
  11. void muestra_lista(nodo *);
  12. nodo *agrega_adyacente(nodo *,char,int);
  13. nodo *anchura (char,nodo *);
  14.  
  15. int main() {
  16.     int Nnodo,
  17.     g=0,i,j,k,z,sum=0,ppeso;
  18.     bool c=false;
  19.     char Nini;
  20.     cout << "Ingrese cantidad de nodos: ";
  21.     cin >> Nnodo;
  22.     nodo *milista = new nodo[Nnodo];
  23.     int *grado = new int[Nnodo];
  24.     int **madj = new int*[Nnodo];
  25.     for(j=0;j<Nnodo;j++){
  26.         madj[j]= new int[Nnodo];
  27.     }
  28.     for(i=0;i<Nnodo;i++) {
  29.         milista[i].nombre = 'A'+i;
  30.         milista[i].next = NULL;
  31.     }
  32.     if(Nnodo!=1) cout << "nSI=1 y NO=0n";
  33.     for(i=0;i<Nnodo;i++) {
  34.         for (j=0;j<Nnodo;j++) {madj[i][j]=0;}}
  35.  
  36.     for(i=0;i<Nnodo;i++) {
  37.         g=0;
  38.         for(j=0;j<Nnodo;j++) {
  39.             if(i!=j) {
  40.                int es_adj;
  41.                cout << "nNodo " << char('A'+i) << " adyacente al nodo " << char('A'+j) << " :";
  42.                cin >> es_adj;
  43.                if(es_adj) {
  44.                   madj[i][j]=1;
  45.                   if(Nnodo==1) {cout << "Peso del arco (" << i+1 << "," << j+1 <<") : ";
  46.                   cin >> ppeso;}
  47.                   agrega_adyacente(&milista[i],'A'+j,ppeso);
  48.                   g++;
  49.                 }}}
  50.        milista[i].grado=g;
  51.        sum=sum+g;
  52.     }
  53.     cout << "nnNodo | Adyacentes...n";
  54.     for(i=0;i<Nnodo;i++) {
  55.         cout << char('A'+i) << "    |";
  56.         muestra_lista(milista[i].next);
  57.         cout << endl;
  58.     }
  59.     cout << "nBUSQUEDA EN ANCHURAn";
  60.     cout<<"Nodo inicial: ";
  61.     cin>>Nini;
  62.     cout << "nCola: ";
  63.     nodo *cola=NULL,*aux;
  64.     for(i=0;i<Nnodo;i++) {milista[i].status=1;}
  65.     for(i=0;i<Nnodo;i++) {
  66.         if(milista[i].nombre==Nini) {
  67.            milista[i].status=2;
  68.            cola=anchura(milista[i].nombre,cola);
  69.         }}
  70.     while(cola!=NULL) {   //
  71.         for(i=0;i<Nnodo;i++) {
  72.             if(milista[i].nombre==cola->nombre) {
  73.                 milista[i].status=3;
  74.                 cout<<milista[i].nombre << "   ";
  75.                 aux=&milista[i];
  76.                 aux=aux->next;
  77.                 z=milista[i].grado;
  78.             }}
  79.         for(i=0;i<z;i++) {   //trabaja con los adyacentes de A
  80.             for(j=0;j<Nnodo;j++) {  //revisa los 5 para ver si son adyacentes
  81.                 if(aux->nombre==milista[j].nombre) {   //pregunta si B (y luego E) coincide con el puntero aux
  82.                     if(milista[j].status==1) {   // pregunta si es estado 1, 2 o 3 para...
  83.                        cola=anchura(milista[j].nombre,cola);   //vuelve a cambiar el puntero cola para q apunte a lo q apunta B (y luego E)
  84.                        milista[j].status=2;   //...cambiar el estado de 1 a 2
  85.                 }}}
  86.             aux=aux->next;
  87.         }
  88.         cola=cola->next;
  89.     }
  90.     cout << endl;
  91.     cin.get();
  92.     system("pause");
  93.     return 0; //
  94. }
  95. void muestra_lista(nodo *lista) {
  96.     while(lista != NULL) {
  97.           cout << " -> " << lista->nombre;
  98.           lista = lista->next;
  99.     }}
  100. nodo *agrega_adyacente(nodo *lista,char nombre,int ppeso) {
  101.     nodo *aux = lista;
  102.     nodo *nuevo = new nodo;
  103.     nuevo->nombre = nombre;
  104.     nuevo->next = NULL;
  105.     if(lista == NULL)  {
  106.         lista = nuevo;
  107.     } else {
  108.         while(aux->next != NULL) {
  109.             aux = aux->next;
  110.         }
  111.         aux->next = nuevo;
  112.     }
  113.     return lista;
  114. }
  115. nodo *anchura (char nombre,nodo *lista) {
  116.     nodo *aux = lista;
  117.     nodo *nuevo = new nodo;
  118.     nuevo->nombre = nombre;
  119.     nuevo->next = NULL;
  120.     if(lista == NULL)  {
  121.        lista = nuevo;
  122.     } else {
  123.         while(aux->next != NULL) {
  124.               aux = aux->next;
  125.         }
  126.         aux->next = nuevo;
  127.     }
  128.     return lista;
  129. }
  130.  
  131.