Estoy tratando de buscar una ruta (no tiene que ser la ruta más corta) en un gráfico de 40 x 20. Los puntos de inicio y finalización se eligen al azar. El DFS funciona bien, hasta que llega al borde. Entonces, en cambio ...

-1
Krzysiek Dymanowski 14 mar. 2021 a las 18:51

1 respuesta

La mejor respuesta

Algunas cuestiones:

  1. Pones el caso base de tu recursión en los comentarios, pero es necesario para finalizar la recursividad con un resultado positivo:

    if (startowy == koncowy) {
        cout << koncowy << setw(5) << "target found";
        return true;
    }
    
  2. El resultado de la llamada DFS recursiva se ignora y, en su lugar, se devuelve true incondicionalmente, también cuando el vecino del nodo ya ha sido visitado. Esto sucede porque la instrucción if interna no tiene cuerpo:

    if (!visited[p->numerwierzcholka])
        if(DFS(TablicaList, visited, p->numerwierzcholka, koncowy, MacierzGrafu));
    return true;
    

    El punto y coma en el lado derecho de if está rompiendo el algoritmo. Esto debería ser:

    if (!visited[p->numerwierzcholka] && 
            DFS(TablicaList, visited, p->numerwierzcholka, koncowy, MacierzGrafu))
        return true;
    
  3. El parámetro startowy nunca cambia durante una llamada de DFS, sin embargo, en su código principal parece esperar que la llamada cambie LosowyWierzcholek hasta que finalmente coincida con KoncowyWierzcholek. Esto no es verdad. LosowyWierzcholek no cambiará. Entonces, el ciclo while en su programa principal es un ciclo infinito.

  4. El programa principal no debería necesitar un bucle en absoluto: el recorrido pasa por recursividad, no por iteración. No ayuda repetir la misma búsqueda DFS nuevamente.

    En cambio, su programa principal debería simplemente llamar a DFS y usar el valor de retorno booleano:

    bool result = DFS(TablicaList, visited, LosowyWierzcholek, KoncowyWierzcholek, MacierzGrafu);
    cout << "result: " << result;
    
1
trincot 14 mar. 2021 a las 16:50