Sea G un grafo con n vértices y m aristas. ¿Cuál es el límite superior más ajustado en el tiempo de ejecución en la primera búsqueda en profundidad de G? Suponga que el gráfico se representa utilizando una array de adyacencia.
(A) O(n)
(B) O(m+n)
(C) O(n 2 )
(D) O(mn)
Respuesta: (C)
Explicación: Profundidad Primero La búsqueda de un gráfico requiere O(m+n ) momento en el que el gráfico se representa mediante una lista de adyacencia.
En la representación de array de adyacencia, el gráfico se representa como una array «nxn». Para hacer DFS, para cada vértice, recorremos la fila correspondiente a ese vértice para encontrar todos los vértices adyacentes (en la representación de lista de adyacencia, recorremos solo los vértices adyacentes del vértice). Por lo tanto, la complejidad del tiempo se convierte en O(n 2 )
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA