algorithm - topological sort c++

Problemas con un algoritmo de dependencia simple.

Question

En mi aplicación web, tenemos muchos campos que resumen otros campos, y esos campos resumen más campos. Sé que este es un grafo acíclico dirigido.

Cuando se carga la página, calculo valores para todos los campos. Lo que realmente estoy tratando de hacer es convertir mi DAG en una lista unidimensional que contendría un orden eficiente para calcular los campos en.

Por ejemplo: A = B + D, D = B + C, B = C + E Orden de cálculo eficiente: E -> C -> B -> D -> A

En este momento, mi algoritmo solo hace inserciones simples en una Lista de forma iterativa, pero me he encontrado con algunas situaciones en las que eso comienza a romperse. Pienso que lo que se necesitaría en su lugar sería trabajar todas las dependencias en una estructura de árbol, y desde allí convertir eso a la forma unidimensional. ¿Existe un algoritmo simple para convertir un árbol de este tipo en un orden eficiente?

Answer 1

¿Buscas ordenamiento topológico ? Esto impone un ordenamiento (una secuencia o lista) en un DAG. Se utiliza, por ejemplo, en hojas de cálculo, para averiguar las dependencias entre las celdas para los cálculos.

Answer 2

Lo que quieres es una búsqueda en profundidad.

function ExamineField(Field F)
{
if (F.already_in_list)
return
foreach C child of F
{
call ExamineField(C)
}
AddToList(F)
}

Luego simplemente llame a ExamineField () en cada campo, a su vez, y la lista se completará en un orden óptimo de acuerdo con sus especificaciones.

Tenga en cuenta que si los campos son cíclicos (es decir, tiene algo como A = B + C, B = A + D), el algoritmo debe modificarse para que no entre en un bucle sin fin.

Para su ejemplo, las llamadas serían:

ExamineField(A)
ExamineField(B)
ExamineField(C)
AddToList(C)
ExamineField(E)
AddToList(E)
AddToList(B)
ExamineField(D)
ExamineField(B)
(already in list, nothing happens)
ExamineField(C)
(already in list, nothing happens)
AddToList(D)
AddToList(A)
ExamineField(B)
(already in list, nothing happens)
ExamineField(C)
(already in list, nothing happens)
ExamineField(D)
(already in list, nothing happens)
ExamineField(E)
(already in list, nothing happens)

Y la lista terminaría C, E, B, D, A.