Реализация BFS не работает должным образом

Приведенный код дает 10. С несколькими изменениями, вот живой пример. Одна модификация заключается в том, что вход x, y устанавливается в качестве отправной точки, я думаю, что это было намерение, как указал Джонатан Леффлер выше. Вторая модификация заключается в том, что теперь происходит проверка диапазона до вставка в очередь, поэтому цикл while изменяется следующим образом:

    while(!search_queue.empty())
{
node top = search_queue.front();
search_queue.pop();

if (visited[top.x][top.y]) continue;
if (map[top.x][top.y] == 1) continue;
visited[top.x][top.y] = true;
result++;
node temp;

temp.y = top.y;

if (top.x < 3)
{
temp.x = top.x + 1;
search_queue.push(temp);
}

if (top.x > 0)
{
temp.x = top.x - 1;
search_queue.push(temp);
}

temp.x = top.x;

if (top.y < 3)
{
temp.y = top.y + 1;
search_queue.push(temp);
}

if (top.y > 0)
{
temp.y = top.y - 1;
search_queue.push(temp);
}
}

Теперь, предполагая, что начальная точка находится в пределах диапазона (и вы можете добавить еще одну проверку для этого), этот цикл всегда будет перемещаться в пределах диапазона и никогда не будет помещать точку вне диапазона в очередь, сохраняя ряд вычислений.

Кроме того, поскольку ваши условия изначально написаны, вы получаете доступ к массивам visited а также map до проверка диапазона, которая может иметь плохие результаты.

Наиболее важно, если ваша цель заключается в find the shortest path through this map, то этот алгоритм не подходит. Число 10 это количество всех позиций, которые можно посетить, начиная с (0, 0). Это не самый короткий путь в никуда. Вам нужен алгоритм кратчайшего пути, и, поскольку веса графа здесь положительны, простой вариант Алгоритм Дийсктра.

Для этого требуется всего несколько модификаций вашего кода, но я оставляю это вам. В основном вам нужно будет заменить массив visited целочисленным массивом distance обозначение минимального расстояния до каждой точки от начальной позиции, инициализируется до «бесконечности» и только уменьшается. И ваша очередь должна быть заменена приоритетной, так что точки посещаются с увеличением расстояния.

Ваш код просто подсчитывает количество доступных ячеек. Я предполагаю, что вы хотите считать только ячейки между началом и концом ( result переменная бесполезна в этом контексте). Я обычно использую такую ​​структуру данных:

std::queue<pair<node,int> > search_queue;

Когда вы извлекаете элемент из очереди, код выглядит так:

    node top = search_queue.front().first;
int current_length = search_queue.front().second;
// if (top == end) return current_length;  (this is the value you are interested in)

Добавление следующих элементов в очередь, конечно, будет выглядеть так:

    search_queue.add(make_pair(temp, current_length + 1));

Я надеюсь, что полный код легко получить отсюда.

Я думаю, что вы должны отладить результат присваивания класса «узел».
Это, вероятно, не работает.

Для этого вы можете перегрузить оператор «=» и добавить конструктор по умолчанию со ссылочным аргументом типа «узел».

другой метод

class Queue:
def __init__(self):
self.items=[]
def enqueue(self,item):
self.items.append(item)
def dequeue(self):
return self.items.pop(0)
def isEmpty(self):
return self.items==[]
def size(self):
return len(self.items)

class Vertex:
def __init__(self,id):
self.id=id
self.color="white"self.dist=None
self.pred=None
self.sTime=0
self.fTime=0
self.connectedTo={}

def addNeighbor(self,nbr,weight):
self.connectedTo[nbr]=weight
def __str__(self):
return str(self.id)+"connectedTo"+str([x for x in self.connectedTo])
def getConnection(self):
return self.connectedTo.keys()
def getId(self):
return self.id
def getWeight(self,nbr):
return self.connectedTo[nbr]
def setColor(self,c):
self.color=c
def getColor(self):
return self.color
def setDistance(self,d):
self.dist=d
def getDistance(self):
return self.dist
def setPred(self,u):
self.pred=u
def getPred(self):
return self.pred
def getsTime(self):
return self.sTime
def getfTime(self):
return self.fTime
def setsTime(self,t):
self.sTime=t
def setfTime(self,t):
self.fTime=t

class Graph:
def __init__(self):
self.vertList={}
self.numVertices=0
self.time=0
def addVertex(self,id):
self.numVertices=self.numVertices+1
newVertex=Vertex(id)
self.vertList[id]=newVertex
def getVertex(self,id):
if id in self.vertList:
return self.vertList[id]
else:
return None
def __contains__(self,id):
return id in self.vertList
def addEdge(self,u,v,weight=0):
if u not in self.vertList:
self.addVertex(u)
if v not in self.vertList:
self.addVertex(v)
self.vertList[u].addNeighbor(self.vertList[v],weight)
def getVertices(self):
return self.vertList.keys()
def __iter__(self):
return iter(self.vertList.values())
def bfs(self,start):
self.vertList[start].setDistance(0)
self.vertList[start].setColor("gray")
q=Queue()
q.enqueue(self.vertList[start])
while(q.size()>0):
u=q.dequeue()
u.setColor("black")
for v in u.connectedTo:
if v.getColor()=="white":
v.setColor("gray")
v.setDistance(u.getDistance()+1)
v.setPred(u)
q.enqueue(v)

print"Id ",u.getId()," color ",u.getColor()," Distance ",u.getDistance()