DFS Complejidad del tiempo

DFS representa la búsqueda en profundidad. Se refiere a cómo se visitan los nodos de un árbol hasta que se encuentre el nodo deseado. Por simplicidad, se visitarán todos los nodos en este artículo. La idea es ver todos los nodos, con cada nodo visitado una vez. Un nodo también se llama vértice. La búsqueda de profundidad primero puede estar en uno de los tres órdenes: pre-pedido, en pedido o posterior a. El recorrido por adelantado se utiliza en este artículo. Este artículo utiliza el siguiente árbol se usa para ilustrar el pedido anticipado para la búsqueda de profundidad primero:

Una rama en el árbol se llama borde. Este artículo tiene como objetivo ilustrar lo que se conoce como la complejidad del tiempo para la búsqueda de profundidad. DFS se explica brevemente. C ++ se usa para la ilustración de código.

Pasado anticipado de pedido para la búsqueda de profundidad primero

El algoritmo es como sigue:

1) Visite el vértice actual.
2) atravesar el sub-árbol izquierdo del vértice actual de manera recursiva.
3) atravesar el sub-árbol derecho del vértice actual de manera recursiva.

Para el árbol anterior, el primer vértice que se debe visitar es un. Este es el vértice actual. Atravesando recursivamente el sub-árbol izquierdo y luego el sub-árbol derecho significa visitar B mientras la visita de C se registra en la memoria que se visitará más tarde.

En B, B es el vértice actual. Atravesando recursivamente el sub-árbol izquierdo y luego el sub-árbol derecho significa visitar E mientras la visita de F se registra en la memoria que se visitará más tarde.

En E, E es el vértice actual. E no tiene sub-árbol a la izquierda o derecha (sin bordes). La última grabación en la memoria para visitar fue el sub-árbol (borde) adecuado para B. El sub-árbol correcto para B consiste en F precedido por su borde. En este punto, se visita F.

La grabación anterior en la memoria para visitar ahora es el sub-árbol (borde) adecuado para un. El sub-árbol correcto para un registrado consiste en C seguido de sus bordes e hijos. En este punto, se visita C. C tiene tres bordes. Según el algoritmo, se accede primero al borde izquierdo.

Cuando se accede al borde izquierdo, se visita G. No hay niño para g. Por el algoritmo, H comparte el mismo padre con G, y como está a la derecha de G, se visita a continuación.

"I" está a la derecha de H y comparte el mismo padre con H. Por el algoritmo, se debe visitar cualquier nodo a la derecha de otro nodo después de visitar el nodo. No importa si el nodo recién visitado está a la derecha de otro nodo. Entonces "yo" se visita a continuación.

No hay nodo a la derecha de "i". C y todos sus descendientes han sido visitados. Sin embargo, tenga en cuenta que hay un nodo a la derecha de C. Este nodo es D. Por el algoritmo, cualquier nodo a la derecha de otro nodo debe visitarse después del nodo (visitado). No importa si el nodo visitado estaba a la derecha de algún otro nodo. Entonces D se visita a continuación.

D tiene dos hijos, J y K. J está a la izquierda de K. J es visitado primero antes de k.

El algoritmo de búsqueda de profundidad se puede resumir de la siguiente manera: después de visitar la raíz, visite el vértice izquierdo mientras cae recursivamente a la izquierda. Desde la parte inferior izquierda, el vértice más a la izquierda, visite los hermanos derecho de ese vértice, y luego suba por el árbol, hacia la derecha y bajando de vez en cuando de manera apropiada.

Con eso, la secuencia DFS del árbol anterior es: A, B, E, F, C, G, H, I, D, J, K.

Complejidad del tiempo

El árbol anterior tiene 11 vértices y 10 bordes. Si el árbol está bien almacenado, entonces el escaneo de todo el árbol involucrará 11 vértices y 10 bordes. Esta es una apreciación de la velocidad de funcionamiento de la búsqueda de profundidad. Es complejidad del tiempo. Está escrito como:

O (| V |+| E |)

Donde | V | es el número de vértices (nodos) y | E | es el número de bordes. Para este árbol, el total es 21 = 11 + 10. El "O" tiene que estar ahí.

Estructura para el árbol

La organización de árboles se puede describir de la siguiente manera:

Vértice A: Niños: B, C, D
Vértice B: Niños: E, F
Vértice C: Niños: G, H, I
Vértice D: Niños: J, K
Vértice E
Vértice F
Vértice g
Vértice H
Vértice I
Vértice j
Vértice k

El árbol anterior se almacenará en un_map de vectores desordenado. Un vértice es una clave, y los niños son los valores del vector de la clave. Los vértices de E a K no tienen hijos.

Codificación de C ++

El programa puede comenzar con el siguiente encabezado:

#incluir
#incluir
#incluir
usando el espacio de nombres STD;

Codificación de C ++ para los vectores undered_map-of-vectores

El undered_map-of-vectors se crea con el siguiente código:

desordenable_map > umv = 'a', 'b', 'c', 'd',
'B', 'e', 'f',
'C', 'g', 'h', 'i',
'D', 'j', 'k',
'E', ,
'F', ,
'G', ,
'H', ,
'I', ,
'J', ,
'K', ;

Esto se puede colocar justo debajo del encabezado anterior.

La función de profundidad primero

Es una función recursiva que imprime cada vértice (nodo) visitado. Es:

Vacío de profundidad de FirstSearch (Char Parent)
cout << parent << "; //print vertex
para (int i = 0; iprofundidadFirstSearch (umv [parent] [i]);

Después de imprimir el vértice izquierdo, el bucle for-bucle imprimiría los vértices derecho. El for-loop tiene el retiro.

Función principal de C ++

Una función principal adecuada para el programa es:

int main (int argc, char ** argv)

profundidadFirstSearch ('a');
cout << endl;
regresar 0;

El algoritmo para la búsqueda de profundidad primero es el siguiente:

1) Visite el vértice actual.
2) atravesar el sub-árbol izquierdo del vértice actual de manera recursiva.
3) atravesar el sub-árbol derecho del vértice actual de manera recursiva.

Esto se puede interpretar de la siguiente manera: después de visitar la raíz, visite el vértice izquierdo, bajando recursivamente a la izquierda. Desde la parte inferior izquierda, el vértice más a la izquierda, visite los hermanos derecho de ese vértice y suba recursivamente por el árbol, hacia la derecha, bajando de vez en cuando, apropiadamente.

La complejidad del tiempo para el algoritmo de búsqueda de profundidad primero es:

O (| V |+| E |)

Conclusión

DFS representa la búsqueda en profundidad. Se refiere a cómo se visitan los nodos de un árbol hasta que se encuentre el nodo deseado. Por simplicidad, todos los nodos del árbol de este artículo han sido visitados. La idea es visitar todos los nodos, con cada nodo visitado una vez. Un nodo también se llama vértice. La búsqueda de profundidad primero puede estar en uno de los tres órdenes: pre-pedido, en pedido o posterior a. En este artículo, se ha utilizado el recorrido por pre-pedido.