Temas de Python - Algoritmos con Python - Grafos

Un grafo es un objeto combinatorio compuesto por un conjunto de vértices V (también conocidos como nodos) y un conjunto de aristas E. Las aristas corresponden a pares de vértices, que generalmente son distintos, y sin una noción de orden en el sentido donde (u, v) y (v, u) denotan el mismo borde.

A veces, consideramos una variante, el grafo dirigido, donde los bordes tienen una orientación. En este caso, los bordes se conocen generalmente como arcos. El arco (u, v) tiene origen u y destino v. La mayoría de los algoritmos descritos en este texto operan en grafos dirigidos, pero se pueden aplicar a grafos no dirigidos reemplazando cada borde (u, v) por dos arcos (u, v) y (v, u).

Los grafos pueden contener información adicional, como pesos o letras, en forma de etiquetas en los vértices o los bordes.