Java算法题：输出两条连通路径之一

Question

/**
* The Problem:
*
* We have a list of tasks. Each task can depend on other tasks. 
* For example if task A depends on task B then B should run before A.
* 
* Implement the "getTaskWithDependencies" method such that it returns a list of task names in the correct order.
* 
* For example if I want to execute task "application A", the method should return a list with "storage,mongo,application A".
*
* List of Tasks:
*
*   - name: application A
*     dependsOn:
*       - mongo
*
*   - name: storage
*
*   - name: mongo
*     dependsOn:
*       - storage
*
*   - name: memcache
*
*   - name: application B
*     dependsOn:
*       - memcache
*
* The Java program is expected to be executed succesfully.
*/
public class Solution { 
 private static List<String> getTaskWithDependencies(List<Task> tasks, String dependsOn) {
   // TODO: please implement logic here
   
 }
  
  

 @Test
 public void testGetTaskDependenciesForApplicationA() {
   Assert.assertEquals(
     Arrays.asList(
       "storage",
       "mongo",
       "application A"
     ),
     getTaskWithDependencies(TaskList.getTasks(), "application A")
   );
 }
}

/**
* Definition of a Task
*/
class Task {
 private final String name;
 private final List<String> dependsOn;

 Task(String name) {
   this(name, new ArrayList<>());
 }

 Task(String name, List<String> dependsOn) {
   this.name = name;
   this.dependsOn = dependsOn;
 }

 public String getName() { return this.name; }
 public List<String> getDependsOn() { return this.dependsOn; }
}

class TaskList {
 public static List<Task> getTasks() {
   List<Task> tasks = new ArrayList<>();

   tasks.add(new Task("application A", Arrays.asList("mongo")));
   tasks.add(new Task("storage"));
   tasks.add(new Task("mongo", Arrays.asList("storage")));
   tasks.add(new Task("memcache"));
   tasks.add(new Task("application B", Arrays.asList("memcache")));

   return tasks;
 }
}

大意是给出一些方向关系，包括： application a -> mongodb -> storage 这是一个连接路径 application b -> memcache 这是一条连接路径，既然指定了应用程序A，就需要在其所在的地方输出连接的路径。我的方法是使用拓扑排序将这 5 个点排序在一起。结果将是 b->memcache->a->mongo->storage。我的问题是：如何只输出一条连接的路径而忽略另一条？我看Leetcode里面没有类似的问题，所以不知道。代码我自己会写，能说说思路就好了

Answer 1

您可以使用递归来解决您的问题。

从方法传入的list of tasks中，通过task的name过滤，取出dependsOn的那个。如果 task 有自己的 dependsOn 列表，遍历列表并调用递归函数，将相同的 list of tasks 和迭代字符串作为 newDependsOn 传递给它。将您从递归函数获得的所有结果附加到逗号分隔的 StringBuilder 中，并使用 "," 将用作生成最终列表的分隔符。

完成所有这些迭代后，将初始 dependsOn 附加到 StringBuilder。最后，return the StrinBuilder.toStirng().split(",") as list得到最终结果。

注意： 我已经编写了代码，但根据您的要求，我没有将其添加到此答案中。如果您需要进一步的帮助，请在评论中询问我，如果需要我会提供代码。

更新

根据您的要求，我添加了以下代码：

private static List<String> getTaskWithDependencies(List<Task> tasks, String dependsOn) {
    StringBuilder resultString = new StringBuilder();
    Task task = tasks.stream().filter(x -> dependsOn.equalsIgnoreCase(x.getName())).findAny().get();
    if (task.getDependsOn() != null && !task.getDependsOn().isEmpty()) {
        for (String newDependsOn : task.getDependsOn()) {
            List<String> res = getTaskWithDependencies(tasks, newDependsOn);
            for (String ele : res) {
                resultString.append(ele).append(",");
            }
        }
    }
    resultString.append(dependsOn);
    return Arrays.asList(resultString.toString().split(","));
}

现在，如果您运行使用以下代码：

public static void main(String[] args) {
    System.out.println(getTaskWithDependencies(TaskList.getTasks(), "application A"));
}

您将得到以下输出：

[storage, mongo, application A]

Java算法题：输出两条连通路径之一

Java algorithm problem: output one of the two connected paths

java

algorithm

graph-algorithm

union-find