Cómo recorrer un árbol no dirigido con DFS y BFS en JavaScript y aplicarlo en proyectos reales de aplicaciones a medida. En Q2BSTUDIO, empresa de desarrollo de software y tecnología, usamos estas técnicas en soluciones de software a medida, ia para empresas y ciberseguridad. Si buscas un partner para transformar tus ideas en productos digitales de alto rendimiento, descubre nuestro enfoque de aplicaciones a medida y software a medida.
Qué es un árbol no dirigido. Es una estructura de nodos conectados por aristas sin ciclos y con un único camino entre cualquier par de nodos. Para programarlo de forma eficiente usaremos una lista de adyacencia, ideal por su simplicidad y rendimiento.
Representación en JavaScript con lista de adyacencia. Ejemplo de árbol con 4 nodos y aristas 0 1, 0 2, 2 3:
const graph=[[1,2],[0],[0,3],[2]]
DFS recursivo recorrido en profundidad. Visita un nodo, explora a sus vecinos y retrocede. Útil para tareas como detección de componentes, orden topológico en grafos dirigidos y exploraciones completas.
function dfsRec(g,start){ const visited=new Array(g.length).fill(false); const order=[]; function visit(u){ visited[u]=true; order.push(u); for(const v of g[u]){ if(!visited[v]) visit(v) } } visit(start); return order }
DFS iterativo con pila. Evita límites de recursión y da control explícito del recorrido.
function dfsStack(g,start){ const visited=new Array(g.length).fill(false); const stack=[start]; const order=[]; while(stack.length){ const u=stack.pop(); if(visited[u]) continue; visited[u]=true; order.push(u); for(let i=g[u].length-1;i>=0;i--){ const v=g[u][i]; if(!visited[v]) stack.push(v) } } return order }
BFS con cola recorrido en anchura. Recorre por niveles y encuentra distancias mínimas en número de aristas, ideal para calcular rutas más cortas en árboles y grafos no ponderados.
function bfs(g,start){ const visited=new Array(g.length).fill(false); const queue=[start]; visited[start]=true; const order=[]; while(queue.length){ const u=queue.shift(); order.push(u); for(const v of g[u]){ if(!visited[v]){ visited[v]=true; queue.push(v) } } } return order }
Reconstrucción de caminos con BFS. Guarda el padre de cada nodo para recuperar la ruta más corta entre start y un objetivo target.
function bfsParents(g,start){ const parent=new Array(g.length).fill(-1); const q=[start]; parent[start]=start; while(q.length){ const u=q.shift(); for(const v of g[u]){ if(parent[v]===-1){ parent[v]=u; q.push(v) } } } return parent } function buildPath(parent,start,target){ const path=[]; for(let v=target; v!==-1; v=parent[v]){ path.push(v); if(v===start) break } path.reverse(); return path }
Complejidad. Tanto DFS como BFS recorren cada arista y cada nodo una vez, con complejidad O V E y memoria O V. En árboles, E es V menos 1, por lo que son lineales y muy eficientes.
Buenas prácticas. 1 valida que la estructura sea un árbol si tu lógica lo requiere, 2 usa números o índices como identificadores para simplificar, 3 preferencia por BFS si buscas rutas mínimas, 4 preferencia por DFS para exploraciones completas y tareas de análisis estructural, 5 en producción, abstrae la cola y la pila para pruebas y métricas.
Aplicaciones reales. En Q2BSTUDIO usamos DFS y BFS en motores de recomendación, agentes IA, análisis de grafos de ciberseguridad, optimización de rutas y workflows de automatización. También los integramos con servicios cloud aws y azure, servicios inteligencia de negocio y power bi para trazar dependencias, linaje de datos y detección temprana de anomalías. Conoce cómo nuestra práctica de inteligencia artificial acelera soluciones de ia para empresas con modelos y agentes IA interoperables.
Resumen accionable. 1 representa tu árbol con lista de adyacencia, 2 usa dfsRec o dfsStack para exploración profunda, 3 usa bfs para niveles y rutas más cortas, 4 añade parents para reconstruir caminos, 5 monitoriza tiempos y memoria. Si necesitas un equipo experto para llevar estas ideas a producción con calidad enterprise, cuenta con Q2BSTUDIO en desarrollo de software a medida, ciberseguridad, servicios cloud aws y azure y analítica con power bi.