CODEWITHSUNDEEP
pythonbreadth-first-search
AndW
AndW

Reputation: 846

How do I return the length of the path found by Breadth First Search?

I'm trying to augment the typical BFS algorithm to also return the length of the path it found. Here's what I've written so far:

from collections import deque
length = 1
visited = set()
q = deque()
visited.add("Start")
while q:
    v = q.popleft()
    length += 1
    if v == "End":
        return length
    else:
        for neighbor in graph[v]:
            if neighbor not in visited:
                visited.add(neighbor)
                q.append(neighbor)

return 0

Here, I'm assuming a graph of strings. An example graph could be

graph = { "Start" : ["A"],
          "A" : ["B"],
          "B" : ["End"],
          "End" : []
          }

I understand that this is wrong as it will count the entire size of graph and not just the length of the path to the goal. How can I modify it to return the length of the path to the goal it found?

Upvotes: 1

Views: 689

Answers (1)

AndW
AndW

Reputation: 846

Based on the advice of @Karl Knechtel, I was able to write it!

from collections import deque
visited = set()
q = deque([("Start", 0)])
visited.add("Start")
while q:
    v, length = q.popleft()
    if v == "End":
        return length + 1
    else:
        for neighbor in graph[v]:
            if neighbor not in visited:
                visited.add(neighbor)
                q.append((neighbor, length + 1))

return 0

Upvotes: 3

Related Questions