¿Qué es Depth First Search (DFS)?

Depth First Search (DFS) es un algoritmo para recorrer o buscar elementos en un grafo o árbol. Explora cada rama del grafo lo más profundo posible antes de retroceder y explorar otra rama.

El Código

                
class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }

  depthFirstSearch(start) {
    const result = [];
    const visited = {};
    const adjacencyList = this.adjacencyList;

    (function dfs(vertex) {
      if (!vertex) return null;
      visited[vertex] = true;
      result.push(vertex);
      adjacencyList[vertex].forEach((neighbor) => {
        if (!visited[neighbor]) {
          return dfs(neighbor);
        }
      });
    })(start);

    return result;
  }
}

// Ejemplo de uso
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addVertex("F");

graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "E");
graph.addEdge("D", "E");
graph.addEdge("D", "F");
graph.addEdge("E", "F");

console.log("Recorrido DFS:", graph.depthFirstSearch("A"));
                
            

Puntos Clave del Algoritmo

• Entrada: Un grafo representado como una lista de adyacencia y un nodo inicial.
• Salida: Un arreglo con los nodos en el orden en que fueron visitados.
• Método:
  • Marca el nodo inicial como visitado.
  • Explora recursivamente cada vecino no visitado del nodo actual.
• Complejidad:
  • Tiempo: O(V + E), donde V es el número de vértices y E el número de aristas.
  • Espacio: O(V) debido a la pila de recursión.
• Aplicaciones:
  • Detectar ciclos en un grafo.
  • Encontrar componentes conectados.
  • Resolver problemas como el laberinto o el análisis de dependencias.

Ejemplo de Ejecución

Grafo inicial:

• Nodos: A, B, C, D, E, F
• Aristas: A-B, A-C, B-D, C-E, D-E, D-F, E-F

Recorrido DFS comenzando en A:

1. Visitar A.
2. Visitar B.
3. Visitar D.
4. Visitar E.
5. Visitar F.
6. Visitar C.

Resultado: [A, B, D, E, F, C]

Información Adicional

DFS es un algoritmo versátil utilizado en muchos problemas relacionados con grafos y árboles. Aunque puede realizarse de forma recursiva o iterativa, la implementación recursiva es más común debido a su simplicidad.