《Eloquent Javascript》3rd Edition中buildGraph函数for循环作用咨询
关于《Eloquent Javascript》中buildGraph函数for循环的疑问
这段代码出自《Eloquent Javascript》第3版第7章,场景是负责取件派件的快递机器人,村庄包含11个地点与14条道路,由roads数组描述。我没法理解buildGraph函数,尤其是里面的for循环,想请教这个for循环的作用是什么?
const roads = [ "Alice's House-Bob's House", "Alice's House-Cabin", "Alice's House-Post Office", "Bob's House-Town Hall", "Daria's House-Ernie's House", "Daria's House-Town Hall", "Ernie's House-Grete's House", "Grete's House-Farm", "Grete's House-Shop", "Marketplace-Farm", "Marketplace-Post Office", "Marketplace-Shop", "Marketplace-Town Hall", "Shop-Town Hall", ]; function buildGraph(edges) { let graph = Object.create(null); function addEdge(from, to) { if (graph[from] == null) graph[from] == [to]; else graph[from].push(to); } for (let [from, to] of edges.map((r) => r.split("-"))) { addEdge(from, to); addEdge(to, from); } return graph; } const roadGraph = buildGraph(roads);
这个for循环的核心作用是把原始的道路字符串数据,转换成双向通行的邻接表图结构,具体拆解成三步:
- 预处理道路数据:
edges.map((r) => r.split("-"))会把每条用-连接的地点字符串(比如"Alice's House-Bob's House")分割成包含两个地点的数组,变成["Alice's House", "Bob's House"]的格式。 - 遍历拆分后的地点对:用解构赋值
let [from, to]把每个数组的两个元素分别取出,代表一条道路连接的两个端点。 - 构建双向可达关系:因为村庄的道路是双向通行的(从A到B能走,从B到A也能走),所以每次循环会调用两次
addEdge:- 第一次把
to加入from的可达地点列表 - 第二次把
from加入to的可达地点列表
- 第一次把
举个实际例子,处理"Alice's House-Bob's House"时:
- 先执行
addEdge("Alice's House", "Bob's House"),让Alice家的可达列表里包含Bob家 - 再执行
addEdge("Bob's House", "Alice's House"),让Bob家的可达列表里包含Alice家
整个循环跑完后,就能得到一个可以快速查询「任意地点能直接到哪些地方」的图结构,方便后续快递机器人规划路线。
另外提一句,代码里有个小bug:addEdge函数里的graph[from] == [to]应该改成graph[from] = [to],不然没法正确初始化地点的可达列表。
内容的提问来源于stack exchange,提问作者bardala
相关产品推荐
相关产品推荐

