1 respuesta
·
Un árbol generador de un grafo es un subgrafo que tiene todos los vértices.
El algoritmo de búaqueda en profundidad consiste en recorrer el grafo empezando por un vértice y en cada paso se va a un vértice adyacente y se van marcando los vértices ya visitados para no volver a ninguno de ellos. Si se llega a un punto donde ya no se puede ir a otro no visitado y no hemos recorrido todo el árbol se retroceden los pasos que haga falta y se vuelve a intentar.
Naturalmente hay que mirar el grafo porque si lo haces al azar te puedes meter en un lío.
Viendo que el 8 solo tiene una arista debe ser el principio o el final del árbol. Asimismo durante el proceso si dejamos tres vértices no visitados con una sola llegada será imposible completarlo.
Bueno, y no cuesta mucho ver los posibles árboles generadores
8 6 5 7 1 3 2 4
8 6 5 7 1 2 4 3
8 6 5 7 2 1 3 4
8 6 5 7 2 4 3 1
8 6 5 3 4 2 1 7
8 6 5 3 4 2 7 1
8 6 5 3 1 7 2 4
8 6 5 7 1 2 3 4
8 6 5 7 1 3 4 2
Etc.
Salen demasiados.
Y eso es todo.
