# 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条回答

• 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.

点赞 评论 复制链接分享