depth first search (DFS)

[Javino89]

Ciao ragazzi. Il mio problema è questo:

Devo creare un metodo che dato il vertice (int) di un grafo, restituisca la somma di tutti
i vertici raggiungibili dal vertice in input. Il grafo è orientato e vorrei utilizzare il DFS ma non
so come fare. Grazie in anticipo.

[Alex'87]

Originariamente inviato da Javino89
Ciao ragazzi. Il mio problema è questo:

Devo creare un metodo che dato il vertice (int) di un grafo, restituisca la somma di tutti
i vertici raggiungibili dal vertice in input. Il grafo è orientato e vorrei utilizzare il DFS ma non
so come fare. Grazie in anticipo.

Per cominciare... sai come funziona la DFS?

[Javino89]

Guarda ho visto tante di quelle implementazioni che ho una certa confusione. La visita
DFS effettua una visita in profondità del grafo. Il primo problema implementativo nasce
dal come rendere un vertice visitato. Potrei semplicemente mettere una variabile d'istanza
di tipo boolean nella classe del vertice inizializzata a false. Questo garantirebbe un'ottima
efficenza. Però ho visto che precisamente il vertice va "colorato" assumendo 3 differenti
colori. bianco --> grigio --> nero.

L'algoritmo DI VISITA GENERICA DFS che ho a disposizione è questo:

rendi visitato il vertice v in input
for all edge uscente (v,w) di v do
if vertice w non è ancora visitato then
chiama ricorsivamente la visita passando w

Ovviamente questo va arricchito per il mio scopo.
Va considerato che dispongo gia di una classe che mi crea il main e va ad effettuare
se questo metodo di cui parliamo funziona.

Edit: Se volessi inserire dei codici con indentazione come devo fare?
Edit: Sto usando la logica della lista delle adiacenze

[Javino89]

Per ora ho scritto questo:

import java.util.*;
class Vertex
{
    private int element;
    private List<Edge> archiEntranti;
    private List<Edge> archiUscenti;
    private boolean explored;
    public Vertex(int e)
    {
        this.element = e;
        this.explored = false;
        this.archiEntranti = new LinkedList<Edge>();
        this.archiUscenti = new LinkedList<Edge>();
    }
    public void setExplored()
    {
        this.explored = true;
    }
    public void setElem(int e)
    {
        this.element = e;
    }
    public boolean isExplored()
    {
        return this.explored == true;
    }
    public int getElem()
    {
        return this.element;
    }
    public List<Edge> getArchiUscenti()
    {
        return this.archiUscenti;
    }
    public List<Edge> getArchiEntranti()
    {
        return this.archiEntranti;
    }
}
class Edge
{
    private Vertex origine;
    private Vertex destinazione;
    private boolean discovery;
    private boolean back;
    private boolean forward;
    private boolean cross;
    public Edge()
    {
        this.discovery = false;
        this.back = false;
        this.forward = false;
        this.cross = false;
    }
    public void setDiscovery()
    {
        this.discovery = true;
    }
    public void setBack()
    {
        this.back = true;
    }
    public void setForward()
    {
        this.forward = true;
    }
    public void setCross()
    {
        this.cross = true;
    }
    public boolean isDiscovery()
    {
        return this.discovery == true;
    }
    public boolean isBack()
    {
        return this.back == true;
    }
    public boolean isForward()
    {
        return this.forward == true;
    }
    public boolean isCross()
    {
        return this.cross == true;
    }
    public Vertex getOrigine()
    {
        return this.origine;
    }
    public Vertex getDestinazione()
    {
        return this.destinazione;
    }
    public void setOrigine(Vertex v)
    {
        this.origine = v;
    }
    public void setDestinazione(Vertex v)
    {
        this.destinazione = v;
    }
}
public class SccGraphSolver extends SccGraph
{
    private List<Edge> listaArchi;
    private List<Vertex> listaVertici;

    public SccGraphSolver()
    {
        this.listaArchi = new LinkedList<Edge>();
        this.listaVertici = new ArrayList<Vertex>();
    }
    public void aggiungiArcoOrientato(int verticeSorgente, int verticeDestinazione)
    {
        for(int i=0; i<this.listaArchi.size(); i++)
        {
            Edge curr = listaArchi.get(i);
            if((curr.getOrigine().getElem()==verticeSorgente) && (curr.getDestinazione().getElem()==verticeDestinazione))
            {
                return;
            }
        }
        Edge nuovo = new Edge();
        Vertex origine = new Vertex(verticeSorgente);
        Vertex destinazione = new Vertex(verticeDestinazione);
        nuovo.setOrigine(origine);
        nuovo.setDestinazione(destinazione);
        this.listaArchi.add(nuovo);
    }
    public void aggiungiVertice(int vertice)
    {
        for(int i=0; i<this.listaVertici.size(); i++)
        {
            Vertex curr = listaVertici.get(i);
            if(curr.getElem()==vertice)
            {
                return;
            }
        }
        Vertex nuovo = new Vertex(vertice);
        this.listaVertici.add(nuovo);
    }
    public Set<Integer> calcolaComponenteFortementeConnessa(int vertice)
    {
        return null;
    }
    public int calcolaSommaRaggiungibilita(int vertice)
    {
        int ris = 0;
        Vertex input = find(vertice);
        ris = calcolaSommaRaggiungibilita(ris,input);
        return ris;
    }
    private int calcolaSommaRaggiungibilita(int ris, Vertex input)
    {
        ris += input.getElem();
        input.setExplored();
        for(Edge x : input.getArchiUscenti())
        {
            Vertex w = x.getDestinazione();
            if(!w.isExplored())
            {
                ris += calcolaSommaRaggiungibilita(ris,w);
            }
        }
        return ris;
    }
    private Vertex find(int vertice)
    {
        for(int i=0; i<this.listaVertici.size(); i++)
        {
            Vertex curr = listaVertici.get(i);
            if(curr.getElem()==vertice)
            {
                return curr;
            }
        }
        return null;
    }
}