Algoritmos en pocas palabras, 2ª edición

Capítulo 6. Algoritmos de grafos

Este trabajo se ha traducido utilizando IA. Agradecemos tus opiniones y comentarios: [e-mail]

Los grafos son estructuras fundamentales que representan información estructurada compleja. Las imágenes de la Figura 6-1 son todos ejemplos de grafos.

En este capítulo, investigamos formas habituales de representar grafos y algoritmos asociados que se dan con frecuencia. Intrínsecamente, un grafo contiene un conjunto de elementos, conocidos como vértices, y relaciones entre pares de estos elementos, conocidas como perímetros. En este capítulo utilizamos estos términos de forma coherente; otras descripciones podrían utilizar los términos "nodo" y "enlace" para representar la misma información. Sólo consideramos grafos sencillos que evitan (a) las aristas propias de un vértice hacia sí mismo, y (b) los perímetros múltiples entre el mismo par de vértices.

Dada la estructura definida por las aristas de un grafo, muchos problemas pueden plantearse en términos de caminos desde un vértice de origen a un vértice de destino en el grafo, construidos utilizando las aristas existentes en el grafo. A veces, una arista tiene asociado un valor numérico conocido como su peso; a veces, una arista está dirigida con una orientación específica (como una calle de sentido único). En el algoritmo del camino más corto de una sola arista, se da un vértice concreto, s, y se le pide que calcule el camino más corto (mediante la suma de los pesos de las aristas) ...