[Risolto] [C] distanza di un nodo in un grafo

[Carlit0sway+]

Salve ragazzi.  :) Ho una domanda. Io ho un grafo (orientato), di interi.
Devo costruire una funzione distanza( x, d ) che stampi tutte le configurazioni y, distanti d dal nodo x.

In pratica ho capito che devo esattamente eseguire d salti.

Ad esempio,con un grafo (semplificato) del tipo:

Codice: Seleziona tutto

1 -> 2 -> 3 <-> 4 -> 5 <- 6

Io avrò queste liste di adiacenza (correggetemi se sbaglio):

Codice: Seleziona tutto

Lista adiacenza di 1 = 2
Lista adiacenza di 2 = 3
Lista adiacenza di 3 = 4
Lista adiacenza di 4 = 3, 5
Lista adiacenza di 5 = /
Lista adiacenza di 6 = 5

Se io eseguo passaggi (1,1) devo in pratica andare a stampare la lista di adiacenza di 1
Se io eseguo passaggi (3,1) devo andare a stampare le liste di adiacenza dei nodi presenti nella lista di adiacenza di 4.

E' corretto?
Mi sono bloccato, non riesco a trovare un algoritmo.
Posso individuare una relazione tra i d introdotti dall'utente, e le distanze che devo esaminare partendo dal nodo x secondo voi?
O è meglio procedere con una visita, magari in ampiezza?

Grazie

[Brig]

prova a guardare i vari algoritmi quali SPT.s, SPT.l, SPT.aciclic, greedy-MST...
il primo dovrebbe essere quello che cerchi, ma non ho capito molto bene cosa cerchi 

[Zoff]

Aldilà di algoritmi consolidati come quelli suggeriti da Brig mi sembra sia piuttosto semplice realizzare la funzione in modo ricorsivo...

In pseudo codice quello che intendo:

Codice: Seleziona tutto

func calcolaDistanza(x,curr,d){
  if(d<0){
    print "Distanza non valida";
    return;
  }
  if(d==0){
    //Stampa
    print x+" --> "+curr+"\n";
    return;
  }
  foreach nodoAdiacente in curr {
    calcolaDistanza(x,nodoAdiacente,d-1);
  }
}

func distanza(x,d){
  calcolaDistanza(x,x,d);
}

[Carlit0sway+]

Grazie 1000  (b2b)