寻找图中两点间所有路径的实际应用

深夜睡不着，开始回忆之前做过的东西。恰巧知乎刷到了深度优先和广度优先的讨论，我想起了之前项目中一个不错的应用案例。

模拟机电实验室，提供数量一定的电源、闸刀开关、电机启动器、滑动变阻器、电阻、电压表、电流表、用电负载等元件，元件有接线柱，每两个接线柱间自由连线。用户进入虚拟实验室，按电路图连接所需的元件，连接完成后提交。

提交后系统判断连接状态，如不正确则报错，报错要显示短路、断路、多余元件等。报错信息基于回路，但要精确到单个元件。判断时要有灵活性，例如闸刀开关接在某元件前和某元件后，有时等价，有时不等价。又或者短路了一个没接入回路的元件，不影响实验。

一切正确后，进入模拟实验步骤，实验过程中调节滑动变阻器、电压、开关等可交互元件，电路元件需要做出响应（电压表、电流表针变化、负载状态变化等）。

在该项目中的做法是模拟电流走向，即电流从电源正极出发，最终回到负极（和电子方向相反）。

每个元件有自己的阻值，例如连接用的导线、闸刀开关、电流表等阻值看作 0，电压表阻值为无穷大。

因此，找出所有电流走向路径，然后与正确路径的阻值和节点元件对比，即可分析出连接情况。

首先建立了一张元件接线柱的基础权重列表，其结构大致如下：

{
    电流表A接线柱a:0
    电流表A接线柱b:1
    权重:100
}
{
    闸刀开关A接线柱a:2
    闸刀开关A接线柱b:3
    权重:10
}
{
    电阻A接线柱a:4
    电阻B接线柱b:5
    权重:200
}

其中接线柱后的值即该接线柱的唯一 ID，而权重与阻值相关但不一定相等。

为什么说权重与阻值相关而二者不一定相等呢？因为我们希望在判断阻值时多排除一些不符的电路（当然不可能完全排除），而权重如果等于阻值，有些情况会不能排除。

举个例子，用户用电流表替换了闸刀开关，假设都用阻值 0 计算，则总阻值数值相同，无法排除不符合的电路。

我记得当初是用权重 10 代表开关，权重 100 代表电流表，当然记忆可能有出入。

之后，将这些接线柱的邻接矩阵生成好，默认每两个接线柱间的权重为 0，再将上面的权重填充进该矩阵，这样就得到了初始邻接矩阵。

用户连线时，前台处理用户逻辑并展示对应表现后，将该线的信息发送至邻接表组件：

{
    连接柱1:4(电阻 A 接线柱 a 的 ID)
    连接柱2:3(闸刀开关 A 接线柱 b 的 ID)
    权重:1
}

邻接表会将两个接线柱间的权重修改为 1，即导线的权重。

我们使用深度优先遍历获取电源正极负极间的所有路径，也就是物理上说的回路。

注意当某元件被短路时，元件两接线柱间的权重为 1，这样回路的阻值就有可能与正常回路产生区别，后面的步骤中就有可能提前排除该回路。

极端条件下（即任意两个接线柱间都连通），该算法的时间复杂度为O(n^2)，但根据操作时，不会有人花几个小时把几十个点两两互连，因此暂不考虑算法效率问题。

这部分应该用流程图表示，但我有点困了，就不画了。

首先对比实际回路个数与正确回路个数。

如果回路数不正确，对比实际元件的权重与标准权重，看是否有短路，之后对比总权重和元件，针对性报错。

如果回路数正确，则对比总权重值。

如果回路数正确、总权重值不正确，先找元件是否短路，之后对比总权重和元件，有针对性报错。

如果回路数与总权重都正确，则先找元件短路，再根据每个实验实际需要，特异化对比元件顺序。

当然，实际写的判错代码要比上面文字复杂得多，尤其是涉及报错优先级、元件接入判断等，不过基本原理算是讲清楚了。

深夜闲谈，只讲想法不提代码。只要会了想法，用啥语言写代码都不成问题。