7.16. Análisis de la búsqueda en profundidad

El tiempo de ejecución general para la búsqueda en profundidad es el siguiente. Los ciclos en bep se ejecutan en \(O(V)\), sin contar lo que ocurre en visitabep, ya que se ejecutan una vez por cada vértice en el grafo. En visitabep el ciclo se ejecuta una vez por cada arista en la lista de adyacencia del vértice actual. Dado que visitabep sólo se llama recursivamente si el vértice es blanco, el ciclo se ejecutará a lo sumo una vez por cada arista en el grafo u \(O(E)\). Por lo tanto, el tiempo total para la búsqueda de profundidad es \(O (V + E)\).

You have attempted of activities on this page