如何在我修改的BFS程序中解决无限循环？

Question

我已经设置了一个代码，该代码将基于与节点之间的每个边缘相关联的值来导航图形。每条边都有一个与之相关的颜色和类型，如果颜色或类型与最后一种颜色或类型匹配，我应该只跟随BFS中的边。第一个颜色/类型由遵循的第一个边缘设置。但是，当我运行我的特定代码时，我在设置中的某个地方得到一个无法解决的infite循环。

我已经尝试设置不同的循环样式并使用迭代器而不是当前的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);
            }
        }
    }
}

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

Answer 1

标记您已经看过的节点，确保您不再访问它们（例如使用.state）：

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