lunes, 1 de octubre de 2012

Algoritmo de búsqueda-Profundidad DFS

Esta búsqueda sobre el grafo ,visita los nodos del grafo recursivamente , por lo que se puede realizar mediante un algoritmo recursivo o con ayuda de una pila.Lo más usual es realizarlo de manera recursiva.

Tiene útil aplicación para el estudio de la conectividad de los grafos.

Haremos un breve pseudocódigo:

algoritmo DFS (nodo origen){
 marcamos origen como visitado
para todos los adyacentes de origen y que no hayan sido visitados 
DFS(uno de los nodos que cumple la premisa dispuesta)
}

Recordemos que podemos obtener la adyacencia mediante la matriz de adyacencia...implementada sobre una matriz o sobre una lista de adyacencia