获取依赖 Id 算法 [英] Get dependencies Ids Algorithm

问题描述

我遇到了这个问题，我想出了一个解决方案，但解决这个问题的最佳方法是什么?提前致谢.

I have this problem and I came out with a solution but what is the best way to solve this problem ? Thank you in advance.

给定一个字符串数组和一个任务数组，您需要返回一个包含任务和依赖项任务 ID 的排序数组.

Given an array of strings and an array of tasks you need to return a sorted array with tasks and dependencies tasks ids.

示例:

$inputs = ['A'];

$tasks = [
    ['id' => 1, 'type' => 'A', 'dependencies' => ['B']],
    ['id' => 2, 'type' => 'A', 'dependencies' => ['C']],
    ['id' => 3, 'type' => 'B', 'dependencies' => ['C']],
    ['id' => 4, 'type' => 'C', 'dependencies' => ['A', 'F']],
    ['id' => 5, 'type' => 'D', 'dependencies' => []],
    ['id' => 6, 'type' => 'D', 'dependencies' => ['F']],
    ['id' => 7, 'type' => 'E', 'dependencies' => ['D']],
    ['id' => 8, 'type' => 'F', 'dependencies' => []]
];

预期输出:

[1, 2, 3, 4, 8]

// Comments.
Id 1 of tasks['type'] = A  - [1]
Id 2 of tasks['type'] = A  - [1, 2]

Tasks id 1 has dependencies B then 
Id 3 of tasks['type'] = B  - [1, 2, 3]

Tasks id 3 has dependencies C then 
Id 4 of tasks['type'] = C  - [1, 2, 3, 4]

Tasks id 4 has dependencies A and F. Take F then 
Id 8 of tasks['type'] = F  - [1, 2, 3, 4, 8]

到目前为止，这是我构建的解决方案，但我想知道我是否走在正确的道路上.

So far this is the solution I built, but I would like to know if I am in the right path.

print_r(getId($inputs, $tasks));

function getId($inputs, $tasks){
    $id   = [];
    $deps = [];
    $values = [];
    $result = [];

    foreach($inputs as $input){
        foreach($tasks as $task){
            if ($task['type'] == $input){
                $result[$task['id']] = $task['id'];

                foreach($task['dependencies'] as $dependencies){
                    if($dependencies != $input){
                        $deps[] = $dependencies;
                    }
                }
            }
            else
            {
                $values[$task['type']]['id'][] = $task['id'];
                $values[$task['type']]['deps'] = $task['dependencies'];
            }
        }

        foreach($deps as $d){
            if(count($values[$d]['deps']) > 0)
            {
                foreach($values[$d]['deps'] as $nDeps)
                {
                    if($nDeps != $input){
                        $result[] = $values[$nDeps]['id'];
                    }
                }
            }
        }
    }

    foreach( $result as $res){
        if (is_array($res)){
            foreach( $res as $r){
                $id[] = $r;
            }
        }
        else {
            $id[] = $res;
        }
    }

    return array_unique($id);
}

推荐答案

完整片段:

<?php

function getId($inputs, $tasks){
   $types = [];
   $dependencies = [];
   foreach($tasks as $task){
       $types[$task['type']] =  $types[$task['type']] ?? [];
       $dependencies[$task['type']] = $dependencies[$task['type']] ?? [];
       $types[$task['type']][] = $task['id'];
       $dependencies[$task['type']] = array_unique(array_merge($dependencies[$task['type']],$task['dependencies']));
   }
   
   $res = [];
   $vis = [];
   foreach($inputs as $in){
       $queue = [];
       foreach($types[$in] as $id){
           if(!isset($vis[$id])){
               $vis[$id] = true;
               $queue[] = [$id , $in];
           }
       }
       while(count($queue) > 0){
           $d = array_shift($queue);
           $res[] = $d[0];
           $vis[$d[0]] = true;
           $type = $d[1];
           foreach($dependencies[$type] as $de_type){
               foreach($types[$de_type] as $id){
                   if(!isset($vis[$id])){
                       $vis[$id] = true;
                       $queue[] = [$id , $de_type];
                   }
               }
           }
       }
   }
   
   sort($res);
   return $res;
}

---

第 1 步:依赖关系和类型映射:

foreach($tasks as $task){
       $types[$task['type']] =  $types[$task['type']] ?? [];
       $dependencies[$task['type']] = $dependencies[$task['type']] ?? [];
       $types[$task['type']][] = $task['id'];
       $dependencies[$task['type']] = array_unique(array_merge($dependencies[$task['type']],$task['dependencies']));
}

• 根据类型收集所有类型的任务.这将有助于累积特定类型的所有任务.
• 还通过收集特定类型的所有依赖项来创建依赖项映射(关联数组).这涉及合并具有相同类型的所有任务的依赖项.

第 2 步:添加在 $inputs 中请求类型的任务

$queue = [];
foreach($types[$in] as $id){
   if(!isset($vis[$id])){
       $vis[$id] = true;
       $queue[] = [$id , $in];
   }
}

上面的代码片段只是在队列中添加节点/任务(仅限之前未添加的节点/任务)

The above snippet is to just add nodes/tasks in the queue(only those who haven't been added before)

第 3 步:遍历所有依赖项

while(count($queue) > 0){
     $d = array_shift($queue);
     $res[] = $d[0];
     $vis[$d[0]] = true;
     $type = $d[1];
     foreach($dependencies[$type] as $de_type){
         foreach($types[$de_type] as $id){
             if(!isset($vis[$id])){
                 $vis[$id] = true;
                 $queue[] = [$id , $de_type];
             }
         }
     }
 }

上面的代码片段一个一个循环遍历每个任务，将它们从队列中弹出.一旦任务被弹出，我们就会遍历它的所有类型依赖项.内循环循环那些在迭代中具有当前类型的任务.这样，整个依赖图被访问和附加.

Above snippet loops over each tasks one by one popping them out from the queue. Once a task is popped out, we loop over all it's type dependencies. The inner loop loops over those tasks which have the current type in iteration. This way, the whole dependency graph is visited and appended.

这篇关于获取依赖 Id 算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！