JavaScript中的广度优先搜索

Question

function BFS_search(data, start, ende){
    var queue = new Array();
    var steps = 0;
    for(var x=0; x<data.Adjazenzen.length-1; x++){  //push start Element in Queue
        if(data.Adjazenzen[x] == start){
            queue.push(data.Adjazenzen[x]);
            steps++;
            break;
        }
    }

    while(queue.length != 0) {
        var t = queue.pop();
        if(t.Von == ende) {
            return t.Von;
        }
        if(t.Nach == ende){
            return t.Nach;
        }
        else{
            queue.push(data.Adjazenzen[0]);
            data.Adjazenzen.shift();
            steps++;
            break;
        }
    }
    return "keine Ergebnis";
}

这段代码应该能够从给定的JSON对象中计算出两个点之间的最佳路径，并添加起始节点和结束节点之间的所有点。基本上，它应该是一个使用BFS的导航系统。

JSON对象的格式如下：

{"Adjazenzen":[
{"Von":"A1.02","Nach":"G-A3-1","X":"5778","Y":"223","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"},
    {"Von":"A1.04","Nach":"G-A3-1","X":"5025","Y":"223","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"},
    {"Von":"A1.05","Nach":"G-A3-1","X":"4212","Y":"223","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"},
    {"Von":"A1.06","Nach":"G-A3-1","X":"3016","Y":"223","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"},
    {"Von":"A1.07","Nach":"G-A3-1","X":"2354","Y":"223","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"},
    {"Von":"A1.08","Nach":"G-A3-1","X":"1856","Y":"223","Z":"3","Treppe":"1","Gebaeude":"A","Level":"0"},
    {"Von":"A1.12","Nach":"G-A3-1","X":"1313","Y":"223","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"},
    {"Von":"B1.01","Nach":"G-B3-1","X":"6572","Y":"223","Z":"3","Treppe":"1","Gebaeude":"B","Level":"0"},
    {"Von":"G-A3-1","Nach":"G-A3-2","X":"906","Y":"223","Z":"3","Treppe":{},"Gebaeude":{},"Level":{}},
    {"Von":"G-A3-1","Nach":"B1.01","X":"6572","Y":"223","Z":"3","Treppe":"1","Gebaeude":"B","Level":"0"},
    {"Von":"G-A3-2","Nach":"A1.14","X":"1066","Y":"1333","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"},
    {"Von":"G-A3-2","Nach":"G-A3-3","X":"1444","Y":"4016","Z":"3","Treppe":{},"Gebaeude":{},"Level":{}},
    {"Von":"G-A3-2","Nach":"A1.15","X":"1207","Y":"2340","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"},
    {"Von":"G-A3-2","Nach":"A1.18","X":"1444","Y":"4016","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"},
    {"Von":"G-A3-2","Nach":"A1.16","X":"1327","Y":"3188","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"},
    {"Von":"G-A3-2","Nach":"A1.13","X":"933","Y":"383","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"},
    {"Von":"G-A3-2","Nach":"A1.17","X":"1425","Y":"3884","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"},
    {"Von":"G-A3-3","Nach":"A1.19","X":"2691","Y":"3977","Z":"3","Treppe":"1","Gebaeude":"A","Level":"0"},
    {"Von":"G-A3-3","Nach":"A1.22","X":"2946","Y":"3969","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"},
    {"Von":"G-A3-3","Nach":"A1.23","X":"2946","Y":"3969","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"},
    {"Von":"G-A3-3","Nach":"A1.20","X":"1990","Y":"4002","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"}]}

你可以忽略除了“Von（从）”和“Nach（到）”之外的所有内容。问题在于我的BFS并不能完全工作，我不知道该如何解决。

举个例子： 如果你想计算从A1.04到A1.15，它应该添加： A1.04，G-A3-1，G-A3-2，A1.15

如果你想从A1.04到A1.20： A1.04，G-A3-1，G-A3-2，G-A3-3，A1.20

我希望你能帮助我解决这个问题。

- Daniel Schott

---

“Adjazenzen” 应该是邻接表吗？ - Crescent Fresh

是的，节点就是导航点。 - Daniel Schott

@Vivin Paliath，我将其更改为data.Adjazenzen[x].Von == start || data.Adjazenzen[x].Nach == start，因为start是一个字符串，它是在输入字段中输入并在单击时读取的。 - Daniel Schott

@Vivin Paliath 好的，没错。那么深度优先搜索会是更好的解决方案吗？ - Daniel Schott

@user2325235 你可能需要进行一些解析，才能获得数据的图形表示。没有任何图遍历算法能够在洗牌后的边缘列表上正常工作。 - G. Bach

Answer 1

我注意到的第一件事是，queue.push(...)和queue.pop()不会像您期望的那样工作，因为这时你使用的是一个栈，这意味着你正在进行深度优先搜索而不是广度优先搜索。

请记住，队列是一个FIFO容器。因此，请使用queue.push(...)（将元素添加到数组的末尾）和queue.shift()（从数组的前面删除元素）。基本上，shift()类似于队列上的dequeue()操作。

- Vivin Paliath