Computer Science Exam Trees and Grpahs part 2

Computer Science
1

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
    visited.add(current_vertex)
   
    # 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 if the target value was not found
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:
print(“Path not found”)

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
2

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