BFS, используя отладку имплантации смежного списка

Я пытаюсь отладить алгоритм BFS, используя соседний список. Он будет правильно печатать до определенной точки, а затем перейдет в бесконечный цикл. Я сделал несколько распечаток и заметил, что он в конечном итоге зацикливается на первых двух узлах графа. Я не уверен, где в моем коде это вызывает эту проблему. Это назначение мне было дано, и это мое последнее средство. Если кто-то и может указать мне правильное направление относительно того, в чем может быть проблема, это очень поможет.

void bfsList(linkedList adjList[], int visit[], int j){
Queue queue(24);
if (visit[j] == 0){
cout << j+1 << endl;
visit[j] = 1;
queue.enqueue(j);
while(!queue.isEmpty()){
int k = queue.dequeue();
//queue.print();
for(int i=0;i<adjList[k].len();i++){
if (visit[adjList[k].elementAt(i)-1]==0){
cout << adjList[k].elementAt(i) << endl;
visit[adjList[k].elementAt(i)-1] = 1;
}
if (!queue.isFull()){
queue.enqueue(adjList[k].elementAt(i)-1);
}
}
}
}
}

0

Решение

Поставьте в очередь, только если узел не посещен.

if (visit[adjList[k].elementAt(i)-1]==0){
cout << adjList[k].elementAt(i) << endl;
visit[adjList[k].elementAt(i)-1] = 1;

if (!queue.isFull()){
queue.enqueue(adjList[k].elementAt(i)-1);
}

}
0

Другие решения

queue.enqueue(adjList[k].elementAt(i)-1);

должен зависеть, был ли узел посещен.
непроверенные:

if (!queue.isFull() && !visit[adjList[k].elementAt(i)-1]){
queue.enqueue(adjList[k].elementAt(i)-1);
}
0

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector