Trovare in modo efficiente la profondità di un grafico da ogni nodo

Question

Ho un problema dove trovo la profondità minima possibile di un grafico che implica che devo trovare la profondità massima da ciascun nodo e restituire il minimo di tutti. Ovviamente un semplice DFS da ogni nodo farà il trucco, ma quando le cose impazziscono con input estremamente grandi, DFS diventa inefficiente (limite di tempo). Ho provato a mantenere la distanza di ogni foglia sul nodo che si sta esplorando in memoria, ma ciò non ha aiutato molto.

Come trovare in modo efficiente la profondità minima di un grafico molto grande. È degno di nota che il grafico in questione ha nessun ciclo.

Answer 1

Per trovare il grafico centrale/centro di un grafo ad albero non orientato si potrebbe:

1. fare un DFS per trovare un elenco di tutti i nodi foglia O (n)
2. eliminasse tutti questi nodi foglia dal grafico e nota durante l'eliminazione che nuovi nodi diventano nodi foglia
3. Ripetere passaggio 2 finché il grafico viene completamente eliminato

il nodo/nodi cancellate nell'ultima fase dell'algoritmo sarà il grafico centri del tuo albero.

Ogni nodo viene eliminato una volta, quindi l'intero processo può essere eseguito in O (n).

Answer 2

Cosa ti sembra di essere alla ricerca di è il diametro/2. Si potrebbe calcolare il diametro di un albero come qui sotto e chiamare come findDiameter(n, null), per un nodo arbitrario n dell'albero.

public findDiameter(node n, node from) returns <depth, diameter> 

    // apply recursively on all children 
    foreach child in (neighbors(n) minus from) do 
     <de, di> = findDiameter(child, n) 

    // depth of this node is 1 more than max depth of children 
    depth = 1 + max(de) 

    // max diameter either uses this node, then it is 1 + the 2 largest depths 
    // or it does not use this node, then it's the max depth of the neighbors 
    diameter = max(max(di), 1 + max(de) + oneButLargest(de)) 

Tutto quello che dovete fare è nel ciclo sopra i vicini tenere traccia del più grande diametro e le 2 profondità maggiori.