7.1. Objetivos¶
Aprender qué es un grafo y cómo se utiliza.
Implementar el tipo abstracto de datos grafo utilizando múltiples representaciones internas.
Ver cómo se pueden usar los grafos para resolver una amplia variedad de problemas.
En este capítulo estudiaremos grafos. Los grafos son una estructura más general que los árboles que estudiamos en el último capítulo; de hecho, se puede pensar en un árbol como un tipo especial de grafo. Los grafos se pueden usar para representar muchas cosas interesantes sobre nuestro mundo, incluyendo sistemas de carreteras, vuelos de avión de una ciudad a otra, cómo está conectada la Internet, o incluso la secuencia de clases que deben tomarse para completar una especialidad en ciencias de la computación. Veremos en este capítulo que una vez que tengamos una buena representación para un problema, podemos usar algunos algoritmos estándar de grafos para resolver lo que de otra manera podría parecer un problema muy difícil.
Si bien es relativamente fácil para los seres humanos ver mapa de carreteras y entender las relaciones entre diferentes lugares, una computadora no tiene tal conocimiento. Sin embargo, también podemos pensar en un mapa de carreteras como un grafo. Cuando lo hacemos, podemos hacer que nuestra computadora haga cosas interesantes para nosotros. Si usted alguna vez ha utilizado uno de los sitios de mapas de Internet, sabrá que una computadora puede encontrar el camino más corto, más rápido o más fácil para llegar de un lugar a otro.
Como estudiante de ciencias de la computación, usted puede preguntarse acerca de las asignaturas que debe tomar con el fin de obtener una especialidad. Un grafo es una buena manera de representar los prerrequisitos y otras interdependencias entre las asignaturas. La Figura 1 muestra otro grafo. Éste representa las asignaturas y el orden en que deben ser tomadas para terminar una especialidad en ciencias de la computación en el Luther College.
Figura 1: Prerequisitos para una especialidad en ciencias de la computación¶
Figura 1: Prerequisitos para una especialidad en ciencias de la computación