Правильно ли работает алгоритм поиска в ширину?

Question

Начал изучать алгоритмы и струкуры данных по книжке "Data Structures and Algorithms with JavaScript", но почему-то алгоритм поиска как в грубину, так и в ширину делает ошибки. Граф строится на основе списока смежности. Продемонстрирую появлениее ошибки на алгоритме поиска в ширину (см. граф в закрепе - 1 скрн). Начинаем прогон по графу с :
0: 0 1 2 3 4 (правильно)
1: 1 0 2 3 4 (правильно)
2: 2 0 1 3 4 (ошибка?)
3: 3 0 1 2 4 (правильно)
4: 4 0 1 2 3 (ошибка?)

Собственно, по моему мнению и по мнению сервиса для графов из Интернета, ошибки получаются при поиске с вершин 2 и 4, ибо должно быть:
2: 2 0 4 1 3 (как выглядит граф для вершины с 2, см. скрин 2)
4: 4 2 0 1 3 (как выглядит граф для вершины с 4, см. скрин 3)

Вот код:

function Graph(v) {
 this.vertices = v;
 this.edges = 0;
 this.adj = [];
 for (var i = 0; i < this.vertices; ++i) {
   this.adj[i] = [];
   this.adj[i].push("");
 }
 this.addEdge = addEdge;
 this.showGraph = showGraph;
 this.bfs = bfs;
 this.edgeTo = [];
 this.marked = [];
 for (var i = 0; i < this.vertices; ++i) {
  this.marked[i] = false;
 }
}

function addEdge(v,w) {
 this.adj[v].push(w);
 this.adj[w].push(v);
 this.edges++;
}

function showGraph() {
 document.write("Выводим граф: <br>");
 for (var i = 0; i < this.vertices; ++i) {
 document.write(i + " -> \n");
 for (var j = 0; j < this.vertices; ++j) {
 if (this.adj[i][j] !== undefined && this.adj[i][j] !== "")
  document.write(this.adj[i][j] + ' ' );
 }
 document.write("<br>");
 }
}

function bfs(s) {
    let queue = [];
    this.marked[s] = true;
    queue.push(s); 
    while (queue.length > 0) {
        let v = queue.shift(); 
        if (v !== undefined && v !== "")
          document.write("Visited vertex: " + v + "<br>");
        for(let w in this.adj[v]) {                 // исправил
            if (!this.marked[this.adj[v][w]]) {     // исправил
                this.marked[this.adj[v][w]] = true; // исправил
                queue.push(this.adj[v][w]);         // исправил
            }
        }
    }
}


let g = new Graph(5);
g.addEdge(0,1);
g.addEdge(0,2);
g.addEdge(0,3);
g.addEdge(2,4);
g.showGraph();
g.bfs(4);

Answer 1

Когда вы достали вершину v из очереди, нужно в очередь положить все смежные с v и непомеченные, а у вас в цикле по w что попало делается.

Обходите список adj[v], проверяя на помеченность

for w in adj[v]   //или как там в JS делается
    if  !marked[w] 
       queue.push(w);

БЛОГ НА HUSL

Правильно ли работает алгоритм поиска в ширину?

Ответы (1 шт):