Si se usa el algoritmo de Kruskal para encontrar un árbol de expansión mínimo de un grafo ponderado G con n vértices y m aristas y los pesos de las aristas ya están dados en una lista ordenada, entonces, ¿cuál será la complejidad de tiempo para calcular el árbol de expansión de costo mínimo dado que las operaciones de unión y búsqueda toman amortizado O(1) ?
(A) O(m registro)
(B) O(n)
(C) O(m)
(D) O(n logm)
Respuesta: (C)
Explicación:
O(m) ya que ya se le han dado los pesos de los bordes en orden ordenado. Solo tiene que elegir los bordes en orden creciente y agregarlo al conjunto de expansión actual si su adición no da como resultado un ciclo; de lo contrario, deséchelo.
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