# Computer Science Exam Trees and Grpahs part 2

i know this is an exam and i cant get help but please ive been stuck for days at %67 here is the question

Complete the iterative bfs() (breadth-first search) function. This function takes in a graph, start_vert, and a target_val that it’s searching for, and should return the path if there is one. The graph is modeled using a Python dictionary. Within the dictionary, each key-value pair maps a vertex value to a set of that vertex’s connected vertex values as follows:
some_vertex_value: set([connected_value_1, connected_value_2, connected_value_3])

Most of the bfs() function has already been written, but you need to add in the iterative steps that occur if the current vertex’s neighbor hasn’t been visited.

## and here is my code

def bfs(graph, start_vert, target_val):
# Initialize the path with the starting vertex
path = [start_vert]
# Initialize the queue with the starting vertex and its path
bfs_queue = deque([[start_vert, path]])
visited = set() # Set to keep track of visited vertices

``````while bfs_queue:
# Dequeue the next vertex and path
current_vertex, path = bfs_queue.popleft()

# Skip if this vertex has already been visited
if current_vertex in visited:
continue

# Mark the vertex as visited

# Iterate over neighbors of the current vertex
for neighbor in graph[current_vertex]:
if neighbor not in visited:
# Create a new path by appending the neighbor to the existing path
new_path = path + [neighbor]
# Enqueue the neighbor and new path
bfs_queue.append([neighbor, new_path])

# Check if the neighbor is the target value
if neighbor == target_val:
return new_path

return None
``````

# Testing the function with a sample graph

the_most_dangerous_graph = {
‘lava’: {‘sharks’, ‘piranhas’},
‘sharks’: {‘lava’, ‘bees’, ‘lasers’},
‘piranhas’: {‘lava’, ‘crocodiles’},
‘bees’: {‘sharks’},
‘lasers’: {‘sharks’, ‘crocodiles’},
‘crocodiles’: {‘piranhas’, ‘lasers’}
}

# Test the function

result = bfs(the_most_dangerous_graph, ‘piranhas’, ‘bees’)
if result:
print(“Path found:”, result)
else:

and i keep getting this error,

Did you add the `neighbor` to the `path` and return it if it’s equal to `target_val`?

ive contacted support, submitted it as a bug, am i beign an idiot or something. i know i cant get direct answer but PLEASE can someone push me in the right direction

1 Like

At every point in your code, given a particular input, you should be able to trace out what should happen, do this on paper first and then…

run this locally and use a debugger (like with the breakpoint() feature or vs code debugger, whatever you prefer). At every juncture affirm that what you think is happening is in fact happening.

As long as the program is doing what you want it to do that’s a big step. Finally, you have to keep in the back of your mind and re-read the problem to make sure that what you want to do is what you have to do.

3 Likes