Dubbio sui Grafi
Ciao a tutti!
Sto studiando per l'esame di informatica e ho un dubbio riguardo ai grafi.
I due algoritmi di visita, in ampiezza (BFS) e in profondità (DFS) permettono di individuare due alberi: albero breadth-first e albero depht-first.
Si può dedurre da uno dei due la distanza di due nodi qualunque sul grafo?
Per me è no! perché solitamente da una visita DFS ottengo un albero degenere e da una visita BFS l'albero che ottengo non sembra darmi informazioni sulle distanze fra nodi generici..
Sto studiando per l'esame di informatica e ho un dubbio riguardo ai grafi.
I due algoritmi di visita, in ampiezza (BFS) e in profondità (DFS) permettono di individuare due alberi: albero breadth-first e albero depht-first.
Si può dedurre da uno dei due la distanza di due nodi qualunque sul grafo?
Per me è no! perché solitamente da una visita DFS ottengo un albero degenere e da una visita BFS l'albero che ottengo non sembra darmi informazioni sulle distanze fra nodi generici..
Risposte
Da questi alberi puoi risalire solo alla distanza con la radice e non tra due nodi generici.
Come pensavo! Grazie mille!! 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo