时间戳

首页 > 解决方案 > 如何解决我修改后的 BFS 程序中的无限循环？

c++ - 如何解决我修改后的 BFS 程序中的无限循环？

问题描述

我已经设置了一个代码，它将根据与节点之间的每条边相关联的值来导航图表。每条边都有一个与之关联的颜色和类型，如果颜色或类型与最后一个颜色或类型匹配，我应该只跟随我的 BFS 中的一条边。第一个颜色/类型由后面的任何第一个边设置。但是，当我运行我的特定代码时，我在设置中的某个地方出现了一个无法解决的无限循环。

我尝试设置不同的循环样式并使用迭代器而不是当前的 for 循环遍历我的列表，两者都不起作用并且都导致相同的错误。

队列 Q；

Q.push(neededNode);
string lastType = "";
string lastColor = "";
while (!Q.empty()){
    node u = Q.front();
    Q.pop();
    for(auto& itr : adjacencyList[u.city]){ //cycle through the adjacency list
        for (auto& entry: nodeList){ //find the node for the entry
            if (entry.city == (itr).city){
                //Initial condition for setting color/type to follow
                if(lastType == "" || lastColor == ""){
                    lastColor = (itr).color;
                    lastType = (itr).type;
                    entry.state = true;
                    entry.distance = u.distance +1;
                    entry.parent = u.city;
                    cout << u.city << " " << lastColor << " " << lastType << endl;
                //If Types match
                }else if(lastType == (itr).type){
                    lastColor = (itr).color;
                    lastType = (itr).type;
                    entry.state = true;
                    entry.distance = u.distance +1;
                    entry.parent = u.city;
                    cout << u.city << " " << lastColor << " " << lastType << endl;
                //If colors match
                }else if(lastColor == (itr).color){
                    lastColor = (itr).color;
                    lastType = (itr).type;
                    entry.state = true;
                    entry.distance = u.distance +1;
                    entry.parent = u.city;
                    cout << u.city << " " << lastColor << " " << lastType << endl;
                }
                Q.push(entry);
            }
        }
    }
}

理想情况下，代码应该运行并在完成后停止运行，并且我应该能够跟随父值到正确的路径。目前，我得到一个无限循环。

标签： c++breadth-first-search

解决方案

标记您已经看到的节点，以确保您不会再次（一次又一次）访问它们，例如使用您的 .state：

if (entry.city == (itr).city && !entry.state) {
    //Initial condition for setting color/type to follow

推荐阅读