Implement the Depth-First Search Algorithm - Implement the Depth-First Search Algorithm

Python
1

Tell us what’s happening:

I can’t pass the last case and I’m not sure why. I believe it may have something to do with the formatting of the list that’s returned?

Your code so far

visited = []

def dfs(matrix, node):
    if node not in visited:
        visited.append(node)

        for i, neighbor in enumerate(matrix[node]):
            if neighbor == 1 and i not in visited:
                dfs(matrix, i)
            
    return visited

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:150.0) Gecko/20100101 Firefox/150.0

Challenge Information:

Implement the Depth-First Search Algorithm - Implement the Depth-First Search Algorithm

Github Link: freeCodeCamp/curriculum/challenges/english/blocks/lab-depth-first-search/68d275dd800f404d22a07564.md at main · freeCodeCamp/freeCodeCamp · GitHub

2

Take a look what happens when running dfs more than once. These are test cases from 4th and 6th test:

print(dfs([[0, 1, 0, 0], [1, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 0]], 3))
print(dfs([[0, 1, 0, 0], [1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0]], 0))
3

Odd, is there a way to do this without using a global variable?

4

There must be :slight_smile:.

One approach is to add another layer within the dfs, which would create and contain new visisted list, with each initial call to dfs. Another is looking at how visited list could be passed around as parameter, once again, after that initial call, which should use fresh list.