Non trovi documentazione a riguardo perché non può esserci una libreria che risponda a tutte le esigenze che si possono presentare, sono praticamente infinite.
Documentazione la trovi per funzioni comuni (come la ricerca), non per casi specifici.

Devi pensare tu ad un algoritmo che ti permetta di farlo e realizzarlo in PHP.

In realtà questa cosa la feci tempo fa in Java per l'università, ma non ricordo assolutamente la soluzione, di sicuro ricordo solo che c'era di mezzo la ricorsione perché era il sistema con minor complessità computazionale e miglior gestione delle risorse.

Se ti va bene fare una cosa molto grossolana, man mano che scandisci l'array ti salvi da qualche parte l'informazione "nodo visitato - genitore".