《Eloquent JavaScript》中findRoute函数工作原理及迭代过程咨询

Hey there! Let's break down this findRoute function step by step, using the Meadowfield road network you referenced. I'll walk through each iteration, explain what's happening, and answer your specific questions along the way.

First, Let's Set the Stage #

First, the roadGraph variable is a bidirectional graph built from the roads array using buildGraph. Each key is a location, and its value is an array of directly connected spots. For example:

roadGraph["Alice's House"] = ["Bob's House", "Cabin", "Post Office"];
roadGraph["Bob's House"] = ["Alice's House", "Town Hall"];

This graph lets us quickly look up which places are reachable from any given location.

What is findRoute Doing? #

This is a breadth-first search (BFS) algorithm—ideal for finding the shortest path in an unweighted network like Meadowfield's roads (where every "step" between locations counts the same). BFS explores all locations 1 step from the start first, then all 2 steps away, etc. That means the first time we hit our destination, we know it's the shortest possible path.

Step-by-Step Walkthrough with Your Example #

Let's trace the call findRoute(roadGraph, "Alice's House", "Town Hall") in detail:

Initialization #

We start by setting up our work queue:

let work = [{at: "Alice's House", route: []}];

Each entry in work is a "task": it tells us where we currently are (at) and the path we took to get there (route).

Iteration 1 (i = 0) #

We pull the first task from work:

let {at: "Alice's House", route: []} = work[0];

Now we loop through all locations directly connected to "Alice's House":

• Bob's House: Not our target ("Town Hall"). Check if any task in work already has at: "Bob's House"? No. So we add a new task to work:

  work.push({at: "Bob's House", route: ["Bob's House"]});
  

• Cabin: Not our target. Not in work yet—add it:

  work.push({at: "Cabin", route: ["Cabin"]});
  

• Post Office: Not our target. Not in work yet—add it:

  work.push({at: "Post Office", route: ["Post Office"]});
  

Now work has 4 entries total:

[
  {at: "Alice's House", route: []},
  {at: "Bob's House", route: ["Bob's House"]},
  {at: "Cabin", route: ["Cabin"]},
  {at: "Post Office", route: ["Post Office"]}
]

Iteration 2 (i = 1) #

Next we pull the second task from work:

let {at: "Bob's House", route: ["Bob's House"]} = work[1];

Loop through its connected locations:

• Alice's House: Already exists in work (the first entry), so we skip adding it again (we don't want to loop in circles).
• Town Hall: This is our target! We immediately return route.concat("Town Hall"), which gives us:

  ["Bob's House", "Town Hall"]
  

The function exits here—we found our shortest path!

Your Questions Answered #

1. What does each iteration do? #

Each iteration follows this pattern:

• Takes one task from the work array (since it's processed in order, it acts like a first-in-first-out queue).
• Looks at every location directly connected to the current at spot.
  • If the connected location is our destination, return the path to get there plus this location.
  • If the connected location hasn't been added to work yet (checked via work.some(w => w.at == place)), add a new task for it with the updated path (original route + this new location).

2. Does the work array grow every time? #

No. The work array only grows when we discover a location that hasn't been added to the queue before. For example, when we processed "Bob's House" and looked at "Alice's House", we didn't add anything to work because Alice's House was already in the array. It only expands when we find new, unvisited locations.

A Quick Note on BFS #

Because we process locations in order of their distance from the start (1 step, then 2 steps, etc.), the first time we reach the destination, that's guaranteed to be the shortest path. That's why this algorithm works so well for this type of problem!

内容的提问来源于stack exchange，提问作者Peter Staal