JavaScript算法实现dfs查找省市区路径

需求

存在如下数组，实现一个算法通过输入区名，返回省->市->区格式的路径，例如输入西湖区，返回浙江省->杭州市->西湖区。

// 定义省市区的嵌套数组
const data = [{name: "浙江省",children: [{name: "杭州市",children: [{ name: "西湖区" },{ name: "上城区" },{ name: "下城区" }]},{name: "宁波市",children: [{ name: "海曙区" },{ name: "江东区" },{ name: "江北区" }]},{name: "温州市",children: [{ name: "鹿城区" },{ name: "龙湾区" },{ name: "瓯海区" }]}]},{name: "北京市",children: [{ name: "东城区", children: [] },{ name: "西城区", children: [] },{ name: "朝阳区", children: [] },{ name: "海淀区", children: [] }]},{name: "江苏省",children: [{name: "南京市",children: [{ name: "玄武区" },{ name: "秦淮区" },{ name: "建邺区" }]},{name: "苏州市",children: [{ name: "姑苏区" },{ name: "吴中区" },{ name: "相城区" }]},{name: "无锡市",children: [{ name: "梁溪区" },{ name: "滨湖区" },{ name: "新吴区" }]}]}
];

分析

数据是一个嵌套结构，DFS 是一种合适的遍历方法。它可以递归地深入到每个节点的子节点中进行搜索。

但是需要考虑如果该节点下没有查找到的情况，则需要将该节点从path中去掉，继续遍历下一个节点。

• 将当前节点的名称添加到路径中。
• 如果当前节点的名称是目标区名，返回 true 表示找到目标，并保留路径。
• 如果当前节点有子节点，递归地对每个子节点调用 DFS。
• 如果在所有子节点中都没有找到目标，从路径中移除当前节点名称，并返回 false。

代码

// 定义DFS查找路径的函数
function findPathDFS(node, target, path) {path.push(node.name);if (node.name === target) {return true;}if (node.children) {for (const child of node.children) {if (findPathDFS(child, target, path)) {return true;}}}path.pop();return false;
}function findPath(data, districtName) {const path = [];for (const province of data) {if (findPathDFS(province, districtName, path)) {return path;}}return null; // 未找到返回null
}// 测试查找路径函数
const districtName = "西湖区";
const path = findPath(data, districtName);if (path) {console.log(`路径: ${path.join(" -> ")}`);
} else {console.log("未找到该区");
}

结果：