7.23. Resumen¶

En este capítulo hemos examinado el tipo abstracto de datos Grafo y algunas implementaciones de un grafo. Un grafo nos permite resolver muchos problemas siempre y cuando podamos transformar el problema original en algo que puede ser representado por un grafo. En particular, hemos visto que los grafos son útiles para resolver problemas en las siguientes áreas generales.

Búsqueda en anchura para encontrar la ruta no ponderada más corta.
El algoritmo de Dijkstra para la ruta ponderada más corta.
Búsqueda en profundidad para la exploración de grafos.
Componentes fuertemente conectados para simplificar un grafo.
Ordenamiento topológico para ordenar tareas.
Árboles de expansión de ponderación mínima para radiodifusión de mensajes.