查找许多列表之间的依赖关系

Question

我有一个包含以下列表的整数列表List<List<Integer>> dependency = new ArrayList<List<Integer>>()列表：

[0, 0]
[1, 0]
[2, 1]
[3, 1]
[4, 3]
[5, 1]
[6, 4]
[8, 5]
[9, 3]
[10, 2]
[11, 6]

每个列表由ID和其依赖于另一个列表组成。例如，可以读取[2,1]，ID为2取决于ID = 1（[1,0]）列表。

我想知道类似于以下示例的列表之间的依赖关系：

10 < - 2 < - 1 < - 0（这可以读作：ID = 10的列表取决于ID = 2的列表，取决于ID = 1的列表，取决于ID列表= 0）

8 < - 2 < - 1 < - 0（ID = 8的列表取决于ID = 5的列表，取决于ID = 1的列表，取决于ID列表= 0）

为此，我做了以下事情：

    for(List<Integer> x: dependency) {
        x1 = x.get(0);
        x2 = x.get(1);

        int x3 = dependency.get(x2).get(1);
        System.out.println(x1 + " -- " + x2 + " -- " + x3);
    }

但这不适用于ID = 6的情况，因为它有更多的依赖性：6 < - 4 < - 3 < - 1 < - 0

此外，在11：11 < - 6 < - 4 < - 3 < - 1 < - 0的情况下

如何解决问题，以便我可以获得尽可能多的依赖项？

Answer 1

看起来像递归使用的经典案例给我。我曾经使用以下代码：

import java.util.ArrayList;
import java.util.List;

public class Listofintegerlists {

    public static void init(List<List<Integer>> list) {
    ...
    }

    public static void main(String[] args) {
        List<List<Integer>> dependency = new ArrayList<List<Integer>>();
        init(dependency);
        System.out.println(dependency);
        printDependenciesAux(dependency);
    }

    public static void printDependenciesAux(List<List<Integer>> dependency) {
        for (List<Integer> x : dependency) {
            System.out.print("Printing dependencies for ID = " + x.get(0) + ": ");
            printDepedencies(x, dependency);
            System.out.println();
        }
    }
    public static void printDepedencies(List<Integer> curList, List<List<Integer>> dependency) {
        int curID = curList.get(0);
        int nextID = curList.get(1);

        System.out.print(curID + " <-- ");
        if (nextID == 0) {
            System.out.print("0");
            return;
        }
        List<Integer> nextList = getNextList(nextID, dependency);
        printDepedencies(nextList, dependency);
    }

    private static List<Integer> getNextList(int nextID, List<List<Integer>> dependency) {
        for (List<Integer> x : dependency) {
            if (x.get(0) == nextID) {
                return x;
            }
        }
        return null;
    }
}

输出：

[[0, 0], [1, 0], [2, 1], [3, 1], [4, 3], [5, 1], [6, 4], [8, 5], [9, 3], [10, 2], [11, 6]]
Printing dependencies for ID = 0: 0 <-- 0
Printing dependencies for ID = 1: 1 <-- 0
Printing dependencies for ID = 2: 2 <-- 1 <-- 0
Printing dependencies for ID = 3: 3 <-- 1 <-- 0
Printing dependencies for ID = 4: 4 <-- 3 <-- 1 <-- 0
Printing dependencies for ID = 5: 5 <-- 1 <-- 0
Printing dependencies for ID = 6: 6 <-- 4 <-- 3 <-- 1 <-- 0
Printing dependencies for ID = 8: 8 <-- 5 <-- 1 <-- 0
Printing dependencies for ID = 9: 9 <-- 3 <-- 1 <-- 0
Printing dependencies for ID = 10: 10 <-- 2 <-- 1 <-- 0
Printing dependencies for ID = 11: 11 <-- 6 <-- 4 <-- 3 <-- 1 <-- 0

Answer 2

假设没有像[1,2]和[2,1]之类的相互依赖关系创建地图，递归地导航地图可以是一个选项：

public static void main(String[] args)  {
    List<List<Integer>> dependency = new ArrayList<>(); // fill your list
    //create a map
    Map<Integer,Integer> depMap = dependency.stream().collect(Collectors.toMap(k->k.get(0), k->k.get(1)));
    //print dependencies using the recursive method provided below 
    System.out.println(getdependencies(depMap,10)); 
}

public static String getdependencies(Map<Integer,Integer> map, Integer key) {
    if(map.containsKey(key)){
        if (map.get(key) == 0) {
            return key + " <- " + map.get(key).toString();
        }
        return key + " <- " + getdependencies(map, map.get(key));
    }
    return "Key: "+key+" not found";
}