Estoy revisando los conceptos de bfs y dfs y recientemente escribí este método de búsqueda para un árbol Trie. Creo que es bfs porque estamos buscando cada nivel comenzando desde la raíz si existe el siguiente valor. No estoy seguro de cómo se vería la implementación de dfs en un problema como este. Aunque podría estar completamente equivocado.
class TrieTree { constructor() { this.root = new TreeNode(); } insert(word) { let currentNode = this.root; for (let char of word) { if (currentNode.children.has(char)) { currentNode = currentNode.children.get(char); continue; } else { currentNode.children.set(char, new TreeNode(char)); currentNode = currentNode.children.get(char); } } currentNode.isWord = true; } //I'm not sure if this should be called bfs or dfs bfs(searchTerm) { let currentNode = this.root; for (let char of searchTerm) { if (currentNode.children.has(char)) { currentNode = currentNode.children.get(char); } else { return false; } } return (currentNode.isWord) } } class TreeNode { constructor(val) { this.data = val; this.children = new Map(); //collection of nodes in TS we would use TreeNode[]; this.isWord = false; } } let tree = new TrieTree(); tree.insert("hello"); tree.insert("bucky"); tree.insert("hell"); console.log(tree.bfs("bucky"));No es ninguno. No está iterando todo el árbol, lo que se puede hacer de manera bfs o dfs. Solo está accediendo al elemento en la posición donde lo espera en su prueba. Esta operación de consulta se suele denominar find , get o has .
Dado
tree.insert("helios"); tree.insert("hello"); tree.insert("helipad");Su estructura de datos se ve así:
h | e | l / \ il / \ \ opo | | sa | d Sin embargo, dado que cada nivel se implementa como un mapa y la búsqueda utiliza Map#has / Map#get no se realiza una búsqueda en todo el espacio. Al buscar "helipad" , el algoritmo nunca consideraría la primera bifurcación después de h -> e -> l , saltaría directamente a la parte i y descartaría la rama l . De manera similar, después de h -> e -> l -> i , no considerará la o como una ruta posible, sino que continuará directamente con p . No es así como funciona la búsqueda primero en amplitud.
Tampoco es así como funciona la primera búsqueda en profundidad, ya que si lo fuera, primero intentaría h -> e -> l -> i -> o -> s y luego retrocedería hasta i e intentaría h -> e -> l -> i -> p -> a -> d .