你如何在 Java 中找到这棵树的路径数？

Question

我正在尝试查找以这种方式表示的树的路径数：

1 4
2 4
3
4
-1

-1代表结束，每个数字代表下一个节点。每行是一个节点，它们的编号从 0 开始。因此，在这个特定实例中，有 3 条路径：0>1>2>3>4>-1、0>4>-1 和 0>1>4 >-1.

import java.io.*;
import java.util.*;

public class PathFinder {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<ArrayList<String>> wholeList = new ArrayList<ArrayList<String>>();
        while (scanner.hasNext()) {
            String input = scanner.nextLine();
            
            StringTokenizer st = new StringTokenizer(input, " ");

            ArrayList<String> temp = new ArrayList<String>();
            while(st.hasMoreTokens()) {
                temp.add(st.nextToken());
            }
            wholeList.add(temp);
        }

        return count;
    }
}

Answer 1

我建议您更改数组，使它们包含整数而不是字符串。那么你可以使用递归解决方案：

import java.io.*;
import java.util.*;

public class PathFinder {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<List<Integer>> wholeList = new ArrayList<>();
        while (scanner.hasNext()) {
            String input = scanner.nextLine();
            
            StringTokenizer st = new StringTokenizer(input, " ");

            List<Integer> temp = new ArrayList<>();
            while(st.hasMoreTokens()) {
                temp.add(Integer.valueOf(st.nextToken()));
            }
            wholeList.add(temp);
        }
        countRoutes(wholeList, 0);
        System.out.println(count);
    }
    
    private static int count = 0;

    private static void countRoutes(List<List<Integer>> tree, int nodeFrom) {
        for (Integer target : tree.get(nodeFrom)) {
            if (-1 == target) {
                count++;
            } else {
                countRoutes(tree, target);
            }
        }
    }
}

如果你想看到路线，你可以稍微修改一下方法：

private static void printRoutes(List<List<Integer>> tree, int nodeFrom, String route) {
    for (Integer target : tree.get(nodeFrom)) {
        if (-1 == target) {
            count++;
            System.out.println(route + "->-1");
        } else {
            printRoutes(tree, target, route + "->" + target);
        }
    }
}

并从主程序调用它为

printRoutes(wholeList, 0, "0");

2021 年 3 月 3 日更新

一种更有效的方法是缓存从给定节点到终点的路径数：

private static int countRoutes(List<List<Integer>> tree, 
                               int nodeFrom, 
                               int[] pathsNumber)
{
    if (nodeFrom == -1) {
        return 1;
    }
    if (pathsNumber[nodeFrom] >= 0) {
        return pathsNumber[nodeFrom];
    }

    int sum = 0;
    for (Integer target : tree.get(nodeFrom)) {
        sum += countRoutes(tree, target, pathsNumber);
    }
    pathsNumber[nodeFrom] = sum;
    return sum;
}

然后在 main 方法中初始化数组 pathsNumber 并按如下方式调用此方法（-1 表示我们尚未计算通往此节点出口的路径数）：

int[] pathsNumber = new int[wholeList.size()];
Arrays.fill(pathsNumber, -1);
System.out.println(countRoutes(wholeList, 0, pathsNumber));