Hay dos formas comunes de recorrer un gráfico, BFS y DFS . Teniendo en cuenta un árbol (o gráfico) de gran altura y ancho, tanto BFS como DFS no son muy eficientes debido a las siguientes razones.
- DFS primero atraviesa los Nodes que pasan por un adyacente de la raíz, luego el siguiente adyacente. El problema con este enfoque es que, si hay un Node cerca de la raíz, pero no en los primeros subárboles explorados por DFS, entonces DFS llega a ese Node muy tarde. Además, es posible que DFS no encuentre la ruta más corta a un Node (en términos de número de aristas).
- BFS va nivel por nivel, pero requiere más espacio. El espacio requerido por DFS es O(d) donde d es la profundidad del árbol, pero el espacio requerido por BFS es O(n) donde n es el número de Nodes en el árbol (¿Por qué? Tenga en cuenta que el último nivel del árbol puede tener alrededor de n/ 2 Nodes y segundo último nivel n/4 Nodes y en BFS necesitamos tener todos los niveles uno por uno en cola).
IDFFS combina la eficiencia espacial de la búsqueda primero en profundidad y la búsqueda rápida de la búsqueda primero en amplitud (para los Nodes más cercanos a la raíz).
¿Cómo funciona el IDDFS?
IDFFS llama a DFS para diferentes profundidades a partir de un valor inicial. En cada llamada, DFS no puede ir más allá de la profundidad dada. Así que básicamente hacemos DFS de manera BFS.
Algoritmo:
// Returns true if target is reachable from
// src within max_depth
bool IDDFS(src, target, max_depth)
for limit from 0 to max_depth
if DLS(src, target, limit) == true
return true
return false
bool DLS(src, target, limit)
if (src == target)
return true;
// If reached the maximum depth,
// stop recursing.
if (limit <= 0)
return false;
foreach adjacent i of src
if DLS(i, target, limit?1)
return true
return false
Una cosa importante a tener en cuenta es que visitamos los Nodes de nivel superior varias veces. El último nivel (o profundidad máxima) se visita una vez, el penúltimo nivel se visita dos veces, y así sucesivamente. Puede parecer caro, pero resulta que no lo es tanto, ya que en un árbol la mayoría de los Nodes están en el nivel inferior. Así que no importa mucho si los niveles superiores se visitan varias veces. A continuación se muestra la implementación del algoritmo anterior.
C++
// C++ program to search if a target node is reachable from
// a source with given max depth.
#include<bits/stdc++.h>
using namespace std;
// Graph class represents a directed graph using adjacency
// list representation.
class Graph
{
int V; // No. of vertices
// Pointer to an array containing
// adjacency lists
list<int> *adj;
// A function used by IDDFS
bool DLS(int v, int target, int limit);
public:
Graph(int V); // Constructor
void addEdge(int v, int w);
// IDDFS traversal of the vertices reachable from v
bool IDDFS(int v, int target, int max_depth);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
// A function to perform a Depth-Limited search
// from given source 'src'
bool Graph::DLS(int src, int target, int limit)
{
if (src == target)
return true;
// If reached the maximum depth, stop recursing.
if (limit <= 0)
return false;
// Recur for all the vertices adjacent to source vertex
for (auto i = adj[src].begin(); i != adj[src].end(); ++i)
if (DLS(*i, target, limit-1) == true)
return true;
return false;
}
// IDDFS to search if target is reachable from v.
// It uses recursive DFSUtil().
bool Graph::IDDFS(int src, int target, int max_depth)
{
// Repeatedly depth-limit search till the
// maximum depth.
for (int i = 0; i <= max_depth; i++)
if (DLS(src, target, i) == true)
return true;
return false;
}
// Driver code
int main()
{
// Let us create a Directed graph with 7 nodes
Graph g(7);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 5);
g.addEdge(2, 6);
int target = 6, maxDepth = 3, src = 0;
if (g.IDDFS(src, target, maxDepth) == true)
cout << "Target is reachable from source "
"within max depth";
else
cout << "Target is NOT reachable from source "
"within max depth";
return 0;
}
Python
# Python program to print DFS traversal from a given
# given graph
from collections import defaultdict
# This class represents a directed graph using adjacency
# list representation
class Graph:
def __init__(self,vertices):
# No. of vertices
self.V = vertices
# default dictionary to store graph
self.graph = defaultdict(list)
# function to add an edge to graph
def addEdge(self,u,v):
self.graph[u].append(v)
# A function to perform a Depth-Limited search
# from given source 'src'
def DLS(self,src,target,maxDepth):
if src == target : return True
# If reached the maximum depth, stop recursing.
if maxDepth <= 0 : return False
# Recur for all the vertices adjacent to this vertex
for i in self.graph[src]:
if(self.DLS(i,target,maxDepth-1)):
return True
return False
# IDDFS to search if target is reachable from v.
# It uses recursive DLS()
def IDDFS(self,src, target, maxDepth):
# Repeatedly depth-limit search till the
# maximum depth
for i in range(maxDepth):
if (self.DLS(src, target, i)):
return True
return False
# Create a graph given in the above diagram
g = Graph (7);
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 3)
g.addEdge(1, 4)
g.addEdge(2, 5)
g.addEdge(2, 6)
target = 6; maxDepth = 3; src = 0
if g.IDDFS(src, target, maxDepth) == True:
print ("Target is reachable from source " +
"within max depth")
else :
print ("Target is NOT reachable from source " +
"within max depth")
# This code is contributed by Neelam Pandey
Javascript
<script>
/* Javascript program to search if a target node is reachable from
a source with given max depth.*/
// Graph class represents a directed graph using adjacency
// list representation.
class Graph
{
constructor(V)
{
this.V = V;
this.adj = new Array(V);
for(let i = 0; i < V; i++)
this.adj[i] = [];
}
addEdge(v, w)
{
this.adj[v].push(w); // Add w to v’s list.
}
// A function to perform a Depth-Limited search
// from given source 'src'
DLS(src, target, limit)
{
if (src == target)
return true;
// If reached the maximum depth, stop recursing.
if (limit <= 0)
return false;
// Recur for all the vertices adjacent to source vertex
for (let i of this.adj[src].values())
{
if (this.DLS(i, target, limit-1) == true)
return true;
}
return false;
}
// IDDFS to search if target is reachable from v.
// It uses recursive DFSUtil().
IDDFS(src, target, max_depth)
{
// Repeatedly depth-limit search till the
// maximum depth.
for (let i = 0; i <= max_depth; i++)
{
if (this.DLS(src, target, i) == true)
return true;
}
return false;
}
}
// Driver code
// Let us create a Directed graph with 7 nodes
g = new Graph(7);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 5);
g.addEdge(2, 6);
let target = 6, maxDepth = 3, src = 0;
if (g.IDDFS(src, target, maxDepth) == true)
document.write("Target is reachable from source within max depth");
else
document.write("Target is NOT reachable from source within max depth");
// This code is contributed by cavi4762.
</script>
Target is reachable from source within max depth
Ilustración: Puede haber dos casos:
- Cuando la gráfica no tiene ciclo: Este caso es sencillo. Podemos DFS varias veces con diferentes límites de altura.
- Cuando la gráfica tiene ciclos. Esto es interesante ya que no hay una bandera visitada en IDFFS.
Complejidad Temporal: Supongamos que tenemos un árbol que tiene factor de ramificación ‘b’ (número de hijos de cada Node), y su profundidad ‘d’, es decir, hay b d Nodes. En una búsqueda de profundización iterativa, los Nodes del nivel inferior se expanden una vez, los del siguiente nivel inferior se expanden dos veces, y así sucesivamente, hasta la raíz del árbol de búsqueda, que se expande d+1 veces. Entonces, el número total de expansiones en una búsqueda de profundización iterativa es:
(d)b + (d-1)b2 + .... + 3bd-2 + 2bd-1 + bd That is, Summation[(d + 1 - i) bi], from i = 0 to i = d Which is same as O(bd)
Después de evaluar la expresión anterior, encontramos que asintóticamente IDFFS toma el mismo tiempo que DFS y BFS, pero de hecho es más lento que ambos, ya que tiene un factor constante más alto en su expresión de complejidad de tiempo. IDFFS es el más adecuado para un árbol infinito completo
Complejidad:
Tiempo: O(b^d)
Espacio: O(d)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA