Construir un árbol no dirigido a partir de aristas en JavaScript

Cómo construir un árbol no dirigido a partir de un arreglo de aristas en JavaScript

En muchos proyectos de software a medida y aplicaciones a medida necesitamos transformar un conjunto de aristas en una estructura de árbol para recorrer jerarquías, optimizar búsquedas o alimentar modelos de inteligencia artificial. Un árbol no dirigido es un grafo sin ciclos y conectado. Si solo tienes un arreglo de aristas, puedes reconstruir sus relaciones padre hijo con un recorrido en anchura o en profundidad partiendo de una raíz.

En Q2BSTUDIO, empresa de desarrollo de software, creamos soluciones robustas para datos y grafos que integran inteligencia artificial, ciberseguridad, servicios cloud aws y azure y servicios inteligencia de negocio. Si buscas un equipo que convierta tu idea en producto, visita nuestro servicio de software a medida y aplicaciones a medida.

Representaciones comunes de relaciones entre nodos

Lista de adyacencia con Map y arreglos. Ventajas: memoria eficiente, iteración directa sobre vecinos. Objeto o diccionario con arreglos. Similar a Map, válido si las claves son enteros o identificadores simples. Map con Set por nodo. Útil si quieres evitar duplicados de manera automática. Matriz de adyacencia. Conveniente para grafos pequeños y densos, pero poco eficiente en memoria para grafos grandes y es innecesaria para un árbol.

Paso a paso para construir el árbol

1. Recolecta el conjunto de nodos a partir de todas las aristas. 2. Construye la lista de adyacencia agregando para cada arista u v la relación en ambos sentidos. 3. Elige una raíz, por ejemplo el primer nodo o uno que te interese como origen de la jerarquía. 4. Recorre con BFS o DFS. Marca el padre de cada nodo cuando lo descubres y agrega ese nodo a la lista de hijos de su padre. 5. Valida que el número de aristas sea n menos 1 y que hayas visitado todos los nodos. Si no, o hay un ciclo o el grafo no es conexo.

Implementación básica en JavaScript sin dependencias

const buildAdj = function(nodes, edges){ const g = new Map(); for(let x of nodes){ g.set(x, []); } for(const e of edges){ const u = e[0]; const v = e[1]; g.get(u).push(v); g.get(v).push(u); } return g; };

const buildTree = function(edges, root){ const nodes = new Set(); for(const e of edges){ nodes.add(e[0]); nodes.add(e[1]); } const n = nodes.size; const g = buildAdj(nodes, edges); const parent = new Map(); const children = new Map(); for(const x of nodes){ children.set(x, []); } const q = []; q.push(root); parent.set(root, root); let visited = 0; while(q.length){ const u = q.shift(); visited = visited + 1; const nbrs = g.get(u); for(const v of nbrs){ if(!parent.has(v)){ parent.set(v, u); children.get(u).push(v); q.push(v); } else if(parent.get(u) !== v && parent.get(v) !== u){ } } } const edgesCount = edges.length; if(visited !== n || edgesCount !== n - 1){ return { ok:false, reason:1 }; } return { ok:true, parent:parent, children:children, root:root }; };

Uso de ejemplo

const E = [[0,1],[0,2],[1,3],[1,4]]; const T = buildTree(E, 0); si T.ok es true entonces children.get(1) devuelve el arreglo 3 y 4 en ese orden de descubrimiento. También puedes usar DFS reemplazando la cola por una pila para otro orden de construcción.

Validaciones y buenas prácticas

Comprueba que el grafo es conexo verificando que visitaste todos los nodos. Asegúrate de que edges.length sea igual a n menos 1. Si tu identificador de nodo no es numérico, usa Map y Set para evitar conflictos. Para árboles muy grandes, prefiere iteraciones iterativas en lugar de recursión profunda para prevenir desbordes de pila.

Variantes de almacenamiento del árbol ya orientado

Mapa de padre por nodo. parent.get(x) te da el padre directo y es muy útil para subir en la jerarquía. Lista de hijos por nodo. children.get(x) te da la descendencia directa y facilita recorridos top down. Estructura compuesta. Guarda parent y children a la vez con referencias cruzadas para consultas rápidas en ambos sentidos.

Rendimiento

Construir la adyacencia es O n mas m y recorrer con BFS o DFS es O n mas m. En un árbol m es n menos 1, por lo que el proceso completo es lineal respecto al número de nodos.

Casos de uso

Jerarquías de permisos y ciberseguridad, taxonomías de contenidos, árboles de decisión para agentes IA y flujos de automatización, rutas mínimas en estructuras sin ciclos, sincronización de catálogos y dependencias en servicios cloud aws y azure.

Q2BSTUDIO impulsa soluciones con inteligencia artificial, ia para empresas, agentes IA, ciberseguridad y power bi integradas con arquitecturas de datos escalables. Si necesitas crear, escalar o modernizar tu plataforma, hablemos. También podemos ayudarte a llevar tu modelo de IA a producción, desde prototipo hasta operación. Conoce más sobre nuestro enfoque en inteligencia artificial para empresas.

Conclusión

Partiendo de un arreglo de aristas, una lista de adyacencia y un recorrido BFS o DFS bastan para construir y validar un árbol no dirigido en JavaScript. Esta técnica es simple, eficiente y lista para integrarse en soluciones de software a medida, analítica avanzada y servicios inteligencia de negocio con power bi. Si buscas un partner de confianza para diseñar e implementar estas capacidades, Q2BSTUDIO está listo para ayudarte.