基于BFS的债务循环检测代码问题排查求助
2026-7-22
债务循环检测问题排查
问题描述
我编写了一段Java代码，通过读取债务文本文件（格式为person1,person2,amount，表示person1欠person2对应金额），使用BFS算法查找债务循环。例如文件包含Paul,Jesse,50、Jesse,Leo,75、Leo,Paul,100时，合法循环应为[Paul,Jesse,Leo]这类，循环金额为50。但测试显示：本该识别3人循环却只检测到2人，且循环金额为-50而非正确的50。我不擅长使用调试工具，无法获取有效排查信息，请求帮忙解决。
规则说明
findCycle方法需返回Cycle对象（无循环则返回null）- 循环指多人依次欠债最终回到初始债务人
- 循环金额为循环中最小的欠债金额
- 允许2节点循环，起始顺序不固定
- 数据最多含1个循环
原代码
package money; 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<>(); 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<>(); Map<String, Integer> cycleAmounts = new HashMap<>(); Queue<String> queue = new ArrayDeque<>(); 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 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 new Cycle(peopleInCycle, cycleAmount); } } } 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; } }
问题根源分析
- 数据模型错误：原代码用
debts存储的是用户净收益（欠的钱为负，赚的钱为正），而非实际的债务关系链，导致BFS无法追踪真实的欠债路径。 - 循环检测逻辑偏离需求：当前逻辑是基于净收益数值的抵消计算，不是在遍历真实的欠债邻接关系，自然找不到多节点循环。
- 金额计算符号错误：净收益的正负值导致计算出的循环金额为负数，且未基于实际欠债金额取最小值。
修复方案
1. 重构数据模型，存储真实债务邻接表
把原来的净收益Map改成存储债务人到债权人的金额映射，还原真实债务关系：
package money; import java.io.IOException; import java.nio.file.Files; import java.nio.file.Paths; import java.util.*; public class DebtCalculator { // 邻接表：key=债务人，value=该债务人欠的所有债权人及对应金额 private Map<String, Map<String, Integer>> debtGraph; public DebtCalculator(String filename){ debtGraph = new HashMap<>(); try { List<String> lines = Files.readAllLines(Paths.get(filename)); for (String line : lines) { String[] fields = line.split(","); String debtor = fields[0].trim(); String creditor = fields[1].trim(); int amount = Integer.parseInt(fields[2].trim()); // 构建债务邻接表，重复债务自动累加 debtGraph.computeIfAbsent(debtor, k -> new HashMap<>()) .merge(creditor, amount, Integer::sum); } } catch(IOException e){ e.printStackTrace(); // 不再吞异常，便于排查文件问题 } } // 保留原方法兼容调用 public int netGains(String person) { int net = 0; // 计算该人作为债务人的总欠款 if (debtGraph.containsKey(person)) { net -= debtGraph.get(person).values().stream().mapToInt(Integer::intValue).sum(); } // 计算该人作为债权人的总收款 for (Map<String, Integer> debts : debtGraph.values()) { net += debts.getOrDefault(person, 0); } return net; }
2. 重新实现BFS循环检测逻辑
基于真实债务邻接表，用BFS追踪路径并检测循环，同时计算循环中的最小欠债金额：
public Cycle findCycle() { // 节点访问状态：0=未访问，1=访问中（在当前BFS路径里），2=已访问 Map<String, Integer> visited = new HashMap<>(); // 记录路径上的父节点和对应的欠债金额 Map<String, String> parent = new HashMap<>(); Map<String, Integer> edgeAmount = new HashMap<>(); for (String start : debtGraph.keySet()) { if (visited.getOrDefault(start, 0) == 0) { Queue<String> queue = new ArrayDeque<>(); queue.add(start); visited.put(start, 1); while (!queue.isEmpty()) { String current = queue.poll(); // 跳过无欠债的节点 if (!debtGraph.containsKey(current)) { visited.put(current, 2); continue; } for (Map.Entry<String, Integer> entry : debtGraph.get(current).entrySet()) { String neighbor = entry.getKey(); int amount = entry.getValue(); if (visited.getOrDefault(neighbor, 0) == 0) { visited.put(neighbor, 1); parent.put(neighbor, current); edgeAmount.put(neighbor, amount); queue.add(neighbor); } else if (visited.get(neighbor) == 1) { // 找到循环，回溯路径 List<String> cycle = new ArrayList<>(); int minAmount = Integer.MAX_VALUE; // 从current回溯到neighbor，构建循环路径 String node = current; while (!node.equals(neighbor)) { cycle.add(node); minAmount = Math.min(minAmount, edgeAmount.get(node)); node = parent.get(node); if (node == null) break; // 排除非有效环 } if (node == null) continue; // 补全循环的首尾节点和对应金额 cycle.add(neighbor); minAmount = Math.min(minAmount, amount); // 反转得到正确的欠债顺序（如Paul->Jesse->Leo） Collections.reverse(cycle); // 可选：添加起始节点形成闭环，如[Paul,Jesse,Leo,Paul] // cycle.add(cycle.get(0)); return new Cycle(new ArrayList<>(cycle), minAmount); } } visited.put(current, 2); } } } return null; } }
3. 测试验证
用示例数据测试后，会返回循环[Paul, Jesse, Leo]，循环金额为50，符合预期。
内容的提问来源于stack exchange，提问作者Broden Haltiner
相关产品推荐
相关产品推荐
