Why isnt my for loop breaking while Depth First Search

Question

I'm doing a depth first search with python. To do this a have a graph with some values which I have to show the path to, with a given initial place, reach the final destination

visited = set()

def dfs(visited, graph, initial, final):
    if initial not in visited:
        print (initial)
        visited.add(initial)
        for neighbour in graph[initial]:
            if(final == initial):
                print("a")
                break
            dfs(visited, graph, neighbour, final)
    return visited

dfs(visited, graph, 'arad', 'lugoj')

The problem is with the if inside for. I wanna break it when the my final place is equal to the current for place ( it means I reach my destination), and return back a list with the path to reach it. But it does not break and doesnt return anything, the only value showed in console is the prints inside method. This is the console:

arad
timisoara
lugoj
a
sibiu
oradea
zerind
rimnicu vilcea
craiova
pitesti
bucharest
fagaras
giurgiu
urziceni
vaslui
lasi
neamt
hirsova
eforie
dobreta
mehadia

As you can see, it had to break in 'a'.

How can I handle this?

##UPDATE

{'timisoara', 'pitesti', 'eforie', 'lasi', 'craiova', 'mehadia', 'arad', 'urziceni', 'lugoj', 'neamt', 'dobreta', 'zerind', 'giurgiu', 'rimnicu vilcea', 'bucharest', 'fagaras', 'sibiu', 'vaslui', 'hirsova', 'oradea'}

GRAPH

#DEPTH_FIRST_SEARCH
graph = {
    'oradea' : ['zerind','sibiu'],
    'zerind' : ['arad', 'oradea'],
    'arad' : ['timisoara', 'sibiu', 'zerind'],
    'timisoara' : ['lugoj', 'arad'],
    'lugoj' : ['mehadia', 'timisoara'],
    'mehadia' : ['dobreta', 'lugoj'],
    'dobreta' : ['craiova', 'mehadia'],
    'craiova' : ['pitesti', 'rimnicu vilcea', 'dobreta'],
    'rimnicu vilcea' : ['craiova', 'pitesti', 'sibiu', ],
    'sibiu' : ['oradea', 'arad', 'rimnicu vilcea', 'fagaras'],
    'fagaras' : ['sibiu', 'bucharest'],
    'pitesti' : ['rimnicu vilcea', 'craiova', 'bucharest'],
    'bucharest' : ['fagaras', 'pitesti', 'giurgiu', 'urziceni'],
    'giurgiu' : ['bucharest'],
    'urziceni' : ['bucharest', 'vaslui', 'hirsova'],
    'vaslui' : ['lasi', 'urziceni'],
    'lasi' : ['neamt', 'vaslui'],
    'hirsova' : ['urziceni', 'eforie'],
    'eforie' : ['hirsova'],
    'neamt' : ['lasi']
}

Answer 1

The problem is that you only break out of the loop in the recursive call, not the callers.

Since you're modifying visited in place, there's no need to return it.

Instead, you can return a boolean that indicates whether final was found, and the caller can break out of their loop as well.

Also, final and initial don't change during the loop, so there's no need to compare them there. Do it before the loop.

def dfs(visited, graph, initial, final):
    if initial not in visited:
        print (initial)
        visited.add(initial)
        if(final == initial):
            print("a")
            return True
        for neighbour in graph[initial]:
            if dfs(visited, graph, neighbour, final):
                return True
    return False