把父子关系的二维数组转化为所有节点路径的二维数组

Question

如题：需要把有父子结构的二维数组，把这个树形结构的分支路径全部遍历出来，组成一个新的数组，最好用php语言，求大佬给个算法
原始数组为

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

转化后的数组为：

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

Answer 1

问题类似 树形数据结构上下反转
之前是 JS 的，反正有点空，翻写个 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); $i++)
    $tree->addNode($arrNode[$i]);

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