Esta página se tradujo automáticamente con la API de traducción de Google Cloud.
Algunas páginas se pueden leer mejor en su totalidad.
En esta publicación, analizaremos la búsqueda en profundidad, un método para recorrer un gráfico. Dado un nodo inicial, la búsqueda primero en profundidad explora lo más lejos posible a lo largo de cada rama antes de retroceder.
La estructura básica del algoritmo es la siguiente:
function depthFirstSearch(node) {
// base case: if node is null, return
if (node == null) {
return;
}
// mark node as visited
node.visited = true;
// do something with node
// ...
// recurse on each of node's unvisited children
for (let child of node.children) {
if (!child.visited) {
depthFirstSearch(child);
}
}
}
Podemos ver que la función depthFirstSearch toma un nodo como entrada. Lo primero que hace es verificar si el nodo es nulo; si lo es, la función simplemente regresa. Si el nodo no es nulo, el nodo se marca como visitado y luego la función hace algo con el nodo. En nuestro caso, simplemente imprimiremos el nodo.
Después de eso, la función recorre cada uno de los hijos no visitados del nodo y recurre a ellos.
Aquí hay una implementación simple de la búsqueda en profundidad en JavaScript:
function depthFirstSearch(node) {
if (node == null) {
return;
}
node.visited = true;
console.log(node.value);
for (let child of node.children) {
if (!child.visited) {
depthFirstSearch(child);
}
}
}
Y aquí hay un ejemplo de cómo usarlo:
// create a graph
// the graph is an array of nodes, each of which has an array of children
let graph = [
{
value: 1,
children: [2, 3, 4]
},
{
value: 2,
children: [5, 6]
},
{
value: 3,
children: [7]
},
{
value: 4,
children: [8, 9]
},
{
value: 5,
children: []
},
{
value: 6,
children: []
},
{
value: 7,
children: []
},
{
value: 8,
children: []
},
{
value: 9,
children: []
}
];
// choose a starting node
let startingNode = graph[0];
// do the search
depthFirstSearch(startingNode);
Ejecutar el código anterior debería imprimir lo siguiente:
1
2
5
6
3
7
4
8
9
Intente implementar usted mismo la búsqueda en profundidad con los siguientes ejercicios:
Aquí están las respuestas a los ejercicios: