Projeto e Análise de Algoritmos - Aula 12 - Algoritmos de busca em largura e profundidade em grafos

Summary

The video script delves into the fundamentals of graph exploration through two core search algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS). It explains how BFS systematically uncovers vertices at increasing distances from the starting point, using a queue to manage unexplored nodes. Conversely, DFS explores as far along a branch as possible before backtracking, utilizing recursion. The script provides a detailed walkthrough of both algorithms, including initialization, vertex marking, and the use of time stamps to track vertex discovery and completion. It also touches on the computational complexity and time consumption of these algorithms, offering insights into their practical applications.

Takeaways

• 📚 The script discusses two fundamental graph exploration algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS).
• 🔍 BFS is used to systematically explore a graph from a starting vertex, discovering all vertices at the same level before moving to the next.
• 🌐 DFS, on the other hand, explores as far as possible along each branch before backtracking, creating a tree or a forest of explored vertices.
• 🔄 BFS uses a queue to keep track of vertices to explore, ensuring that vertices are processed in the order of their discovery level.
• 📈 The script explains that BFS marks vertices with different colors to indicate their state, such as unexplored, discovered, or fully explored.
• 🎯 DFS uses a stack implicitly through recursion to keep track of vertices to visit and marks them with a visit time to indicate when they were discovered.
• 🕒 Both algorithms have a time complexity of O(V + E), where V is the number of vertices and E is the number of edges in the graph.
• 📝 The script provides a step-by-step explanation of how BFS and DFS work, including the initialization process and the iterative or recursive steps involved.
• 🛠️ The pseudocode for both algorithms is presented, showing the logic behind the exploration process and the conditions checked at each step.
• 🌳 DFS can result in a spanning tree or a forest if the graph is not connected, whereas BFS will explore all vertices reachable from the starting point.
• 🔑 The script highlights the importance of these algorithms in solving various problems, such as finding paths between vertices or determining the connectivity of a graph.

Q & A

What are the two fundamental search algorithms discussed in the script?

The two fundamental search algorithms discussed are Breadth-First Search (BFS) and Depth-First Search (DFS).

What is the primary purpose of using search algorithms in graphs?

The primary purpose of using search algorithms in graphs is to explore or traverse the graph systematically, which is essential for solving various problems such as finding paths between vertices.

How does Breadth-First Search (BFS) explore a graph?

BFS explores a graph by visiting all the vertices at the present depth before going deeper to the vertices at the next depth level. It uses a queue to keep track of the vertices to be explored.

What does the term 'level' refer to in the context of BFS?

In the context of BFS, 'level' refers to the shortest distance from the source vertex to the current vertex, measured in the number of edges.

How does Depth-First Search (DFS) differ from Breadth-First Search (BFS) in terms of exploration strategy?

DFS differs from BFS in that it explores as far as possible along a branch before backtracking. It uses a stack (either explicitly or via recursion) to remember where to continue the search.

What is the significance of marking vertices in search algorithms?

Marking vertices is significant to keep track of which vertices have been visited to avoid revisiting them and to prevent infinite loops in the search process.

What data structure is typically used to implement the queue in BFS?

A queue data structure is typically used to implement BFS, where vertices are dequeued in the order they were enqueued, ensuring exploration by levels.

How does the script describe the process of updating distances in BFS?

The script describes the process of updating distances in BFS by stating that when a vertex is dequeued, its adjacent vertices are examined, and their distances are updated if they are further from the source vertex than the current vertex.

What is the purpose of the 'predecessor' concept in DFS?

The 'predecessor' concept in DFS is used to keep track of how the algorithm arrived at each vertex, which is essential for reconstructing paths or understanding the order of exploration.

How does the script explain the time complexity of BFS and DFS in terms of operations on a queue or stack?

The script explains that each vertex and edge is enqueued and dequeued once in BFS, and similarly, each vertex is pushed and popped once in DFS, leading to a time complexity of O(V + E) for both algorithms, where V is the number of vertices and E is the number of edges.

Outlines

00:00

📚 Introduction to Graph Exploration Algorithms

This paragraph introduces the topic of graph exploration algorithms, focusing on two fundamental algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS). It explains the importance of these algorithms in systematically exploring a graph, which has numerous applications such as finding paths and solving various search problems. The explanation includes the basic concept of marking vertices as discovered and the process of exploring all vertices from a starting point using BFS and DFS.

05:01

🔍 Detailed Explanation of Breadth-First Search

The second paragraph delves into the specifics of the Breadth-First Search algorithm. It describes the process of BFS, starting from an initial vertex and exploring all its neighbors at the present depth prior to moving on to nodes at the next depth level. The summary explains the use of a queue to keep track of vertices to be explored and how BFS can be used to find the shortest path in an unweighted graph. It also discusses the algorithm's time complexity, which is O(V + E), where V is the number of vertices and E is the number of edges.

10:03

🌐 Analysis of Depth-First Search Algorithm

This paragraph provides an in-depth look at the Depth-First Search algorithm, contrasting it with BFS. DFS is characterized by exploring as far as possible along a branch before backtracking. The summary outlines the process of visiting vertices, marking them as discovered, and recursively visiting all unvisited adjacent vertices. It also touches on the use of a stack or recursion to manage the traversal and the time complexity of DFS, which is also O(V + E), similar to BFS.

15:07

🕒 Time Complexity Analysis of Search Algorithms

The fourth paragraph discusses the time complexity of both BFS and DFS algorithms. It explains that each operation of enqueueing and dequeueing in BFS, as well as the recursive calls in DFS, contributes to the overall time complexity. The summary emphasizes that the time spent on these operations is proportional to the number of vertices and edges in the graph, leading to a conclusion that both algorithms have a linear time complexity in terms of the graph's size.

20:08

🛠️ Recursive Implementation of Depth-First Search

This paragraph focuses on the recursive implementation of the Depth-First Search algorithm. It describes the process of visiting a vertex, marking it as discovered, and then recursively visiting all unvisited adjacent vertices. The summary explains how the algorithm uses a time counter to track the order of vertex discovery and the completion of the visit. It also illustrates how DFS can create a forest of trees, with each tree representing a connected component of the graph.

🎓 Conclusion on Graph Search Algorithms

The final paragraph wraps up the discussion on graph search algorithms, summarizing the key points about BFS and DFS. It highlights the practical applications of these algorithms in graph theory and their significance in computer science. The summary concludes with a note on the presentation of the algorithms, hoping that the explanation has been informative and enjoyable.

Keywords

💡Breadth-First Search (BFS)

Breadth-First Search is an algorithmic paradigm used for traversing or searching tree or graph data structures. It explores the neighbor nodes at the present depth prior to moving on to nodes at the next depth level. In the context of the video, BFS is used for systematically exploring a graph to find paths or determine the shortest path. An example from the script is the description of BFS as an algorithm that 'discovers all its neighbors and if you see from that initial vertex s, although you're going to do that algorithm in parallel, it will determine the distance of each of its vertices to s'.

💡Depth-First Search (DFS)

Depth-First Search is another graph traversal algorithm that explores as far as possible along a branch before backtracking. It is used to find paths, test connectivity, and for various other tasks in graph theory. The script refers to DFS as an algorithm that 'proceeds to search always from the most recently discovered vertex until it has no more undiscovered neighbors', contrasting it with BFS.

💡Graph

A graph in mathematics and computer science is a structure that consists of a set of objects in which some pairs of the objects are in one-to-one correspondence. In the video, the graph is central to explaining how algorithms like BFS and DFS work, as the script mentions 'a fundamental problem in graphs and knowing how to explore a graph systematically'.

💡Vertices

In graph theory, a vertex (plural vertices) is the fundamental unit of which a graph is composed. The script uses the term 'vertices' when explaining the process of graph exploration by BFS and DFS, stating 'we have a set of vertices and sets of edges'.

💡Edges

Edges are connections between vertices in a graph. The script refers to edges in the context of explaining how a graph is made up of vertices and edges, which are essential components for the operation of search algorithms like BFS and DFS.

💡Traversal

Traversal refers to the process of visiting all the elements of a data structure in a specific order. In the video, traversal is the main operation performed by BFS and DFS algorithms as they explore a graph, with the script mentioning 'how to explore a graph systematically'.

💡Search Algorithm

A search algorithm is a method for solving the search problem, which is the task of finding a particular item from a collection of items. The video discusses search algorithms in the context of graph traversal, specifically BFS and DFS, as it explains 'algunas aplicaciones son extraídas como problemas de búsqueda'.

💡Distance

In the context of graph theory, the distance between two vertices is the length of the shortest path between them. The script mentions the concept of distance when describing BFS, stating 'it will determine the distance of each of its vertices to s', where 's' is the starting vertex.

💡Queue

A queue is a linear structure that follows a particular order in which the operations are performed. The script refers to the use of a queue in the BFS algorithm, where it is used to keep track of vertices to be explored, as indicated by 'usar una fila, entonces llamamos un ejemplo aquí'.

💡Stack

A stack is another linear data structure that follows the Last In First Out (LIFO) principle. The script does not explicitly mention 'stack', but the concept is implied in the context of DFS, which can be implemented using a stack to keep track of vertices to be explored next.

💡Time Complexity

Time complexity is a measure of how long an algorithm takes in terms of the amount of input. The script discusses the time complexity of BFS, stating 'consumo de tiempo ese algoritmo primero vamos a analizar a parte de visita dos vértices', explaining the time it takes for the algorithm to perform operations.

Highlights

Introduction to graph exploration algorithms, specifically breadth-first search (BFS) and depth-first search (DFS).

Explanation of how BFS systematically explores a graph by discovering all vertices at the same level before moving on to the next.

DFS is introduced as an alternative that explores as far as possible along a branch before backtracking.

BFS algorithm's process of marking vertices as discovered and using a queue to keep track of vertices to be explored.

DFS algorithm's use of a stack or recursion to explore deeper into the graph's branches.

The concept of graph traversal to find simple paths between vertices.

Illustration of BFS algorithm with a step-by-step example, showing how vertices are discovered and explored.

Explanation of how DFS marks vertices with discovery and finish times to track the order of exploration.

The importance of marking vertices as discovered in both BFS and DFS to avoid revisiting them.

Visualization of how BFS produces a single tree, while DFS can produce a forest of trees.

Algorithmic complexity analysis of BFS, highlighting its time complexity.

Algorithmic complexity analysis of DFS, discussing its time complexity in comparison to BFS.

Practical applications of BFS and DFS in solving various graph-related problems.

The role of BFS in finding the shortest path in unweighted graphs.

DFS's utility in topological sorting and detecting cycles in graphs.

Pseudo-code for implementing BFS, providing a clear guide for coding the algorithm.

Pseudo-code for implementing DFS, including recursive and iterative approaches.

Conclusion summarizing the key points of BFS and DFS algorithms and their significance in graph theory.

Transcripts

[Música]

i

[Música]

o la pesoe sellan beijing 2 nos habla

número 12 del proyecto y análisis y

algoritmos en esa aula veremos al

algoritmo de búsqueda largura y

algoritmo de búsqueda profundidad y en

grafos

un problema fundamental en grafos y

saber cómo explorar un grafo de forma

sistemática muchas aplicaciones son

extraídas como problemas de busca

entonces algoritmos de busca son a base

de varios algoritmos más gerais en

grafos

como que podemos explorar un grafo

suponía que bosé que el saber si existen

caminos simples entre dos vértices

porque tenemos que pensar aquí es que en

un grafo pues cuando per cojamos su

grafo la gente consiga llegar un vértice

anterior en todo de algunos editores y

tengo que marcar los vértices que ya

fueron explorados tenemos que marcar los

vértices tal vez por ejemplo como face o

algoritmo de busca en profundidad y

largura de algún insecto

comencemos entonces como algoritmo de

búsqueda largura sellaje un grafo o si

tenemos un conjunto de vértices y

conjuntos de aristas y tenemos un

vértice se ha partido la famosa será

busca o algoritmo de búsqueda y largura

también conocido como brett fierce age

el ifai per todas las aristas de

geógrafo descubriendo todos sus suertes

y satín si veis a partir de ese no

