¿Cuál es el mejor tiempo de ejecución de un algoritmo que verifica la conexión entre dos conjuntos de nodos en un gráfico?

Encontrar la intersección de ambos conjuntos de nodos es trivial.

Para la parte de la ruta, creo que un simple BFS o DFS será suficiente. Para verificar si hay una ruta entre al menos un par de nodos n1, n2 donde n1 está en el primer conjunto y n2 está en el segundo conjunto, haga una primera búsqueda en profundidad desde un nodo (digamos x) en el primer conjunto, si Si llega a un nodo (digamos y) en el segundo conjunto, definitivamente puede decir que existe tal ruta. El tiempo de ejecución es solo el costo de hacer la primera búsqueda en profundidad en el gráfico, O (V + E). Breadth First Search también se puede usar en lugar de Depth First Search. Pero creo que DFS funcionará mejor.

Psuedocódigo del algoritmo:

  procedimiento dfs (fuente del nodo):
	 visitado [fuente] = 1
	 si fuente en nodeset2:
    	 volver verdadero
	 para todos los nodos adyacentes v que visitaron [v] = 0:
    	 si dfs (v):
	 volver verdadero
	 visitado [fuente] = 2
	 falso retorno

  procedimiento isConnected (nodeset1, nodeset2):
		 para el nodo en el conjunto de nodos1:
			 visitado [nodo] = 0
		 if setIntersection (nodeset1, nodeset2):
			 volver verdadero
		 para el nodo en el conjunto de nodos1:
			 si no se visita [nodo] y dfs (nodo):
				 volver verdadero
		 falso retorno

No necesita verificar las rutas entre todos los pares de nodos. Simplemente puede verificar si puede llegar a cualquier nodo en n2, comenzando desde cualquier nodo en n1.

Para hacer eso, ejecute una Búsqueda de aliento primero (BFS) en un gráfico que consta de ambos conjuntos de nodos y márquelo a medida que los visita. Debe iniciar BFS desde cada nodo n1 no visitado y detener el algoritmo cada vez que visite cualquier nodo en n2.

En el peor de los casos, debe visitar todos los nodos y seguir todos los bordes. Por lo tanto, la complejidad temporal del algoritmo es O (V + E), mientras que la complejidad espacial es O (V + E)