Как разрешить бесконечный цикл в моей модифицированной программе BFS?

Question

Я установил код, который будет перемещаться по графику на основе значений, связанных с каждым ребром между узлами. Каждое ребро имеет связанный с ним цвет и тип, и я должен следовать за ребром в моей 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);
            }
        }
    }
}

В идеале код должен запускаться и останавливаться после завершения, и я должен иметь возможность следовать родительским значениям по правильному пути. В настоящее время я получаю бесконечный цикл.

Answer 1

Отметьте узлы, которые вы уже видели, чтобы убедиться, что вы не посещаете их снова (и снова), например, используя .state:

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