-1
\$\begingroup\$

there are some problems in this code that I can't think of a solution. It does work for print(real_path,count) but the real thing I want is return real_path,count and for doing this I need to make the recursive function recurse flawless in the for loop which seems like it is impossible. I hope you can help me!

    path = {
    'a':['b','c'],
    'b':['d','f'],
    'c':['d','e'],
    'd':[],
    'e':['f']
}
#the goal is reaching the point f
def bfs(start,destination,map,count,real_path):
    a = map[start]
    del map[start]
    try:
        if count == 0:
            real_path.append(start)
        if destination in a:
            count+=1
            print(real_path,count)
        else:
            for i in a:
                bfs(i,destination,map,count+1,real_path+[i])
    except:
        return None

print(bfs('a','f', path,0, []))
\$\endgroup\$

2 Answers 2

4
\$\begingroup\$
#the goal is reaching the point f

Turn this comment into a docstring, preferably with some description about the arguments it expects too.


def bfs(start,destination,map,count,real_path):
    a = map[start]
    del map[start]

PEP-8 advises you to append a single trailing underscore to identifiers to avoid naming conflictions with keywords, and whilst map isn't a keyword, I'd suggest using the same convention for builtins too.

By that, map should be map_. Or use a different term altogether.


You don't want the function to execute if another module imports it. Consider using the main guard:

if __name__ == "__main__":
    bfs()

Also consider using ruff or black to format the code automatically.

\$\endgroup\$
4
\$\begingroup\$

Advice I - incorrectness

Your print(bfs('a','f', path,0, [])) prints None, so your implementation is plain wrong.

Advice II - no recursion please

Basically, you have a depth-first search.

Advice III - graph data structure

In your graph data structure, you represent all neighborhoods of nodes as a list. I suggest you convert those lists to set()s. That is faster in the case where you check whether a node \$u\$ is a child of \$v\$.

Summa summarum

All in all, I had this rewrite in mind:

from collections import deque

path = {
    'a':['b','c'],
    'b':['d','f'],
    'c':['d','e'],
    'd':[],
    'e':['f']
}

graph = {
    'a': {'b', 'c'},
    'b': {'d', 'f'},
    'c': {'d', 'e'},
    'd': {},
    'e': {'f'},
    'f': {},
}

def bfs(start,destination,map,count,real_path):
    a = map[start]
    del map[start]
    try:
        if count == 0:
            real_path.append(start)
        if destination in a:
            count += 1
        else:
            for i in a:
                bfs(i,destination,map,count+1,real_path+[i])
    except:
        return None


def traceback_path(node, parents):
    p = []
    while node:
        p.append(node)
        node = parents[node]
    p.reverse()
    return p


def real_bfs(source, target, graph):
    queue = deque([source])
    parents = {source: None}

    while queue:
        v = queue.popleft()
        if v == target:
            return traceback_path(v, parents)
        for u in graph[v]:
            if u not in parents.keys():
                parents[u] = v
                queue.append(u)
    return None


print(bfs('a','f', path,0, []))
print(real_bfs('a', 'f', graph))

Prints:

None
['a', 'b', 'f']
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.