¿Cuáles son los problemas más comunes que se pueden resolver con estas dos estructuras de datos?¿Qué problemas pueden resolverse o abordarse más fácilmente usando gráficos y árboles?
Sería bueno para mí tener también recomendaciones sobre libros que:
Lo primero que pienso cuando leo esta pregunta es: ¿qué tipos de cosas usan gráficos/árboles? y luego pienso hacia atrás en cómo podría usarlos.
Por ejemplo, tomar dos usos comunes de un árbol:
el DOM y XML para el caso, se asemejan a las estructuras de árbol.
Tiene sentido, también. Tiene sentido debido a cómo se deben organizar estos datos. Un sistema de archivos, también. En un sistema UNIX, hay un nodo raíz y se bifurca a continuación. Cuando montas un nuevo dispositivo, lo estás conectando al árbol.
También debería preguntarse: ¿los datos caen en este tipo de estructura? Crea estructuras de datos que tengan sentido para el problema y el resto seguirá.
En cuanto a ser más fácil, creo que es relativo. ¿Eres bueno con las funciones recursivas para atravesar un árbol/gráfico? ¿Qué pasa si necesitas equilibrar el árbol?
Piensa en un programa que resuelve un acertijo de búsqueda de palabras. Puede mapear todas las letras de la búsqueda de palabras en un gráfico y verificar los nodos circundantes para ver si esa cadena coincide con alguna de las palabras. ¿Pero no podrías hacer lo mismo con una sola matriz? Todo lo que necesita hacer es mover un índice para revisar las letras a la izquierda y derecha, y por el ancho para verificar las letras arriba y abajo. Resolver este problema con un gráfico no es difícil, pero puede crear mucho trabajo extra y dificultad si no te sientes cómodo con su uso; por supuesto, eso no debería desanimarte, especialmente si estás aprendiendo sobre ellos.
Espero que eso lo ayude a pensar sobre estas estructuras. En cuanto a una recomendación de libro, tendría que ir con Introduction to Algorithms.
Hay un curso para tales cosas en mi universidad: CSE 326. No pensé que el libro fuera demasiado útil, pero los proyectos son divertidos y te enseñaron bastante sobre la implementación de algunas de las estructuras más simples.
Como por ejemplo, uno de los problemas más comunes (por número de personas que lo usan) que se resuelve con árboles es el de la entrada de texto del teléfono celular. Puede usar árboles, no necesariamente binarios, para representar el espacio de posibles palabras que pueden salir de una lista dada de números que un usuario introduce rápidamente.
Algorithms for Java: Part 5 de Robert Sedgewick tiene que ver con los algoritmos de gráficos y las estructuras de datos. Este sería un buen primer libro para trabajar si quieres implementar algunos algoritmos de gráficos.
Los gráficos de escena para dibujar gráficos en juegos y aplicaciones multimedia usan mucho árboles y gráficos. Los nodos representan los objetos que se representarán, transformaciones, controles, grupos, ...
Los gráficos de escenas suelen tener múltiples capas y atributos, lo que significa que solo puede dibujar un nodo de un gráfico (atributos) en un orden específico (capas) . Dependiendo del tipo de gráfico de escena que tenga, puede tener dos estructuras paralelas: declaraciones e instanciación. Th
The Algorithm Design Manual contiene algunos casos de estudio interesantes con uso creativo de gráficos. A pesar de su nombre, el libro es muy legible e incluso entretenido a veces.
@DavidJoiner/todo:
Fwiw: Una nueva versión de la Algorithm Design Manual se debe a cabo en cualquier momento.
Todo el curso que el profesor Skiena desarrolló este libro para también está disponible en la web:
http://www.cs.sunysb.edu/~algorith/video-lectures/2007-1.html
diagramas de circuito.
compilación (gráficos dirigidos acíclicos)
Maps. Muy compacto como gráficos.
Problemas de flujo de red.
Decisión árboles de sistemas expertos (sic)
diagramas de espina de pescado para la detección de fallos, mejora a procesos, análisis de seguridad. Para los puntos de bonificación, implemente su código de recuperación de errores como objetos que son el diagrama de espina de pez.
Los árboles se utilizan mucho más en lenguajes de programación funcionales debido a su naturaleza recursiva.
Además, los gráficos y los árboles son una buena manera de modelar muchos problemas de IA.
Casi todos los problemas se pueden reescribir en términos de teoría de grafos. No estoy bromeando, mira cualquier libro sobre problemas completos de NP, hay algunos problemas bastante extravagantes que se convierten en teoría de grafos porque tenemos buenas herramientas para trabajar con gráficos ...
Los juegos a menudo usan gráficos para facilitar el hallazgo caminos en el mundo del juego. La representación gráfica del mundo puede tener algoritmos como la búsqueda de amplitud o A * para encontrar una ruta a través de ella.
También suelen utilizar árboles para representar entidades en el mundo. Si tiene miles de entidades y necesita encontrar una en cierta posición, iterar linealmente en una lista puede ser ineficiente, especialmente si necesita hacerlo a menudo. Por lo tanto, el área se puede subdividir en un árbol para permitir que se busque más rápidamente. Del mismo modo que un espacio lineal se puede buscar de manera eficiente con una búsqueda binaria (y por lo tanto dividido en un árbol binario), el espacio 2D se puede dividir en un espacio quadtree y 3D en un octree.