Comprensione della soluzione ricorsiva di alcuni algoritmi

1

La maggior parte delle volte abbiamo bisogno di capire il codice di qualcun altro, ad esempio sto studiando algoritmi grafici dalle risorse online di Sedgewick, il particolare esempio di codice è tratto dall'algoritmo di rilevamento del ciclo here :

 private void dfs(Graph G, int u, int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {

            // short circuit if cycle already found
            if (cycle != null) return;

            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(G, v, w);
            }

            // check for cycle (but disregard reverse of edge leading to v)
            else if (w != u) {
                cycle = new Stack<Integer>();
                for (int x = v; x != w; x = edgeTo[x]) {
                    cycle.push(x);
                }
                cycle.push(w);
                cycle.push(v);
            }
        }
    }

Anche se conosco l'essenza di base dell'algoritmo (trovando il bordo posteriore) e posso capire dal codice che sta tentando di archiviare il ciclo generato, ma non sono in grado di tracciare come l'algoritmo verrebbe eseguito e perché l'autore ha preso un parametro aggiuntivo nel codice dfs . In generale, come devo procedere per comprendere tali algoritmi ricorsivi?

    
posta CodeYogi 22.05.2016 - 20:20
fonte

1 risposta

1

Questo algoritmo dfs cerca un ciclo nel grafico G a partire da v. Il "parametro extra" u è il nodo "precedente" o "genitore" di v nell'albero di ricerca, viene passato qui perché consente all'algoritmo di evitare di prendere una sequenza come "u - v - u" per un ciclo.

Capire il codice a volte non è facile, richiede pratica, specialmente il codice ricorsivo. Esistono diverse tecniche, come l'aggiunta di commenti, "refactoring dei graffi", l'esecuzione del codice in un debugger (come suggerito da Robert Harvey), l'aggiunta di istruzioni di registrazione al codice ed eseguirlo, o disegnare un esempio su un pezzo di carta ed eseguire "usando una matita. Solo tu puoi scoprire quale tecnica funziona meglio per te e per il tuo caso specifico.

    
risposta data 22.05.2016 - 23:27
fonte

Leggi altre domande sui tag