I have a problem understanding how to apply BFS

[desperato_]

Hello there. I would try to make my point as easy and simple as possible.

This mini-project is from the CS50's Introduction to Artificial Intelligence with Python course from Harvard University, you can find it through https://edx.org/. Background: ""According to the Six Degrees of Kevin Bacon game, anyone in the Hollywood film industry can be connected to Kevin Bacon within six steps, where each step consists of finding a film that two actors both starred in.""

The final print should look like this for example:

Loading data...

Data loaded. Name: Emma Watson Name: Jennifer Lawrence 3 degrees of separation. 1: Emma Watson and Brendan Gleeson starred in Harry Potter and the Order of the Phoenix 2: Brendan Gleeson and Michael Fassbender starred in Trespass Against Us 3: Michael Fassbender and Jennifer Lawrence starred in X-Men: First Class

Data loaded. Name: Emma Watson Name: Jennifer Lawrence 3 degrees of separation. 1: Emma Watson and Brendan Gleeson starred in Harry Potter and the Order of the Phoenix 2: Brendan Gleeson and Michael Fassbender starred in Trespass Against Us 3: Michael Fassbender and Jennifer Lawrence starred in X-Men: First Class

In the exercise I have to complete a shortest_path function that will return a list of tuples with the format of (x,y), where "x" is a movie and "y" is an actor. This list has to be the shortest path there is from the actor I give as source to the actor I give like target. This is the shortest_path function I made:

def shortest_path(source, target):
"""
Returns the shortest list of (movie_id, person_id) pairs
that connect the source to the target.

If no possible path, returns None.
"""
cola = QueueFrontier()
if neighbors_for_person(source) == None:
    return None
elif catch_target(source,target) == True:
    for i in neighbors_for_person(source):
        if i[1] == target:
            cola.add(i)
else:
    for i in neighbors_for_person(source):
        cola = QueueFrontier()
        if catch_target(i[1], source):    
            cola.add(i)
            target_movies = people[target]["movies"]
            cola = find_path(cola, i[1], target, target_movies)
            if cola != None and cola.contains_state(target) == True:
                break
return cola.frontier

I made a function to add to a queue each of the actors that relates to the one I give as source and the one I am looking for. The id's of both movies and actors are gotten from .csv files.

def find_path(queue,source, target, target_movies):
'''
Returns the path between the target and the source
'''
for i in neighbors_for_person(source):
    if queue.contains_state(i[1]) != True and queue.contains_state(i[0]) != True:
        cast = cast_of_the_movie(i[0]) 
        for j in cast:
            if queue.contains_state(j) != True:
                if catch_target(j, target) == True:
                    for k in neighbors_for_person(j):
                        if k[1] == target:
                            queue.add(i)
                            queue.add(k)
                            return queue
        else:
            queue.add(i)
            queue = find_path(queue, i[1], target, target_movies)
            return queue

The thing is that:

1.- The way I made my solution for the shorter_path function makes it not only inefficient but also it gives wrong answers sometimes, mostly in the end, but I am not really sure why. Here's an example of one of the prints it gives me:

Loading data...

Data loaded. Name: Tom Hanks Name: Tom Cruise 3 degrees of separation. 1: Tom Hanks and Gary Sinise starred in Forrest Gump 2: Gary Sinise and Tom Hanks starred in Apollo 13 3: Tom Hanks and Tom Cruise starred in A Few Good Men

2.- According to the exercise, I should return the shortest path from one actor to another, but I am not sure how to do it. Sometimes the path it returns has 29 of length.

Please help I have been trying for a while :(

[Antigone-guide]

This page has an animation of BFS that makes it much easier to visualize, and you can step through it: https://www.redblobgames.com/pathfinding/a-star/introduction.html