Recorrido de Grafos

 

Igual que los recorridos en árboles, se parte de un nodo dado y sirven para visitar los vértices y los arcos de manera sistemática, existen dos tipos de recorridos:

 a) Búsqueda en amplitud o anchura.

Es equivalente a recorrer un árbol por niveles. Dado un nodo v, se visitan primero todos los nodos  adyacentes a v, luego todos los que están a distancia 2 (y no visitados), a distancia 3, y así sucesivamente hasta recorrer todos los nodos.

 b) Búsqueda en profundidad.

Es equivalente a un recorrido en preorden de un árbol. Se elige un nodo v de partida. Se marca como visitado y se recorren los nodos no visitados adyacentes a v, usando recursivamente la búsqueda primero en profundidad.

* El recorrido puede ser para grafos dirigidos o no dirigidos.

 

Recorrido de Grafos por Anchura y Profundidad.

 

a) Por Anchura:

 

 

b) Por Profundidad:

 

 

Como es un grafo no dirigido, podemos utilizar el principio de Pre-Orden para abarcar el máximo de nodo.

Se visita la raíz, se recorre el subárbol Izquierdo y se recorre el subárbol Derecho.

 

Recorrido por Anchura.

 

 

Recorrido desde Vértice por anchura desde vértice  D ={D, B, C, H, R, A, T }.

 

Recorrido por Profundidad.

 

Grafo Dirigido, por lo tanto necesitamos buscar la ruta que incluya más nodos.

En este tipo de grafos se asume en algunos casos que el recorrido esta sujeto a los supuestos de peso y orden alfabético.

 

 

Recorrido por profundidad desde Vértice D= {D, C, R, H, T, A, B}.