Un grafo consta de vértices (o nodos) y aristas. Los vértices son objetos que contienen información y las aristas son conexiones entre vértices. Para representarlos, se suelen utilizar puntos para los vértices y líneas para las conexiones, aunque hay que recordar siempre que la definición de un grafo no depende de su representación.

Un camino entre dos vértices es una lista de vértices en la que dos elementos sucesivos están conectados por una arista del grafo. Así, el camino AJLOE es un camino que comienza en el vértice A y pasa por los vértices J,L y O (en ese orden) y al final va del O al E. El grafo será conexo si existe un camino desde cualquier nodo del grafo hasta cualquier otro. Si no es conexo constará de varias componentes conexas.

Un camino simple es un camino desde un nodo a otro en el que ningún nodo se repite (no se pasa dos veces). Si el camino simple tiene como primer y último elemento al mismo nodo se denomina ciclo. Cuando el grafo no tiene ciclos tenemos un árbol (ver arboles). Varios árboles independientes forman un bosque. Un árbol de expansión de un grafo es una reducción del grafo en el que solo entran a formar parte el número mínimo de aristas que forman un árbol y conectan a todos los nodos.

Representación de grafos

Una característica especial en los grafos es que podemos representarlos utilizando dos estructuras de datos distintas. En los algoritmos que se aplican sobre ellos veremos que adoptarán tiempos distintos dependiendo de la forma de representación elegida. En particular, los tiempos de ejecución variarán en función del número de vértices y el de aristas, por lo que la utilización de una representación u otra dependerá en gran medida de si el grafo es denso o disperso.

Para nombrar los nodos utilizaremos letras mayúsculas, aunque en el código deberemos hacer corresponder cada nodo con un entero entre 1 y V (número de vértices) de cara a la manipulación de los mismos.Exploración de grafos

A la hora de explorar un grafo, nos encontramos con dos métodos distintos. Ambos conducen al mismo destino (la exploración de todos los vértices o hasta que se encuentra uno determinado), si bien el orden en que éstos son "visitados" decide radicalmente el tiempo de ejecución de un algoritmo, como se verá posteriormente.

En primer lugar, una forma sencilla de recorrer los vértices es mediante una función recursiva, lo que se denomina búsqueda en profundidad. La sustitución de la recursión (cuya base es la estructura de datos pila) por una cola nos proporciona el segundo método de búsqueda o recorrido, la búsqueda en amplitud o anchura.

Suponiendo que el orden en que están almacenados los nodos en la estructura de datos correspondiente es A-B-C-D-E-F... (el orden alfabético), tenemos que el orden que seguiría el recorrido en profundidad sería el siguiente:

A-B-E-I-F-C-G-J-K-H-D

En un recorrido en anchura el orden sería, por contra:

A-B-C-D-E-G-H-I-J-K-F

Es decir, en el primer caso se exploran primero los verdes y luego los marrones, pasando primero por los de mayor intensidad de color. En el segundo caso se exploran primero los verdes, después los rojos, los naranjas y, por último, el rosa.