计算给定电阻邻接列表的总电阻

Question

我需要解决的问题是计算给定连接电阻列表的电路的总电阻（如果将电阻视为节点，则为邻接列表）。

例如以下电路：

列表将如下所示：

R1 -> R2
R1 -> R3
R2 -> R4
R3 -> R4

每个电阻都有一个 ID 及其阻值。连接元组存储在具有

getFrom

和

getTo

方法的结构中。

我到目前为止开发的递归算法考虑了 2 个任意电阻之间的总电阻的计算：

private double calculateResistance(Resistor c1, Resistor c2){
    double res = 0;
    for(ComponentConnection cc : getGraph()){
        if(cc.getFrom().getId() == c1.getId()){
            if(cc.getTo().getId() == c2.getId())
                return c1.getRes() + c2.getRes();
            res += (1/calculateResistance(cc.getTo(),c2));
        }
    }
    return c1.getRes() + 1/res;
}

问题在于，当电路中存在分叉时，算法无法确定何时完成并重复某些组件（在示例中，R4 被考虑了两次）。

有什么想法可以解决这个问题或用其他方法解决问题吗？

Answer 1

我会通过递归减少节点来解决这个问题，而不是电阻器：

• 从第一个和最后一个节点开始
• 有中间节点吗？
• 不 -> 你已经完成了。 返回（一个或无）中间电阻的电阻
• 是的，有中间节点 -> 对于中间串联/并联节点，通过递归归约来归约。

为最简单的串联/并联节点（2个并联和2个串联）定义reduce函数。 所有其他的最终都会减少到这些。

Answer 2

有两种操作供您考虑：

• 减少并联电阻
• 减少串联电阻
  
  

对于并联电阻，您必须考虑电阻器：

如果两个电阻在一侧共享一个连接并在另一侧共享另一个连接，您可以减少它们

对于串联电阻，您必须考虑节点：

如果一个节点仅连接两个电阻器，您可以减少它们

算法是：

boolean isStillWorking = true;
do{
    boolean foundParallel = reduceParallel();
    boolean foundSerial = reduceSerial();
    isStillWorking = foundParallel | foundSerial;
}while(isStillWorking);

Answer 3

我用 C++ 编写了一个解决方案。

这里是链接：https://khobaib529.medium.com/solving-electrical- Circuits-a-graph-based-algorithm-for-resistance-calculations-921575c59946