0
219
VistasDeterminar si ciertos nodos en un gráfico están conectados directamente
¿Cómo puedo determinar si los nodos seleccionados en un gráfico están conectados directamente?
Creo que necesito calcular rutas para cada nodo seleccionado a todos los demás nodos seleccionados. Luego, cuando tengo la ruta, tengo que verificar si la ruta contiene solo los nodos seleccionados.
En el código, todo lo que tengo es una noción de nodes y edges , así:
const nodes = [ { id: "A" }, { id: "B" }, { id: "C" }, { id: "D" }, { id: "E" }, { id: "F" }, ]; const edges = [ { target: "A", source: "B" }, { target: "B", source: "C" }, { target: "C", source: "D" }, { target: "D", source: "E" }, { target: "E", source: "F" }, ];Ejemplos:
Buena selección:
Mala selección:
¿Hay algún algoritmo para verificar eso? ¿Conoce algunos paquetes npm en el caso de JavaScript?
·
Juan Pablo Isaza
1 Respuestas
Responde la pregunta0
Solución posible
- Transforme el gráfico dirigido actual en un gráfico no dirigido (por lo que para cada par
(source, target),(target, source)también debe agregarse a losedges), ya que no estamos interesados en si A llega a B o B llega a A, sino estamos tratando de ver si están conectados - Ejecute un algoritmo transversal de gráficos ( Primera búsqueda en profundidad (DFS) o Búsqueda en amplitud (BFS) desde cualquier nodo seleccionado en el gráfico no dirigido que acaba de crear. Si se puede llegar a todos los nodos seleccionados, devuelva
true, de lo contrario, devuelvafalse
notas
- No importa desde qué
selected nodeejecute el DFS/BFS, siempre que el gráfico no esté dirigido. Por lo tanto, es importante ejecutar DFS/BFS solo una vez para mantener la complejidad de tiempoO(1). Ejecutar DFS/BFS desde todos los nodos seleccionados dará como resultado una complejidad de tiempoO(N), dondeN = # of nodes, y también proporcionaría un resultado correcto, pero introduciría recorridos de gráficos redundantes.
·
Juan Pablo Isaza
Denunciar
Responde la pregunta