Preguntas sobre el posible algoritmo gráfico de relación más rápido en PHP

Puede ver estas relaciones como paquetes de Composer. Cada paquete tiene su propia dependencia.

Como por ejemplo,

$relation1 = [1, 2];
$relation2 = [2, 3];

• En el ejemplo anterior, puede decir que el paquete 1 depende del paquete 2 y el paquete 2 depende del paquete 3.

• Del mismo modo, tenemos que encontrar todos los componentes conectados. La relación entre 2 paquetes no necesariamente tiene que ser reflexiva, lo que significa que el paquete A depende del paquete B no necesariamente significa que el paquete B depende del paquete { {X3}}.

• Pero para el alcance de este problema, podemos hacer que la relación sea reflexiva para obtener los componentes conectados a través de {{ X0}}. Si lo desea, puede adaptarse a una idea no reflexiva utilizando union find by path compression para fusionar valores con padres singulares, pero en mi respuesta, me quedaría con DFS.

Su entrada:

$relation1 = [1, 2];
$relation2 = [2, 3];
$relation3 = [4, 5];
$relation4 = [6, 7];
$relation5 = [7, 2];

Para la entrada anterior, la lista de adyacencia se vería así:

1 => 2
2 => 1,3,7
3 => 2
4 => 5
5 => 4
6 => 7
7 => 6,2

Fragmento:

function getConnectedComponents($relations,$total_nodes){
    $result = [];
    $nodes = [];
    $visited = [];

    for($i=1;$i<=$total_nodes;++$i){
        $nodes[$i] = [];
        $visited[$i] = false;
    }

    foreach($relations as $relation){
        $nodes[$relation[0]][] = $relation[1];
        $nodes[$relation[1]][] = $relation[0];
    }

    for($i=1;$i<=$total_nodes;++$i){
        if(!$visited[$i]){
            $temp = [];
            dfs($nodes,$i,$visited,$temp);
            $result[] = $temp;
        }
    }

    return $result;
}

function dfs($nodes,$node,&$visited,&$temp){
    if($visited[$node]) return;
    $visited[$node] = true;
    $temp[] = $node;
    foreach($nodes[$node] as $child_node){
        dfs($nodes,$child_node,$visited,$temp);
    }
}

Demostración: https://3v4l.org/JWAF6

En el algoritmo anterior, construimos la lista de adyacencia y hacemos una búsqueda profunda en primer lugar en cada nodo. Marcamos los nodos como visitados en el camino para asegurarnos de que no estamos visitando algo que ya procesamos.