Entiendo los conceptos básicos de cómo funciona una búsqueda en amplitud. Utiliza una estructura de datos de cola para encontrar vértices adyacentes nivel por nivel.

Mi problema es entender cómo encontrar el camino más corto entre dos vértices. En el siguiente ejemplo, asignamos vértices recién visitados junto con su borde a una matriz llamada edgeTo , pero mi pregunta es ¿cómo se almacenan los datos? ¿Es una matriz bidimensional? ¿Y cómo se recupera con la función pathTo ?

El bucle for en la función pathTo me parece un poco extraño, sin duda porque podría ser nuevo en esto. ¿Cómo obtiene esto la ruta más corta y cómo se estructuran los datos o cómo se guardan los bordes?

 // add this to Graph class this.edgeTo = []; // bfs function function bfs(s) { var queue = []; this.marked[s] = true; queue.push(s); // add to back of queue while (queue.length > 0) { var v = queue.shift(); // remove from front of queue if (v == undefined) { print("Visited vertex: " + v); } for each(var w in this.adj[v]) { if (!this.marked[w]) { this.edgeTo[w] = v; this.marked[w] = true; queue.push(w); } } } } function pathTo(v) { var source = 0; if (!this.hasPathTo(v)) { return undefined; } var path = []; for (var i = v; i != source; i = this.edgeTo[i]) { // this for loop is new to me path.push(i); } path.push(s); return path; } function hasPathTo(v) { return this.marked[v]; }