Encontrar nodos adyacentes

Un grafo es un conjunto de nodos y aristas que conectan esos nodos.

Los grafos pueden ser dirigidos o no dirigidos. En un grafo no dirigido, una arista funciona en ambas direcciones, como una calle de doble sentido. En un grafo dirigido, cada arista tiene su propia dirección, como una calle de un solo sentido. Dos nodos son adyacentes cuando una arista los conecta.

Una matriz de adyacencia representa un grafo con n nodos mediante una matriz n × n. El valor de la fila i y la columna j es 1 cuando los nodos i y j son adyacentes, y 0 en caso contrario. Para el grafo anterior, la matriz es:

let graph = [
  [0, 1, 0, 0],
  [1, 0, 1, 1],
  [0, 1, 0, 1],
  [0, 1, 1, 0]
]

La primera fila indica que el nodo 0 está conectado al nodo 1, pero no a sí mismo ni a los nodos 2 o 3. La segunda fila indica que el nodo 1 está conectado a los nodos 0, 2 y 3, pero no a sí mismo. La tercera fila indica que el nodo 2 está conectado a los nodos 1 y 3, mientras que la cuarta indica que el nodo 3 está conectado a los nodos 1 y 2. Como este grafo no es dirigido, la matriz es simétrica con respecto a su diagonal principal.

Devuelve si los dos nodos proporcionados son adyacentes en el grafo no dirigido representado por la matriz.

Ejemplos

let graph = [
  [0, 1, 0, 0],
  [1, 0, 1, 1],
  [0, 1, 0, 1],
  [0, 1, 1, 0]
]

isAdjacent(graph, 0, 1) // true
isAdjacent(graph, 0, 2) // false

let graph2 = [
  [0, 1, 0, 1, 1],
  [1, 0, 1, 0, 0],
  [0, 1, 0, 1, 0],
  [1, 0, 1, 0, 1],
  [1, 0, 0, 1, 0]
]

isAdjacent(graph2, 0, 3) // true
isAdjacent(graph2, 1, 4) // false

Notas

• La matriz es cuadrada, contiene únicamente 0 y 1, y representa un grafo no dirigido.
• Los índices de ambos nodos son válidos.
• Los grafos pueden contener hasta 25,000 nodos.
• Límite de tiempo: 100 milisegundos.