inicial de ese vértice inicial s

aunque que vais a hacer ese algoritmo en

tonel y va a determinar la distancia de

cada uno de sus vértices a s

esa distancia país en mérida el número

de aristas

vamos porque vamos a comenzar en todo a

explorar ese grafo de aquí mostrado una

figura y tenemos un estado una verdad de

uno inicial que es en un aparte del que

vamos a aplicar a busquen largura antes

de encontrar un vértice a distancia cama

y zoom de ese todo suceda desde la

distancia caso encontrados pero

algoritmo de búsqueda largura en todo

primero que va a hacer encontrar ese

vértice un que está a distancia cero del

mismo después va a encontrar todos sus

vértices que están a distancia aunque

sería 1 2 4 y 3 después va a encontrar

los que están a distancias 2 que serían

un su vértice 6 y 6 y de puestos que

están a distancia 3 que sería un vértice

cuándo

ejecutamos algoritmo de búsqueda largura

he producido un árbol he producido más

árboles

con jasen ese es a árboles by contener

todos sus vértices accesibles a partir

de ahí vamos necesario les vamos ver un

camino más culto desde ese ate en que te

un vértice a csif esta valores a mostrar

aquí con líneas ver medias mentón

tenemos un árbol en hai sada en un

vértice

y el lacón tiene todos sus vértices que

sería en este caso todos sus vértices

del grafo por todos ellison accesibles a

partir de vértice

para facer a busquen largura ya falamos

que precisamos marcaron sus vértices de

algún objeto nunca se buscan largura sus

vértices son pintados de diferentes

colores

vamos coloridos vértices de blanco sin

ciprés o en blanco podemos colocar los

vértices que no fueron descubiertos

aínda en sheen's a vértices que ya

fueron descubiertos más a indalo

examinamos sus vecinos y en preto sus

vértices cuyos vecinos ya fueron

examinados y para mantener sus vértices

hinchas vamos a usar una fila

entonces llamamos un ejemplo aquí

tenemos un grafo de inicio tenemos todos

sus vértices coloridos de blanco y todos

él existen distancia infinita

vamos a hacer a buscar el argumento

compartido ver si este es el primero que

efecto el vértice origen y pintado de

zinsa que ese de aquí vértice origen y

eléctrica de considerado descubierto en

el jr y colocado una fila nos afila

llamada de que ese vértice es retirado

de la fila o sea su vértice se ha

retirado de la fila y usuarias es

israelí son colocados en que hay

pintados de ciencia quien somos

adyacentes a ese son vértices

liberticida bleu usd hoy somos ser

colocados manos afilada bleú viaje

el índice actualizada distancia para que

en este caso sería a distancia a ese 1 y

aquí a distancia de doble a ese 1 y

actualizado también un parking dubai

está marcando aquí como por medio de

ésta para saber quién culpar

apósito coloritmo su vértice completo

por sus museos vecinos sus vecinos de

ese ya fueron todos visitados

descubiertos

antón tenemos una fila dable hubiese un

próximo elemento que va a ser retirado

de la fila va a ser dable los diseños de

edad lo que en que son son tesis lo que

vamos a hacer vais a ir dable y va a

entrar una fila de gis

elevamos el colorido de zinsa y un

vértice dable uvais el colorido de preto

actualizamos a distancia están siento a

que se va a ser una más que upyd cada

uno de él y en ese caso para tablet en

distancia aún por tanto tesifonte

distancia 2 vamos a estar a una

distancia 2

el próximo elemento que vais a retirar

una fila de escayola mosquín que son un

censista eres son v y u s más único que

blanco v entonces ha retirado guarde

aquí va a ser ingerido v

una fila cierto color y maxwell de

presto y ahí continuamos con un proceso

quien que el próximo que va a ser

retirado de la fila de usted hoy vamos

que en que somos vecinos de usted

son 16 maestros y ya fue visitado antes

tanto observe que son menchi colocamos

la fila vértices blancos en este caso

apenas u que son inmediatamente

coloridos de ciencia o entran a fila ok

el próximo elemento que vais a retirado

de la fila eu si hallamos que en que

somos adyacentes a él y son weeps y lo

cierto único blanco que hay es en chile

weeps el aumento muchas hay wifi lo

entra en la fila

vamos austeros y siguen sin ser todo

actualizamos también a distancia

actualizamos que en kuwait pronto y

después su próximo vértice que vice se

ha retirado de la fila v estamos aquí

como ve él y no tenía ya sense el que se

abran cuento no voy a contestar nada

solamente y vais a ir úbeda fila un

próximo que están a fila

no tengo más niño un vértice blanco

adyacente a él y entonces ser simples

mensaje tirado la fila y actualizado

claro oa distancia a tves

en este caso

y después un último elemento baixa

retirado de la fila que vino

en torno al final tenemos a fila fácil

un peso del código de algoritmo de

búsqueda largura está aquí en todo

primero que pasemos a patxi de

inicialización tono inicio lo que vamos

a hacer para todos sus vértices excepto

un vértice es el que vamos color y de

liz de blanco vamos a hacer vamos a

hacer el color y de lis de blanco

colocar a distancia infinito para cada

uno de ellis y como no conocemos aínda

que en kuwait dubai ser mío

el próximo paso es color y vértice s

como zinsa que un primero vértice que

vais a descubierto a distancia de ese

para ese cero e hizo que ésta sino fetal

una línea 6 y después su padre es en yo

y no inicio a fila está vacía aquí a

phil está vacía y colocamos su vértice s

una fila que sería esa línea

en cuanto existan vértices cintas o que

vamos a hacer es tirar primero el

elemento de la fila la línea 11 y para

cada vértice asia central y que hizo que

éstas y no afecte aquí hay en chivay

primero preguntar si el blanco si el

blanco qué vamos a hacer vamos color ir

cada vértice alias en sí de zinsa

actualizar a distancia una línea en esa

línea de aquí actualizar quien que hay

aquí es cierto tengo que vamos a ver el

club hay desde uno que le voy a

descubierta desde que en ese caso y

después vamos colocar ese vértice ve una

fila eso que está siendo feito una línea

16

después de tener visitado todos los

vértices adyacentes

aquí hay en tipos y color y dentón

finalmente un vértice como que

hizo efecto en una niña

ahora veamos cuánto que consume de

tiempo ese algoritmo primero vamos a

analizar a parte de visita dos vértices

adyacentes cada vértice colocado en la

fila no máximo más beige y por tanto

retirado de la fila también un máximo

más beige

ok precisamos saber cuánto que consume

cada operación de colocar la fila y deja

tirar la fila cada operación de de kiwi

en club que sería colocar y retirar la

fila de morante en pro de un evento a un

tiempo total de operaciones una fila va

a ser o debe

el indicio sabemos que la lista de

aceites de cada vértice examinados

solamente cuando vértice girado y

desequilibrado cierto a listas de

adyacencias de cada vértice he examinado

la verdad sin un máximo más vez ya vimos

las aulas anteriores que la cantidad de

elementos las listas de adyacencia o de

cantidad de aristas

por tanto un tiempo gasto para bajar

todas todos los elementos las listas de

adyacencias va a ser idea

entonces podemos concluir que la línea

de esta línea de solito consume o dea a

partir de inicialización como estamos

pero corriendo aquí todos sus vértices

en ese lazo de aquí la línea aún estamos

por cogiendo todos sus vértices va a ser

o debe y por tanto consumo el tiempo de

algoritmo de busca en largura va a ser o

debe maysan

ok alto ahora pasemos para el próximo

algoritmo de busca que sería el

algoritmo de búsqueda profundidad

conocido también como decir search de fs

con la idea de ese algoritmo y proseguir

a buscar siempre a partir de vértice

descubierto más recientemente ate que

ese no tenía más diseños descubiertos

entones ese caso se falta para un

vértice anterior a él

o posto dudo algoritmo anterior busquen

largura

o algoritmo de búsqueda profundidad y

explorado vértice más antiguo primero

y diferente de otro algoritmo que vimos

antes él no va a crear solamente una

él iba a crear más florencia que sería

un conjunto de árboles

o algoritmo de búsqueda profundidad y

también marca los vértices de albudeite

