6.3.1.-Algoritmos de recorrido y búsqueda

El camino mas corto
El problema de los caminos más cortos es el problema que consiste
en encontrar un camino entre dos vértices (o nodos) de tal manera
que la suma de los pesos de las aristas que lo constituyen es mínima.
Ahora bien, podemos emplear el algoritmo de Dijkstra para éstos
casos, los pasos o procedimientos a seguir para éste algoritmo son
los siguientes : Teniendo un grafo dirigido ponderado de N nodos no
aislados, sea x el nodo inicial, un vector D de tamaño N guardará al
final del algoritmo las distancias desde x al resto de los nodos.
1. Inicializar todas las distancias en D con un valor infinito
relativo ya que son desconocidas al principio, exceptuando la
de x que se debe colocar en 0 debido a que la distancia de x a x
sería 0.

2. Sea a = x (tomamos a como nodo actual).

3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi

4. Si la distancia desde x hasta va guardada en D es mayor que la distancia desde x hasta a, sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada.

5. Marcamos como completo el nodo a.



6. Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenándolos valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.



6.3.2.- Algoritmos de recorrido y búsqueda A lo ancho


La búsqueda en anchura es otro procedimiento para visitar
sistemáticamente  todos los vértices de un grafo. Es adecuado
especialmente para resolver problemas de optimización, en los que
se deba elegir la mejor solución entre varias posibles. Al igual que
en la búsqueda en profundidad se comienza en un vértice v (la raíz)
que es el primer vértice activo. En el siguiente paso se etiquetan
como visitados todos los vecinos del vértice activo que no han sido
etiquetados. Se continúa etiquetando todos los vecinos de los hijos
de v (que no hayan sido visitados aún). En este proceso nunca se
visita un vértice dos veces por lo que se construye un grafo sin
ciclos, que será un árbol

6.3.3 Algoritmos de recorrido y búsqueda En profundidad



Muchos algoritmos de grafos necesitan visitar de un modo sistemático todos los vértices de un grafo. En la búsqueda en profundidad se avanza de vértice en vértice, marcando cada vértice visitado. La búsqueda siempre avanza hacia un vértice no marcado, internándose “profundamente” en el grafo sin repetir ningún vértice. Cuando se alcanza un vértice cuyos vecinos han sido marcados, se retrocede al anterior vértice visitado y se avanza desde éste. Si dado un grafo simple G, escogemos un vértice v para iniciar la exploración del grafo utilizando la búsqueda en profundidad, el árbol que se construye es un árbol generador de la componente conexa del grafo que contiene a v. 
Sea  G(V, E) un grafo conexo y  v un vértice de  V. El algoritmo de búsqueda en profundidad puede detallarse así:
1.  Se comienza en un vértice  v (vértice activo) y se toma como la raíz del árbol generador T que se construirá. Se marca el vértice v.
2.  Se elige un vértice u, no marcado, entre los vecinos del vértice activo. Si no existe tal vértice, ir a 4.
3.  Se añade la arista (v, u) al árbol T.  Se marca el vértice u y se toma como activo. Ir al paso 2.
4.  Si se han alcanzado todos los vértices de G el algoritmo termina. En caso contrario, se toma  el vértice padre del vértice activo como nuevo vértice activo y se vuelve al paso 2.

La complejidad de este algoritmo es O(max{n, m})