Hola, no se si ponerlo aca o en Matematicas Discretas y Algoritmos, no se si deba explicar que es DFS, pero creo que no es tan necesario, pues se podria hacer viendo el codigo simplemente
Entonces... Dado \( G=(V,E) \) un grafo con \( |V|=n \) y \( |E|=m \) tenemos el siguiente algoritmo
\(
\begin{array}{l}
\textbf{DFS}(s):\\
\quad \text{Initialize } S \text{ to be a stack with one element } s\\
\quad \textbf{while } S \neq \emptyset \textbf{ do}\\
\quad\quad \text{Take a node } u \text{ from } S\\
\quad\quad \textbf{if } \text{Explored}[u] = \text{false} \textbf{ then}\\
\quad\quad\quad \text{Set } \text{Explored}[u] \leftarrow \text{true}\\
\quad\quad\quad \textbf{for each } (u,v) \in E \textbf{ do}\\
\quad\quad\quad\quad \text{Add } v \text{ to the stack } S\\
\quad\quad\quad \textbf{end for}\\
\quad\quad \textbf{end if}\\
\quad \textbf{end while}
\end{array}
\)
Basicamente tenemos una pila \( S \) y \( s \) es un nodo, un nodo donde comenzara la Busqueda DFS, también tendremos un array de tamaño n donde indicaremos si el nodo fue explorado. Lo que debo hallar es T(n), el tiempo de ejecución, la demostracion del libro no me ayuda tanto
Spoiler
Dem:
Observa que un nodo \(v\) puede aparecer en la pila \(S\) múltiples veces, ya que puede ser adyacente a varios nodos \(u\) que exploramos, y cada uno de estos nodos agrega una copia de \(v\) a la pila. Sin embargo, solo usaremos una de estas copias para explorar el nodo \(v\): la copia que se agrega más recientemente.
El paso principal del algoritmo consiste en agregar y eliminar nodos de la pila \(S\), lo cual toma tiempo \(O(1)\). Por lo tanto, para acotar el tiempo de ejecución, necesitamos acotar la cantidad de estas operaciones. Para contar el número de operaciones sobre la pila, basta contar la cantidad de nodos que se agregan a \(S\), ya que cada nodo debe ser agregado una vez por cada vez que puede ser eliminado de \(S\).
¿Cuántos elementos se agregan en total a \(S\)? Como antes, sea \(n_v\) el grado del nodo \(v\). El nodo \(v\) será agregado a la pila \(S\) cada vez que uno de sus \(n_v\) nodos adyacentes sea explorado, por lo que el número total de nodos agregados a \(S\) es como máximo:
\[
\sum_{v \in V} n_v = 2m.
\]
Esto demuestra la cota deseada de \(O(m+n)\) para el tiempo de ejecución de DFS.
Antes que nada, \( T(n) \) es en el peor caso, ahora, lo que si entiendo es lo siguiente: Lo que esta dentro del IF, se ejecuta n veces, pues es el peor caso de que se exploren todos los nodos, por lo tanto se ejecutaran \( n \) veces instrucciones \( O(1) \) para decir que el nodo fue explorado entonces O(n), luego dentro del if esta ese bucle For, que también se ejecuta n veces, como hay n nodos por lema de handshaking la suma nos da \( 2m \) entonces \( O(m) \), hasta ahi todo bien, podriamos decir luego \( O(n+m) \), pero mi pregunta es ¿Y el bucle while? ¿Cuantas veces se ejecuta? como pueden ver en el spoiler si no se dieron cuenta, la pila puede cargar nodos ya visitados, obviamente no los va a recorrer para buscar sus vecinos (pues el if no lo permite y por eso lo permite ejecutar n veces, 1 por nodo) pero, sin menor importancia, se ejecutara alguna instrucción o(1) como es el la comparación del IF, por lo tanto el bucle while se puede ejecutar mas de n veces y hara como minimo o(1), cosa que esto no lo tuvo en cuenta el libro, lo omitio
Podria hacer algo asi, una sumatoria que represente el while
\( T(n)=\displaystyle\sum_{i=1}^?{}(c+n_v+c_4) \) no se cuantas veces se ejecuta el while por eso le puse el simbolo "?" pero seria luego algo asi \( T(n)=\displaystyle\sum_{i=1}^?{c}+\displaystyle\sum_{i=1}^n{v_k}+\displaystyle\sum_{i=1}^n{c_4} \) por las dudas, \( c_2 \) seria la instrucción \( Explored[u]=true \) y \( c \) seria las instrucciones como tomar el nodo de la pila y la comparacion del if. entonces quedaria ahi si \( T(n)=\displaystyle\sum_{i=1}^?{c}+cn+2m \sim{\displaystyle\sum_{i=1}^?{c}+o(m)+o(n)} \)
Faltaría esa sumatoria que es básicamente lo del while, las instrucciones del while que se ejecutaran mas de n veces
Gracias