en este caso los vértices van josé

verdejo tú los rótulo de que un momento

en que vértice fue descubierto o sella

en un momento en que uberti se tornó 60

o efe que un momento en que examinamos u

se os veciños o sella un momento en que

torno o secreto y así a gente sabe que

un vértice blanco desde inicio ate the

scene sa desde ate efe entre df y el

proyecto a partir de ese aunque que

vamos a hacer no algoritmos agora para

enmarcar con esos rótulos df y así va a

precisar de veo más variado que marque

el tiempo de visita

tenemos aquí un ejemplo tenemos un

vértice origen que va a ser este de aquí

no iniciando marcamos comenzamos con ese

contador de tiempo el tempo está en cero

cuando visitamos es el vértice origen un

contador va a estar en 1 y marcamos un

tiempo de visita del vértice de ese

vértice de aquí común

ay preguntamos existe algún vértice hay

esencia o ver dice que no tenía sido

descubierto si existen varios nada

así es existen 3-6 israel

vamos pegarse un de ellis

nos peguemos ese de aquí marcamos el y

como visitado con marcamos su valor de

de el que va a ser 2

cierto ahí continuamos hacemos la misma

pregunta existe algún 26 ya sea en el

vértice actual que no tenía sido

descubierto existe si existen varios

existe ese y ese de aquí que estamos

pegado un de ellis

y antes de eso vamos a marcar él como

visitado un tiempo de él y de visita que

se dio 3

hacemos la misma pregunta existe algún

vértice a ellas en su vértice que no

tenía sido descubierto entonces vemos

aquí usadas ya sensis a ese vértice de

aquí ese maíz feliz ya fue descubierto

antes no tengáis en todo

no existe termine con ese vértice y

marcó el y marcó el fin de él

marcamos con

con un valor de esa variable que hay en

esta tengo a un longo de tiempo que

sería 4 con un tiempo 4 ese vértice ya

fue descubierto y elisa fue y todos sus

vecinos de delicias fueron analizados

termine con ese vértice pintó el y de

y volta se la buscaba yo

precursor de ese vértice quien que un

precursor de ese vértice ese de aquí

y continuamos haciendo la misma pregunta

existe al burger dicen 10 en su vértice

a ese vértice de aquí que no te haya

sido descubierto existe existes

que vamos a visitar el viento y marcar

un tiempo de visitar visitamos en línea

tiempo 5

pasemos continuamos con la misma

pregunta existe algún berti celia

sánchez efe dice que no tenía sido

descubierto no

esto no existe termine con él y marcó un

tiempo del tiempo efe y en todo

colocamos aquí 6 y terminé de visitar un

tiempo 6 ese vértice botas en la busca

pero precursor de ese vértice que en que

un precursor de ese vértice un precursor

de ese de aquí

preguntamos si no existe algún vértice

adyacente a él y que no te haya sido

descubierto no tengáis entonces marcamos

su tiempo de fin de el tiempo de fin de

visita de él y estamos no seis un

próximo serios hecho con él y fue

marcado con un tiempo de 5h y alende

hizo el y colorido de pret

existe algún vértice alias en su vértice

que no tenga sido descubierto

entramos por fidel y existe si tomamos

más caro el tiempo de visita de él que

sería tiempo hoy te parece el vértice de

aquí

continuamos existe algún particiación si

a él y si marcamos un tiempo de visita

del serio no existe algún vértice hacia

él y no marcamos el y como y

marcamos su tiempo de fin que sería days

desde aquí

la i volta moss para precursor de el que

guaita y ahora vamos preguntar si existe

algún vértice que haya no fue visitado

no tengáis en todo marcamos el y como

marcamos su tiempo de visita de

fin de visita de él que sería 11 votamos

para precursor que ese de aquí o que

existe algún vértice adyacencia el que

no tenía sido visitado no acabamos con

ese vértice marcamos un tiempo de de

visita de fin va a ser un 12 y pronto

qué aconteció aquí la gente comenzó como

vértice origen la gente visitó todos sus

vértices accesibles a partir de ese

vértice por en haina no visitamos esos

dos vértices de aquí tú que te vai facer

o algoritmo que busquen profundidad y

les voy a continuar con los vértices que

hayan estado en blanco que hainán o

fueron visitados debemos comenzar con

intentando visitar ese vértice de aquí

ahora él iba a ser un vértice origen

marcamos de un tiempo de inicio la

visita 13 preguntamos si existe algún

plan y será recibido a partir de él ya

existe sin ese de aquí marcamos su

tiempo de visita del 14 preguntamos si

existe algún vértice adyacente ese 14

que no tenía sido visitado no existe más

en todo acabamos con ese vértice

marcamos su tiempo de fin que facer 15

pronto contamos para un antecesor de él

y que ese vértice de aquí preguntamos si

existe algún vértice adyacencia del que

aínda no fue visitado no existen más

niños en todo acabamos también con él y

marcamos su tiempo de fin de visita del

que va a ser 16

un resultado que los resultados de

algoritmo de búsqueda profundidad de una

floresta en este caso más floresta que

tendrás árboles cadenas los árboles la

verdad ya sabe estas es de esas árboles

esta marca de enfermería y tenemos aquí

un árbol

y tenemos aquí una u otra árbol

plantemos un árbol con seis vértices y

tenemos otra árbol con dos vértices o

pensamos en toma gora finalmente

algoritmo de búsqueda profundidad juppé

pseudo código de eli y primero vamos a

ver qué acontece cuando visitamos un no

un vértice lo primero que vamos a hacer

es color y el vértice de zinsa

porque indica que uberti se acabo de ser

descubierto después vamos a hacer ese

contador que vaya aumentando de 1

marcamos su tiempo de visita de de ese

vértice con ese valor de esa variable de

tiempo del contador de tiempo y después

vamos ver si existe algún vértice alias

el chele y se está haciendo feito las

líneas 4 5 y 6

tengo que vamos a hacer si un vértice

hacia seychelles de blanco

en todo el juego marcado en kuwait desde

antes el pay de ella más recursiva mente

o algoritmo que visite un vértice como

llamar o algoritmo decir search con un

parámetro b para ser llamado recursiva

mente visitar a gurús vértice ve cuando

él y termine de explorar todos sus

vértices adyacentes

entonces ya podemos hablar que todos sus

vértices adyacentes fueron examinados y

por tanto podemos marcar ese vértice o

decor prette ok y marcamos también un

tiempo designado de visita de él y que

eeuu efe

esto de aquí que vais a hacer en la

verdad crear un árbol más segura

antes que busca en profundidad el y cría

una floresta con como pasemos para crear

la floresta lo que vamos a hacer

entonces llamar es y algoritmos varias

veces para los vértices que aínda son

blancos aunque falso decir 6 visite el y

visita un vértice y todos los usos

adyacentes para todos sus usuarios

alcanzables a partir de él y voy a crear

más árboles con país en un es en ese

caso

entonces aquí tenemos un algoritmo que

se llama ese algoritmo decir sense visit

este algoritmo va a recibir un conjunto

de vértices conjunto de aristas y un

primero que vais a hacer a partir de

inicialización y después a llamada a ese

algoritmo que visita un vértice no es un

apache de inicialización que son esas

líneas de aquí ser tocadas vértice del

primero y colorido de blanco no sabemos

qué en kuwait son colocamos su país todo

el mundo y guagua new un tiempo comencé

en cero tiempo de visita que hoy en

tchité para marcar de puestos de uefa y

después para cada vértice que existe en

un grafo que vamos preguntar y vértice

hay blancos y el blanco visitamos cl

y entonces el llamado ese algoritmo de

aquí que va a visitar todos sus vértices

que son atendibles a partir de v

se detuvo parece que aquí un árbol y

aquí una verdad si fueses criada más

floresta ese algoritmo de búsqueda

profundidad si también tengo un consumo

de tiempo de odio de maíz

igual que el algoritmo de busca en

largura con eso terminamos entonces

a presentar son los dos algoritmos

básicos de busca buscar en algoritmos

que en profundidad y en grafos espero

que nos estén y han gustado y teatros

[Música]

2

[Música]

[Música]

sí

[Música]

ah