Dado un gráfico ponderado no dirigido conectado en forma de array 2D donde cada fila es del tipo [Node inicial, Node final, peso] que describe un borde, y también dos números enteros (A, B) . Devuelve si el borde formado entre (A, B) es parte de cualquiera de los árboles de expansión mínimos (MST) del gráfico.
Árbol de expansión mínimo (MST): este es un subgráfico especial del gráfico, de modo que todos y cada uno de los vértices están conectados y la suma total de los pesos de los bordes de este subgráfico es la mínima posible. Un gráfico puede tener varios árboles de expansión mínimos.
Ejemplos:
Entrada: gráfico = [[0 ,1, 20] , [0 , 2 , 5] , [ 0, 3, 10 ] , [ 2, 3, 10]], A = 2, B = 3 Salida
: Verdadero
Explicación : Se pueden generar 2 árboles de expansión mínimos que tendrán un peso de 35. Las conexiones de los árboles son
1: [(0,1) , (0,3) , (0,2)] => 20 + 10 + 5 = 35
2do: [ ( 0 , 1) , ( 0 , 2 ) , ( 2 , 3) ] => 20 + 5 + 10 = 35 Como puede
verse, la arista (2, 3) está presente en el segundo MST.El gráfico se muestra en la imagen:
Entrada : gráfico = [[0 ,1, 20] , [0 , 2 , 5] , [ 0, 3, 10 ] , [ 2, 3, 20]], A = 2, B = 3 Salida
: Falso
Explicación : Solo se puede generar 1 árbol de expansión mínimo con un peso de 35,
pero el borde (2, 3) no está incluido.
[(0,1) , (0,3) , (0,2)] => 20 + 10 + 5 = 35El gráfico se da en la imagen.
Enfoque : el algoritmo de Kruskal y el algoritmo de Prim son los dos algoritmos más utilizados que se pueden usar para encontrar el MST de cualquier gráfico. En este artículo, la solución se basa en el algoritmo de Kruskal. Siga los pasos que se mencionan a continuación para resolver el problema utilizando este enfoque:
- Encuentre el costo mínimo del árbol de expansión de todo el gráfico, utilizando el algoritmo de Kruskal .
- A medida que se verifica la inclusión del borde (A, B) en el MST, incluya este borde primero en el árbol de expansión mínimo y luego incluya otros bordes posteriormente.
- Finalmente, verifique si el costo es el mismo para ambos árboles de expansión, incluido el borde (A, B) y el peso calculado del MST.
- Si el costo es el mismo , entonces el borde (A, B) es parte de algún MST del gráfico; de lo contrario, no lo es.
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python program to implement above approach
# Class to implement disjoint set union
class dsu:
def __init__(self):
self.parent = {}
self.rank = {}
# Function to find parent of a node
def find(self, x):
if (x not in self.parent):
self.rank[x] = 1
self.parent[x] = x
if (self.parent[x] != x):
self.parent[x] = \
self.find(self.parent[x])
return (self.parent[x])
# Function to perform union
def union(self, u, v):
p1 = self.find(u)
p2 = self.find(v)
# If do not belong to same set
if (p1 != p2):
if (self.rank[p1]
< self.rank[p2]):
self.parent[p1] = p2
elif(self.rank[p1]
> self.rank[p1]):
self.parent[p2] = p1
else:
self.parent[p2] = p1
self.rank[p1] += 1
return (True)
# Belong to same set
else:
return False
class Solution:
# Find the MST weight
def kruskal(self, include, edges, a, b):
obj = dsu()
total = 0
# If include is True , then include
# edge (a,b) first
if (include):
for (u, v, wt) in edges:
# As graph is undirected so
# (a,b) or (b,a) is same
# If found break the for loop
if (u, v) == (a, b) or \
(b, a) == (u, v):
val = obj.union(a, b)
total += wt
break
# Go on adding edge to the disjoint set
for (u, v, wt) in edges:
# Nodes (u,v) not belong to
# same set include it
if (obj.union(u, v)):
total += wt
# Finally return total weight of MST
return (total)
# Function to find if edge (a, b)
# is part of any MST
def solve(self, edges, a, b):
# Sort edges according to weight
# in ascending order
edges.sort(key=lambda it: it[2])
# Not included edge (a,b)
overall = self.kruskal(False,
edges, a, b)
# Find mst with edge (a,b) included
inc = self.kruskal(True,
edges, a, b)
# Finally return True if same
# else False
if (inc == overall):
return (True)
else:
return (False)
# Driver code
if __name__ == "__main__":
obj = Solution()
graph = [[0, 1, 20], [0, 2, 5],
[0, 3, 10], [2, 3, 10]]
A, B = 2, 3
val = obj.solve(graph, A, B)
if (val):
print("True")
else:
print("False")
True
Complejidad del Tiempo : O(E * logV). donde E es el número de aristas y V es el número de vértices.
Espacio Auxiliar : O(V)