Gracias L3m0n por la interesante respuesta. La verdad es que a veces me parece que las uniones son las grandes desaprovechadas...están ahí y se usan poco. Me ha gustado mucho el enfoque que le has dado para guardar la lista de funciones a usar.
 
Pero al final he usado el "invento" de los functores.
La verdad es que me proporciona la ventaja del polimorfismo de C++.
Así, por ahora (y espero que me dure) lo he he hecho de ésta forma:   
Código C++:
Ver originaltemplate <typename datonodo_t, typename datoarista_t>
void Grafo<datonodo_t,datoarista_t>::recorrerHijos(const pNodo& padre, Tratar& tratamiento)
{
    if (padre->adyacente!=0)
        {
            pArista A=padre->adyacente;
             while (A->siguiente!=0)
                {
                    tratamiento(A);
                    A=A->siguiente;
                }
            tratamiento(A);
        }
}
  
en lugar del puntero a función le paso un objeto de la clase Tratar 
y luego la clase Tratar es abstracta, y voy definiendo "la perrería" que le quiero hacer en cada clase derivada.    
y de ahí derivo:   
ó   
Y por supuesto, en las funciones miembro de la clase que maneja al grafo, tengo:    
Código C++:
Ver originalTratar* tratamiento= new Buscar (nombreNodo, auxiliar);
  
ó   
Código C++:
Ver originalTratar* tratamiento=new Imprimir (nombreNodo, auxiliar);
  
en cada función miembro. 
Bueno, marco el tema como solucionado y me compro una botella de vino chileno para celebrarlo