php - 通过链接导航多个对象而不重复

Question

我正在尝试浏览一堆带有指向其他对象的链接的对象。我想从 1 的 id 开始并浏览每个对象。有些对象会循环回到以前的对象，所以我想确保每个对象只看一次，否则我会陷入无限循环。我还希望能够通过链接导航来判断哪些对象无法访问。我认为导航顺序无关紧要。

这是我可能会遇到的示例数据集(我的实际数据将来自数据库):

<?php

$obj_array = [] ;

$obj = new stdClass;
$obj->id = 1;
$obj->name = "Apple";
$obj->link = array(14, 5);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 3;
$obj->name = "Carrot";
$obj->link = array(1, 14, 3);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 4;
$obj->name = "Dill";
$obj->link = array(1, 5);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 5;
$obj->name = "Egg";
$obj->link = array(6);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 6;
$obj->name = "Fred";
$obj->link = array(7);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 7;
$obj->name = "Goat";
$obj->link = array(7, 8);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 8;
$obj->name = "Harry";
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 9;
$obj->name = "Igloo";
$obj->link = array(14, 5);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 10;
$obj->name = "Jason";
$obj->link = array(1, 5, 8);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 11;
$obj->name = "Klaus";
$obj->link = array(1, 5, 10);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 14;
$obj->name = "Banana";
$obj->link = array(3);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 15;
$obj->name = "Oyster1";
$obj->link = array(16);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 16;
$obj->name = "Oyster2";
$obj->link = array(15);
$obj_array[] = $obj;

我希望看到这样的东西(顺序无关紧要):

已处理:

Apple
Banana
Carrot
Egg
Fred
Goat
Harry

未链接:

Dill
Igloo
Jason
Klaus
Oyster1
Oyster2

如何创建一个循环来遍历这样的结构，尤其是当每个对象可以有多个链接时？

Answer 1

虽然@wizards answer工作，我觉得我想制作一个代码更清晰的版本。下面的版本返回一个包含链接元素和无行元素的对象，我相信它是如何工作的已经很清楚了。

我想这样工作的原因是为了能够扩展它以解决 future 的问题。比如“一个项目被链接了多少次”或“哪个链接最多”。它也可以很容易地适应以回答这些问题。

另一个好处是它使用尽可能有限的循环，这可以在大小增加时大大加快速度。

<?php
error_reporting(E_ALL);

$obj_array = [] ;

$obj = new stdClass;
$obj->id = 1;
$obj->name = "Apple";
$obj->link = array(14, 5);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 3;
$obj->name = "Carrot";
$obj->link = array(1, 14, 3);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 4;
$obj->name = "Dill";
$obj->link = array(1, 5);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 5;
$obj->name = "Egg";
$obj->link = array(6);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 6;
$obj->name = "Fred";
$obj->link = array(7);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 7;
$obj->name = "Goat";
$obj->link = array(7, 8);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 8;
$obj->name = "Harry";
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 9;
$obj->name = "Igloo";
$obj->link = array(14, 5);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 10;
$obj->name = "Jason";
$obj->link = array(1, 5, 8);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 11;
$obj->name = "Klaus";
$obj->link = array(1, 5, 10);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 14;
$obj->name = "Banana";
$obj->link = array(3);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 15;
$obj->name = "Oyster1";
$obj->link = array(16);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 16;
$obj->name = "Oyster2";
$obj->link = array(15);
$obj_array[] = $obj;


/*
 * CALL
 */

$parser = new ObjectLinker($obj_array, 1);

//dump found
//decode/encode to only show public values
print_r(json_decode(json_encode($parser)));


/*
 * ACTUAL CODE
 */


class ObjectLinker
{
    private $_array;
    private $_start;

    public $LinkedElements = array();
    public $UnLinkedElements = array();

    final public function __construct($ar, $start)
    {
        $this->_array = $ar;
        $this->_start = $start;

        $this->getElementsArray();
        $this->findLinked($this->_start);
    }

    final private function getElementsArray()
    {       
            //since each Id is unique, i'm using the ID as the key in the array. this will allow faster access
            //Ofcourse it would be better if you would create the array like this in the first place, then you can skip this step
            foreach($this->_array as $obj) {
                if (!is_null($obj) && property_exists($obj, 'id')) {
                    //I add everything to the unlinked elements. We will remove the linked once, to have once less loop
                    $this->UnLinkedElements[$obj->id] = $obj;
                }
            }
    }


    final private function findLinked($id)
    {
        //If the key is not in the array, it's already loaded
        if (!array_key_exists($id, $this->UnLinkedElements)) {
            return;
        }

        //get obj
        //Because of the getElementsArray() step, I'm already sure the object exists.
        //If you change the input array, you might want to check for invalid obj
        $obj = $this->UnLinkedElements[$id];

        //add to linked
        $this->LinkedElements[$id] = $obj;

        //remove from unlinked
        unset($this->UnLinkedElements[$id]);

        //no links
        if (!property_exists($obj, 'link')) {
            return;
        }

        $links = $obj->link;

        //Invalid links
        if (!is_array($links)) {
            return;
        }

        //check links
        foreach($links as $link) {
            $this->findLinked($link);
        }
    }

}

?>

输出:

stdClass Object
(
  [LinkedElements] => stdClass Object
    (
      [1] => stdClass Object
        (
          [id] => 1
          [name] => Apple
          [link] => Array
            (
              [0] => 14
              [1] => 5
            )

        )

      [14] => stdClass Object
        (
          [id] => 14
          [name] => Banana
          [link] => Array
            (
              [0] => 3
            )

        )

      [3] => stdClass Object
        (
          [id] => 3
          [name] => Carrot
          [link] => Array
            (
              [0] => 1
              [1] => 14
              [2] => 3
            )

        )

      [5] => stdClass Object
        (
          [id] => 5
          [name] => Egg
          [link] => Array
            (
              [0] => 6
            )

        )

      [6] => stdClass Object
        (
          [id] => 6
          [name] => Fred
          [link] => Array
            (
              [0] => 7
            )

        )

      [7] => stdClass Object
        (
          [id] => 7
          [name] => Goat
          [link] => Array
            (
              [0] => 7
              [1] => 8
            )

        )

      [8] => stdClass Object
        (
          [id] => 8
          [name] => Harry
        )

    )

  [UnLinkedElements] => stdClass Object
    (
      [4] => stdClass Object
        (
          [id] => 4
          [name] => Dill
          [link] => Array
            (
              [0] => 1
              [1] => 5
            )

        )

      [9] => stdClass Object
        (
          [id] => 9
          [name] => Igloo
          [link] => Array
            (
              [0] => 14
              [1] => 5
            )

        )

      [10] => stdClass Object
        (
          [id] => 10
          [name] => Jason
          [link] => Array
            (
              [0] => 1
              [1] => 5
              [2] => 8
            )

        )

      [11] => stdClass Object
        (
          [id] => 11
          [name] => Klaus
          [link] => Array
            (
              [0] => 1
              [1] => 5
              [2] => 10
            )

        )

      [15] => stdClass Object
        (
          [id] => 15
          [name] => Oyster1
          [link] => Array
            (
              [0] => 16
            )

        )

      [16] => stdClass Object
        (
          [id] => 16
          [name] => Oyster2
          [link] => Array
            (
              [0] => 15
            )

        )

    )

)