CODEWITHSUNDEEP
pythonbreadth-first-search
duk
duk

Reputation: 744

Breadth first search wrong output

teren = [
    '########',
    '#s.....#',
    '###..#.#',
    '#...##.#',
    '#.#....#',
    '#.####.#',
    '#......#',
    '###e####'
    ]

def bfs(teren, start, end):
    queue = []
    visited = []
    queue.append([start])

    while queue:
        path = queue.pop()
        node = path[-1]

        x = node[0]
        y = node[1]

        if node == end:
            return path
        if node in visited or teren[x][y] == "#":
            continue

        visited.append(node)

        for adjacent in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)

print(bfs(teren, (1,1), (7, 3)))

This is the code i used to try and navigate this maze type thing, this is the output i get [(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 6), (3, 6), (4, 6), (4, 5), (4, 4), (4, 3), (3, 3), (3, 2), (3, 1), (4, 1), (5, 1), (6, 1), (6, 2), (6, 3), (7, 3)] while this is the output i need [(1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), (4, 1), (5, 1), (6, 1), (6, 2), (6, 3), (7, 3)]

It seems this is printing out all the walkable coordinates, but I have no idea how to fix that, all the examples online that use grids focus to much on drawing the grid which clutters the actual bfs.

Upvotes: 0

Views: 66

Answers (1)

trincot
trincot

Reputation: 351208

You will get the output you look for if you treat your queue as a queue. This means you don't pop the last element off, but you shift out the first:

replace:

 path = queue.pop()

with:

 path, queue = queue[0], queue[1:]

or:

 path = queue.pop(0)

However deque-objects are better suited for such operations:

from collections import deque

def bfs(teren, start, end):
    queue = deque([])
    visited = []
    queue.append([start])

    while queue:
        path = queue.popleft()
        # ...etc.

Upvotes: 4

Related Questions