配电网馈线拓扑深度优先搜索(DFS)算法解析

一、 背景知识：电力拓扑建模

在配电自动化系统（DAS）中，电网并非简单的图片，而是基于CIM (Common Information Model) 抽象出的图论模型。每一个物理设备（如断路器、负荷开关、导线段）被视为图中的一个节点 (Node)。

关键概念：

• ConnectivityNode (连接点)：物理上的接线端子。在数据集中体现为 connectivity_node。
• Equipment (一次设备)：断路器 (Breaker)、隔离开关 (Disconnector)、交流导线段 (ACLineSegment)。
• 拓扑关联：两个设备通过共享同一个 connectivity_node 实现电气连接。

避雷器 (Arrester) 在本模型中通常挂接在导线段的末端，用于吸收过电压能量，保护变压器等核心资产。搜索两个开关间的避雷器，本质是在图中寻找简单路径 (Simple Path) 及其关联的分支节点。

二、 算法核心流程

1. 邻接表构建原理

由于电力线路是双向导电的，图被抽象为无向图。我们必须处理“节点-连接点-节点”的多级关系：

// 伪代码：构建双向映射
FOR each link IN links:
    device = link.source;
    conn_node = link.connectivity_node;
    graph[device].add(conn_node);
    graph[conn_node].add(device); // 建立双向索引

三、 交互式拓扑演示

四、 核心算法实现 (JavaScript)

function findArrestersInPath(startId, endId, nodes, links) {
    // 1. 预处理：构建邻接表
    const adj = {};
    links.forEach(l => {
        if (!adj[l.source]) adj[l.source] = [];
        adj[l.source].push(l.target); // 简化版：直接关联 source 与 target
    });

    // 2. DFS 搜索路径
    let resultPath = [];
    function dfs(curr, target, visited, path) {
        if (curr === target) { resultPath = [...path]; return true; }
        visited.add(curr);
        for (let neighbor of (adj[curr] || [])) {
            if (!visited.has(neighbor)) {
                if (dfs(neighbor, target, visited, [...path, neighbor])) return true;
            }
        }
        return false;
    }

    dfs(startId, endId, new Set(), [startId]);

    // 3. 过滤避雷器 (根据名称或类型标识)
    return resultPath.filter(id => {
        const node = nodes.find(n => n.id === id);
        return node && node.name.includes('避雷器');
    });
}