使用 BFS 寻找循环的图

Question

我写了这段代码，它应该通过读取一个显示人与人之间债务的文本文件来找到一个循环。所以“person1,person2,amount”表示 person1 欠 person2 的金额。我需要创建一种方法来查找文件中人员之间的循环。因此，如果文件包含以下信息：Paul,Jesse,50 杰西，狮子座，75 岁 狮子座，保罗，100 循环可以是 [Paul, Jesse, Leo]、[Jesse, Leo, Paul] 或 [Leo, Paul, Jesse]，循环次数为 50.

我有测试来确保循环的顺序是正确的，当我运行测试时，它说循环中只有两个人，而应该是 3 个人，而且它说循环量是 -50什么时候应该是 50。我不擅长使用调试器，所以我没有从中得到太多信息。

以下是一些可以提供帮助的信息：

findCycle 方法不带参数，并使用提供的 Cycle 类返回对 Cycle 对象的引用。该方法会检测债务数据是否存在循环，存在则返回。如果有任意数量的人都欠下一个人钱，而最终以某种方式归还给原始债务人，则存在一个循环。循环的金额是整个循环的最小欠款额。如果存在这样的循环，则循环中每笔债务的金额都可以减少循环金额（您不必减少债务，只需检测循环即可）。例如，如果保罗欠杰西 50 美元，杰西欠利奥 75 美元，而利奥欠保罗 100 美元，则有一个循环 [保罗、杰西、利奥] 为 50 美元 如果不存在循环，则该方法返回 null 如果存在循环，则返回一个循环对象，其中包含循环中每个人的姓名（按出现顺序排列）和循环数量。请注意，起点不明确，因此您的测试必须接受任何有效的顺序。在上面的示例中，存在三个有效顺序 [Paul, Jesse, Leo]、[Jesse, Leo, Paul] 和 [Leo, Paul, Jesse] 您可以假设数据文件中最多有 1 个周期，并且您的测试用例最多应包含 1 个周期 一个周期可以小到2个节点（比如2个人互相欠钱） 提示：如果你运行 BFS 并找到一条通向起始节点的边，你就找到了一个循环

这是我的代码：

package money;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;

public class DebtCalculator {
    private Map<String, Integer> debts;


    public DebtCalculator(String filename){
        debts = new HashMap<String, Integer>();
        try {
            ArrayList<String> lines = new ArrayList<>(Files.readAllLines(Paths.get(filename)));
            for (String line : lines) {
                ArrayList<String> fields = new ArrayList<>(Arrays.asList(line.split(",")));
                String person1 = fields.get(0);
                String person2 = fields.get(1);
                int amount = Integer.parseInt(fields.get(2));
                int existingDebt = debts.getOrDefault(person1, 0);
                debts.put(person1, existingDebt - amount);
                int existingCredit = debts.getOrDefault(person2, 0);
                debts.put(person2, existingCredit + amount);
            }
        }catch(IOException e){
            new ArrayList<>();
        }
    }

    public int netGains(String person) {
        return debts.getOrDefault(person, 0);
    }

    public Cycle findCycle() {
        Map<String, String> parents = new HashMap<String, String>();
        Map<String, Integer> cycleAmounts = new HashMap<String, Integer>();
        Queue<String> queue = new ArrayDeque<String>();
        for (String person : debts.keySet()) {
            parents.put(person, null);
            cycleAmounts.put(person, 0);
            queue.add(person);
        }
        while (!queue.isEmpty()) {
            String person1 = queue.poll();
            int amount1 = debts.get(person1);
            for (String person2 : debts.keySet()) {
                if (person1.equals(person2)) {
                    continue;
                }
                int amount2 = debts.get(person2);
                int amount12 = Math.min(amount1, - amount2);
                int newAmount1 = amount1 - amount12;
                int newAmount2 = amount2 + amount12;
                if (newAmount1 == 0) {
                    continue;
                }
                if (parents.get(person2) == null) {
                    parents.put(person2, person1);
                    cycleAmounts.put(person2, amount12);
                    queue.add(person2);
                } else if (parents.get(person2).equals(person1)) {
                    ArrayList<String> peopleInCycle = new ArrayList<String>();
                    String person = person2;
                    int cycleAmount = cycleAmounts.get(person);
                    while (!person.equals(person1)) {
                        peopleInCycle.add(person);
                        person = parents.get(person);
                        cycleAmount = Math.min(cycleAmount, cycleAmounts.get(person));
                    }
                    peopleInCycle.add(person1);
                    // return the first cycle found
                    return new Cycle(peopleInCycle, cycleAmount);
                }
            }
        }
        // no cycle found
        return null;
    }
}
package money;

import java.util.ArrayList;

public class Cycle {

    private ArrayList<String> peopleInCycle;
    private int cycleAmount;

    public Cycle(ArrayList<String> peopleInCycle, int cycleAmount) {
        this.peopleInCycle = peopleInCycle;
        this.cycleAmount = cycleAmount;
    }

    public ArrayList<String> getPeopleInCycle() {
        return this.peopleInCycle;
    }

    public void setPeopleInCycle(ArrayList<String> peopleInCycle) {
        this.peopleInCycle = peopleInCycle;
    }

    public int getCycleAmount() {
        return this.cycleAmount;
    }

    public void setCycleAmount(int cycleAmount) {
        this.cycleAmount = cycleAmount;
    }

}

我有测试来确保循环的顺序是正确的，当我运行测试时，它说循环中只有两个人，而应该是 3 个人，而且它说循环量是 -50什么时候应该是 50。我不擅长使用调试器，所以我没有从中得到太多信息。

以下是一些可以提供帮助的信息：

findCycle 方法不带参数，并使用提供的 Cycle 类返回对 Cycle 对象的引用。该方法会检测债务数据是否存在循环，存在则返回。如果有任意数量的人都欠下一个人钱，而最终以某种方式归还给原始债务人，则存在一个循环。循环的金额是整个循环的最小欠款额。如果存在这样的循环，则循环中每笔债务的金额都可以减少循环金额（您不必减少债务，只需检测循环即可）。例如，如果保罗欠杰西 50 美元，杰西欠利奥 75 美元，而利奥欠保罗 100 美元，则有一个循环 [保罗、杰西、利奥] 为 50 美元 如果不存在循环，则该方法返回 null 如果存在循环，则返回一个循环对象，其中包含循环中每个人的姓名（按出现顺序排列）和循环数量。请注意，起点不明确，因此您的测试必须接受任何有效的顺序。在上面的示例中，存在三个有效顺序 [Paul, Jesse, Leo]、[Jesse, Leo, Paul] 和 [Leo, Paul, Jesse] 您可以假设数据文件中最多有 1 个周期，并且您的测试用例最多应包含 1 个周期 一个周期可以小到2个节点（比如2个人互相欠钱） 提示：如果你运行 BFS 并找到一条通向起始节点的边，你就找到了一个循环