Implement the Breath-First Search Algorithm

Python
1

Hello. I did Implement the Breath-First Search Algorithm. but it was simply doing what each step said. I did the workshop, but can’t really understand the code and why it is a BFS algorithm, can anyone explain what the code does? (the indentation is wrong because I copied from fCC, sorry)

def gen_parentheses(pairs):

    if not isinstance(pairs, int):

return 'The number of pairs should be an integer'

if pairs < 1:

return 'The number of pairs should be at least 1'

    queue = [('', 0, 0)]

    result = []

while queue:

        current, opens_used, closes_used = queue.pop(0)

if len(current) == 2 * pairs:

            result.append(current)

else:

if opens_used < pairs:

                queue.append((current + '(', opens_used + 1, closes_used))

if closes_used < opens_used:

                queue.append((current + ')', opens_used, closes_used + 1))

return result

(sorry if i should’ve not sent the code, I sent it because it’s available on the website by choosing the step, so probably not really spoiling it.)

2

This would be a great learning exercise for you.

Look up what that algorithm is and get a good understanding of it, and then look at the code and try to understand how it works.

You can try changing parts of it if you need to experiment to understand how it reacts.

If you have more specific questions you should definitely ask here.

However, everything you’ve implemented here has been described in previous lessons. Feel free to go back and read about it if you need a refresher (you are no expected to remember everything the first time)

3

understood it. thanks.

1 Like