Cómo 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. La entrada 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:

$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 se conecta con el nodo 1, pero no consigo mismo ni con los nodos 2 o 3. La segunda fila indica que el nodo 1 se conecta con los nodos 0, 2 y 3, pero no consigo mismo. La tercera fila indica que el nodo 2 se conecta con los nodos 1 y 3, mientras que la cuarta indica que el nodo 3 se conecta con los nodos 1 y 2. Como este grafo no es dirigido, la matriz es simétrica respecto de su diagonal principal.

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

Ejemplos

$graph = [
  [0, 1, 0, 0],
  [1, 0, 1, 1],
  [0, 1, 0, 1],
  [0, 1, 1, 0]
];

is_adjacent($graph, 0, 1); // true
is_adjacent($graph, 0, 2); // false

$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]
];

is_adjacent($graph2, 0, 3); // true
is_adjacent($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.