Algo检测形成路径的节点的顺序

Question

my problem is very simple, I'll try to explain with example. I have an array (unsorted) like so:

$nodes = [
  ['id' => 1, 'dest_id' => 2],
  ['id' => 2, 'dest_id' => 3],
  ['id' => 3, 'dest_id' => null],
  ['id' => 4, 'dest_id' => 5],
  ['id' => 5, 'dest_id' => null],
  ... etc
]

So basically nodes have an id and can have a destination which is the id of another node. Destination can be null. No node can have the same destination. I'm looking for an algorithm that could output this:

$paths = [[1, 2, 3], [4, 5]]

As you can see, in the output, the nodes that form a path are ordered so that node 2 which is destination of node 1 is placed after node 1.

Any help? Thank you.

Answer 1

So since there doesn't exist an answer to my question, I will answer it with what I came up with, in order to close it. But it is not a very good answer (sorry).

$raw_nodes = [
  ['id' => 1, 'dest_id' => 2],
  ['id' => 2, 'dest_id' => 3],
  ['id' => 3, 'dest_id' => null],
  ['id' => 4, 'dest_id' => 5],
  ['id' => 5, 'dest_id' => null]
];

$nodes = [];
// get the nodes in such a way that you can access them from their id
foreach($raw_nodes as $raw_node) {
  $nodes[$raw_node['id']] = [
    "id" => $raw_node['id'],
    "dest_id" => $raw_node['dest_id'],
    "parent_id" => null
  ];
}

// find the parent to each node
foreach($nodes as $node) {
  if ($node['dest_id'] && $nodes[$node['dest_id']]) {
    $nodes[$node['dest_id']]['parent_id'] = $node['id'];
  }
}

function buildPath($nodes, $node) {
  $path = [];
  if ($node['parent_id']) {
    $path = buildPath($nodes, $nodes[$node['parent_id']]);
  }
  array_push($path, $node['id']);
  return $path;
}

$paths = [];
// for every node without a destination,
// build its full path by recursive search starting from its own parent
foreach($nodes as $node) {
  if ($node['dest_id'] === null) {
    $path = buildPath($nodes, $node);
    array_push($paths, $path);
  }
}

Now $paths contains the output I want! Thanks everyone.