Algoritmo Depth First Search (DFS) para búsqueda en grafos: Explicación, ejemplos y código
Vložit
- čas přidán 8. 07. 2024
- En el video de hoy voy a explicarte como funciona el algoritmo Depth First Search (DFS), uno de los más conocidos en la teoría de grafos y a su vez más utilizados en diversas aplicaciones. Este algoritmo es vital para la búsqueda en profundidad en grafos, y ademas explico la modificación de DFS Forest que vuelve este algoritmo mucho más útil.
Cualquier duda o error que tengas deja un comentario y te ayudare en lo posible!
Pseudocodigos vistos en el video:
DFS(grafo G, Nat u){
marco al vertice u como descubierto (verde);
for(cada vertice v adayacente a u){
if(el vertice v no fue visitado){
padre[v] = u;
DFS(G,v);
}
}
marco al vertice u como visitado (negro);
}
DFS_FOREST(G){
//Inicializacion
for(cada vertice v en Grafo.vertices()){
marco al nodo actual como no visitado;
padre[v] = NULL;
}
//Recorro todos los vertices del grafo, esto es lo que hce el forest
for(cada vertice v en Grafo.vertices()){
if(el vertice v no fue visitado){
DFS(G,v);
}
}
Mas informacion sobre este algoritmo: es.wikipedia.org/wiki/B%C3%BA...
Servidor de Discord El Taller De TD: / discord
Contacto/Contact: eltallerdetd@gmail.com
Información extra, esquemas y mas en mi blog: eltallerdetd.wordpress.com/
Los mejores proyectos con Arduino en el canal: goo.gl/mCKknp
Los mejores proyectos de Programación en el canal: czcams.com/users/playlist?list...
Mis redes sociales:
Suscribite ahora!: goo.gl/s9jhnN
Sígueme en Facebook: goo.gl/8krydS
Sígueme en Twitter: goo.gl/i1V7xo
Sígueme en Instagram: goo.gl/nqgzbF
Indice del video:
00:00 Introduccion al video
00:46 Explicacion Algoritmo Depth First Search paso a paso (Con ejemplos)
11:12 Codigo Algoritmo Depth First Search y seguimiento del mismo
19:44 Determinar si existe un camino entre dos vertices de un grafo
23:22 Explicacion Algoritmo DFS Forest paso a paso (Con ejemplos y codigo)
28:11 Conclusiones finales y despedida
¡Muchas Gracias!
*ERRATA*
A partir del minuto 11:17 el pseudocodigo correcto del DFS es:
DFS(grafo G, Nat u){
marco al vertice u como descubierto (verde);
for(cada vertice v adayacente a u){
if(el vertice v no fue visitado){
padre[v] = u;
DFS(G,v);
}
}
marco al vertice u como visitado (negro);
}
Al hacer el video se me olvido agregar la linea:
*marco al vertice u como visitado (negro);*
Disculpen el error!
es lo que iba a preguntar... solo que el if, pregunta si el vértice adyacente (no es negro), aunque en el segmento de DFS la pizarra preguntas si (no es verde)
se aprecia, la motivacion para implementarlo
Espero que haya servido la corrección Dario, gracias por el comentario!
Ya que lo mencionas la condicion en concreto seria algo asi: estado[u] = NO_VISITADO, donde siempre verificamos que el estado del vertice al que vamos este NO_VISITADO
Saludos!
Me di cuenta un par de horas despues de analizar el video xD, pero se entendio.
se nota como uno aprende con el tiempo, gran explicación, muchas gracias por su aporte compañero, se aprecia muchísimo!!!
Excelente, la mejor explicación que he visto hasta el momento, espero puedas seguir con este formato de videos que la verdad ayudan bastante. Gracias por compartir tus conocimientos.
Muchas gracias amigo! Pronto subire un nuevo video sobre grafos! Saludos!
con este video me di cuenta que mi ex era recursiva, volvía a todos los que llamaba papi antes que yo. Muy interesante este tema tade, un capo.
Buen chiste HunterLeague jaja Abrazo y gracias por ver el video!
Buenísimo, gran explicación, lo entendí todo
Clarísimo, mae usted explica demasiado bien. En serio excelente profe.
Muchas gracias!
Excelente!!! Por favor continúa con los demás algoritmos 😊
Gracias Juan! Ya estoy preparando esos videos! Saludos!
Excelente. Conociendo un poco mas los tipos de algoritmos de Busqueda. 👍
Muchas gracias Cesar, un saludo!
Excelete, muchas gracias.
Muchas gracias !
saludos desde Venezuela muy buena la clase me dio curiosidad y lo vi completo
estoy aprendiendo a programar paso a paso lo lograre
Muchas gracias por tu comentario Samuel! Estoy seguro que seras un gran programador si asi lo deseas! Saludos!
Muchas gracias crack
10/10
Excelente explicación
Muchas gracias!
Excelente explicacion!!
Muchas gracias por tu comentario!
Gracias a dios me dedico a la infraestructura... ajajaja
Muy grosso todo Mr. TD!
Muchas gracias Marcos!! Sin los de infraestructura como vos estariamos todos perdidos jaja!! Abrazo!!
Nunca subió el video de BFS
Grande
Muchas gracias!
Excelente video amigo, pero tengo una duda, podrías explicarme porque o como hace el algoritmo para pasar al vértice E?
5 palabras, crack
Gracias!
Dios quiera q hayas hecho el bfs
Pronto 👀
haz del bfs
Sera el proximo video de esta serie! Muchas gracias por la recomendacion!
Función DFS(grafo G, vértice u):
// Marcar el vértice u como "descubierto" (puedes usar un arreglo de visitados)
Marcar u como "descubierto" (verde)
// Iterar sobre los vértices adyacentes a u
Para cada vértice v adyacente a u:
Si v no ha sido visitado:
// Establecer a u como el padre de v (opcional)
padre[v] = u
// Realizar una llamada recursiva para explorar v
DFS(G, v)
// Marcar el vértice u como "visitado" (puedes usar un arreglo de visitados)
Marcar u como "visitado" (negro)
dejo el codigo mas claro
haz un tutorial
thread hilos
parents child process.
Lo tendre en cuenta, gracias por el comentario!
Hola tidi
Erziooook