Dado un grafo no dirigido con N Nodes y dos vértices S & T , la tarea es comprobar si existe un ciclo entre estos dos vértices (y devolverlo) o no, de forma que ningún otro Node excepto S y T aparezca más de una vez en ese ciclo.
Ejemplos :
Entrada : N = 7, bordes[][] = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 2}, { 2, 6}, {6, 0}}, S = 0, T = 4
Salida : No existe un ciclo simple de S a T
Explicación : No existe un ciclo simple de S a T,
porque el Node 2 aparece dos veces, en el único ciclo que existe entre 0 y 4Entrada : N = 7, bordes[][] = {{0, 1}, {1, 2}, {1, 6}, {2, 3}, {3, 4}, {4, 5}, { 5, 2}, {2, 6}, {6, 0}}, S = 0, T = 4
Salida : 0->1->3->4->5->2->6->0
Explicación : el ciclo no repite ningún Node (excepto 0)
Enfoque ingenuo: El enfoque ingenuo del problema se analiza en el Conjunto 1 de este problema.
Enfoque eficiente : en el enfoque ingenuo se verifican todos los caminos posibles. La idea de este enfoque es similar al algoritmo de Ford Fulkerson con la implementación de Edmonds-Karp , pero con solo 2 BFS . Siga los pasos a continuación para resolver el problema
- Primero, haga un gráfico dirigido duplicando cada Node (excepto S y T ) en receptor y remitente :
- Si el gráfico original tenía el borde: {a, b}, el nuevo gráfico tendrá {sender_a, receiver_b}
- El único Node que apunta a un remitente es su receptor , por lo que el único borde que termina en sender_v es: { receiver_v, sender_v }
- El receptor solo apunta a su remitente, por lo que la lista de adyacencia de receiver_v es: [sender_v]
- Ejecute un BFS para encontrar una ruta de S a T y memorice la ruta de regreso (usando una array predecesora).
- Invierta los bordes en la ruta encontrada , este paso es similar a la actualización de una ruta de aumento en Ford Fulkerson.
- Mientras invierte memorizar el flujo de un Node a otro en el camino
- Entonces, si el Node anterior de cur es pred, entonces flow[cur] = pred
- Finalmente, memoriza el último Node (antes del Node t), llamémoslo: first_node (porque es el primer Node, después de t, del flow_path), first_node = flow[t]
- Ejecute un BFS nuevamente para encontrar la segunda ruta y memorice la ruta de regreso (usando una array predecesora).
- Memoriza de nuevo el flujo del segundo camino:
- Sólo marque el flujo si no hubo un flujo anterior en sentido contrario, de esta forma se descartarán dos flujos opuestos. Por lo tanto, si fluir[pred] == cur no hacer: fluir[cur] = pred
- Si el Node anterior de cur está pred en una ruta, entonces flow[cur] = pred
- Finalmente, une los caminos:
- Atraviese ambas rutas por el flujo, una ruta que comienza en first_node y la otra flow[t]
- Como tenemos 2 caminos de t a s, invirtiendo uno de ellos tendremos un camino de s a t y otro de t a s.
- Recorra un camino de s a t y el otro de t a s.
Todo este trabajo de duplicación del gráfico y registro del flujo se realiza para garantizar que el mismo Node no se atraviese dos veces.
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python program for the above approach
# Auxiliary data struct for the BFS:
class Node:
def __init__(self, val):
self.val = val
self.next = None
class queue:
def __init__(self):
self.head = None
self.tail = None
def empty(self):
return self.head == None
def push(self, val):
if self.head is None:
self.head = Node(val)
self.tail = self.head
else:
self.tail.next = Node(val)
self.tail = self.tail.next
def pop(self):
returned = self.head.val
self.head = self.head.next
return returned
# BFS to find the paths
def bfs(graph, s, t):
# Number of nodes in original graph
N = len(graph)//2
Q = queue()
Q.push(s)
predecessor = list(-1 for _ in range(2 * N))
predecessor[s] = s
while not Q.empty():
cur = Q.pop()
# Add neighbors to the queue
for neighbour in graph[cur]:
# If we reach node we found the path
if neighbour == t or neighbour == t + N:
predecessor[t] = cur
predecessor[t + N] = cur
return predecessor
# Not seen
if predecessor[neighbour] == -1:
Q.push(neighbour)
predecessor[neighbour] = cur
return None
# Invert the path and register flow
def invert_path(graph, predecessor, flow, s, t):
N = len(graph)//2
cur = t
while cur != s:
pred = predecessor[cur]
if flow[pred] != cur:
flow[cur] = pred
# Reverse edge
graph[cur].append(pred)
graph[pred].remove(cur)
cur = pred
# Node S and T are not duplicated
# so we don't reverse the edge s->(s + N)
# because it shouldn't exist
graph[s].append(s + N)
return flow
# Return the path by the flow
def flow_path(flow, first_node, s):
path = []
cur = first_node
while cur != s:
path.append(cur)
cur = flow[cur]
return path
# Function to get the cyclle with 2 nodes
def cycleWith2Nodes(graph, s = 0, t = 1):
# Number of nodes in the graph
N = len(graph)
# Duplicate nodes:
# Adjacency list of sender nodes
graph += list(graph[node] for node in range(N))
# Adjacency list of receiver nodes
graph[:N] = list([node + N] for node in range(N))
# print('duplicated graph:', graph, '\n')
# Find a path from s to t
predecessor = bfs(graph, s, t)
if predecessor is not None:
# List to memorize the flow
# flow from node v is:
# flow[v], which gives the node who
# receives the flow
flow = list(-1 for _ in range(2 * N))
flow = invert_path(graph, predecessor, flow, s, t)
first_node = flow[t]
else:
print("No cycle")
return
# Find second path
predecessor = bfs(graph, s, t)
if predecessor is not None:
flow = invert_path(graph, predecessor, flow, s, t)
# Combine both paths:
# From T to S
path1 = flow_path(flow, first_node, s)
path2 = flow_path(flow, flow[t], s)
# Reverse the second path
# so we will have another path
# but from s to t
path2.reverse()
simpleCycle = [s]+path2+[t]+path1+[s]
print(simpleCycle[::2])
else:
print("No cycle")
# Driver Code
if __name__ == "__main__":
graph = [
[1, 6], # 0
[0, 2, 3], # 1
[1, 3, 5, 6], # 2
[1, 2, 4], # 3
[3, 5], # 4
[2, 4], # 5
[0, 2], # 6
]
cycleWith2Nodes(graph, s = 0, t = 4)
[0, 6, 2, 5, 4, 3, 1, 0]
Análisis de complejidad: a continuación se muestra la complejidad de cada función.
- Crear gráfico duplicado: O(V+E)
- 2 BFS: O(V+E)
- 2 inversiones (flujo de registro): O (tamaño de ruta) <= O (V + E)
- Vuelva a crear las rutas desde la array de flujo: O (tamaño de la ruta) <= O (V + E)
- Invertir una ruta: O (tamaño de la ruta) <= O (V + E)
Complejidad de tiempo : O(V+E)
Espacio auxiliar : O(N*N), donde N es el recuento de vértices en el gráfico.