dongzhazhuo0572
dongzhazhuo0572
2018-04-16 15:36

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

已采纳

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.

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

1条回答

  • doulei8861 doulei8861 3年前

    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.

    点赞 评论 复制链接分享