Necesidad algoritmo para el cálculo de Secuencia

Question

Estoy tratando de encontrar la solución para un problema en el que tengo algo así como

1. A> B
2. B> C
3. B> D
4. C> D

Y debería obtener la respuesta que A> B> C> D

Las condiciones para este problema

1. La salida incluirá todos los elementos.
2. El problema no tendrá ningún entradas falsas. por ejemplo, (A> B) (C> D) es una entrada falsa, ya que no podemos determinar la salida.
3. Las entradas pueden ser de cualquier tamaño, pero nunca falso y siempre habrá una solución al problema.

Tengo que encontrar una solución para esto utilizando de manera óptima las colecciones de Java. Algún consejo / sugerencias son bienvenidos.

Gracias de antemano!

Answer 1

Se llama una ordenación topológica. http://en.wikipedia.org/wiki/Topological_sorting

Teniendo en cuenta que, usted debería ser capaz de completar su tarea por su cuenta.

Answer 2

Te apuesto gráficos recientemente cubiertos en esta clase ...
¿Cómo cree que una gráfica se podría aplicar aquí?
¿Puede pensar en una estructura que se podría construir sobre la base de las entradas problemáticas (A> B>, A> D, C> A, etc.)? Tal vez algún tipo de gráfico dirigido ...

Una vez que el problema se expresa en un gráfico de este tipo, la solución implicaría la navegación de este gráfico ...

Answer 3

empezar a ponerlos en un List. La lista se ordenará, por lo que para el n par (a, b)th, miras hacia arriba a, utilizando una búsqueda binaria. Si ya existe omitir, si no se inserta en al punto apropiado. Desde a > b, lo hace de nuevo con b en la parte restante de la lista. Espero que esta ayuda.

Answer 4

Puede hacer esto con un mapa de las entradas y un método recursivo que añade que de respuesta a una lista devuelta (o simplemente imprime cada nodo a medida que desciende el árbol.) Si va a devolver la respuesta, entonces pre -pendiente de la lista devuelta evitará que la respuesta sea revertido D-> C-> B-> a cuando se completa (o simplemente puede .reverse () la lista al final.) no se olvide de probar para una condición de descanso cuando recursivamente. (Pista: clave no encontrada)