Convert a two-dimensional array of parent-child relationships into a two-dimensional array of all node paths

such as the title: it is necessary to traverse all the branch paths of the tree structure from a two-dimensional array with a parent-child structure to form a new array. It is best to use php language to find an algorithm
the original array is

$array = [
        ["ID"=>"A","SD"=>"B"],
        ["ID"=>"A","SD"=>"C"],
        ["ID"=>"A","SD"=>"D"],
        ["ID"=>"B","SD"=>"E"],
        ["ID"=>"B","SD"=>"F"],
        ["ID"=>"E","SD"=>"G"],
        ["ID"=>"C","SD"=>"H"],
        ["ID"=>"C","SD"=>"I"]
        
    ];

the converted array is:

$targe = [
    ["B","E","G"],
    ["B","F"],
    ["C","H"],
    ["C","I"],
    ["D"]
]

Php tree-structure data-structure algorithm

Mar.19,2022

The

problem is similar to the tree data structure reversing up and down
before it was JS, anyway, it's a little empty, so rewrite the

of PHP.

<?php

class Node
{
    /** @var string */
    public $id;

    /** @var self */
    public $prev;

    /** @var self[] */
    public $next;

    /**
     *
     */
    public function __construct()
    {
        $this->prev = null;
        $this->next = [];
    }

    /**
     * @return array
     */
    public function findAllPath()
    {
        $arrPath = [];

        if(count($this->next) <= 0)
        {
            $arrPath[] = [$this->id];
        }
        else
        {
            foreach($this->next as $node)
            {
                $arr = $node->findAllPath();
                foreach($arr as $path)
                {
                    array_unshift($path, $this->id);
                    $arrPath[] = $path;
                }
            }
        }

        return $arrPath;
    }
}

class Tree
{
    const ROOT_ID = '';

    /** @var Node[] */
    public $mapRoot;

    /** @var Node[] */
    public $mapNode;

    /**
     *
     */
    public function __construct()
    {
        $this->mapRoot = [];
        $this->mapNode = [];
    }

    /**
     * @param string $id
     * @param bool   $create
     *
     * @return Node|null
     */
    protected function getNode($id, $create=false)
    {
        if(array_key_exists($id, $this->mapNode) === true)
            return $this->mapNode[$id];

        if($create === false)
            return null;

        $node = new Node();
        $node->id   = $id;
        $node->prev = null;
        $node->next = [];

        $this->mapNode[$id] = $node;

        return $node;
    }

    /**
     * @param array $data
     */
    public function addNode($data)
    {
        $nodeThis = $this->getNode($data['SD'], true);
        $nodePrev = $this->getNode($data['ID'], true);

        $nodeThis->prev   = $nodePrev;
        $nodePrev->next[] = $nodeThis;

        if($nodePrev !== null && array_key_exists($nodePrev->id, $this->mapRoot) === false && $nodePrev->prev === null)
            $this->mapRoot[$nodePrev->id] = $nodePrev;

        if(array_key_exists($nodeThis->id, $this->mapRoot) === true && $nodeThis->prev !== null)
            unset($this->mapRoot[$nodeThis->id]);
    }

    /**
     * @return array
     */
    public function findAllPath()
    {
        $arrPath = [];

        foreach($this->mapRoot as $id => $node)
        {
            $arr = $node->findAllPath();
            foreach($arr as $path)
            {
                $arrPath[] = $path;
            }
        }

        return $arrPath;
    }
}

$arrNode = [
    ['ID'=>'A','SD'=>'B'],
    ['ID'=>'A','SD'=>'C'],
    ['ID'=>'A','SD'=>'D'],
    ['ID'=>'B','SD'=>'E'],
    ['ID'=>'B','SD'=>'F'],
    ['ID'=>'E','SD'=>'G'],
    ['ID'=>'C','SD'=>'H'],
    ['ID'=>'C','SD'=>'I']
];

$tree = new Tree();
for($i=0; $i<count($arrNode); $iPP)
    $tree->addNode($arrNode[$i]);

$arrPath = $tree->findAllPath();
foreach($arrPath as $path)
{
    echo(json_encode($path));
    echo('<br />');
}

Previous: How to modify a value in a multidimensional array under data under vue?

Next: How to optimize the performance of mobile terminal length list? Drop-down loading always fills the page with data. What if there are too many dom pages that are too stuck?