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

Python
1

Tell us what’s happening:

I read the forum post about controlling the order of the result list and will deal with that next, but first, I can’t even get the tests to run. I added a print statement to check the creation/content of the result list and it seems right. Why won’t the tests run?

Your code so far

# am = [
#       [0, 1, 0, 0],
#       [1, 0, 1, 0],
#       [0, 1, 0, 1],
#       [0, 0, 1, 0]
#     ]

def dfs_adjacency_matrix(matrix, start):
    visited = [False] * len(matrix)
    dfs_helper(matrix, start, visited)
    node_list = []
    for i in range(len(visited)):
        if visited[i]:
            node_list.append(i)
    return node_list

def dfs_helper(matrix, node, visited):
    visited[node] = True
    for neighbor in range(len(matrix[node])):
        if matrix[node][neighbor] == 1 and not visited[neighbor]:
            dfs_helper(matrix, neighbor, visited)

print(dfs_adjacency_matrix([[0, 1, 0, 0], [1, 0, 1, 0], [0, 1, 0, 1], [0, 0, 1, 0]], 1))

Your browser information:

User Agent is: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/26.1 Safari/605.1.15 Ddg/26.1

Challenge Information:

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

2

The tests run for me, but they all fail.

3

You should focus on your own tests and getting the correct results first.

That said, what is the requirement of the first test?

Hm, the tests all failed for me as well, but I got this output:

// running tests
1. Your code raised an error before any tests could run. Please fix it and try again.
2. Your code raised an error before any tests could run. Please fix it and try again.
3. Your code raised an error before any tests could run. Please fix it and try again.
4. Your code raised an error before any tests could run. Please fix it and try again.
5. Your code raised an error before any tests could run. Please fix it and try again.
6. Your code raised an error before any tests could run. Please fix it and try again.
// tests completed
// console output
[0, 1, 2, 3]

Did you get this?

4

Yes, that’s the same output I got. So if there’s any information to be gleaned from failed tests, I can’t even get that far. I tested the other test cases and get the right content in my returned lists, although not in the right order when there’s more than one visited node. Any ideas on why the tests won’t even run?

5

What is the requirement of the first test?

7

I’ve updated the functions to pass and accept a list to which the nodes get appended as they’re visited. That gets part of it right, but the statement “for neighbor in range(len(matrix[node])):” always starts the search at node=0, which isn’t right. I changed it to start with node = node + 1, and added a second for loop that goes back to node=0 and searched up until node=node, getting all the right results, but still failing to run the tests even after removing the print statements.

    visited = [False] * len(matrix)
    node_list = []
    dfs_helper(matrix, start, visited, node_list)
    return node_list

def dfs_helper(matrix, node, visited, node_list):
    visited[node] = True
    node_list.append(node)    
    for neighbor in range(node + 1, len(matrix)):
        if matrix[node][neighbor] == 1 and not visited[neighbor]:
            dfs_helper(matrix, neighbor, visited, node_list)

    for neighbor in range(node):
        if matrix[node][neighbor] == 1 and not visited[neighbor]:
            dfs_helper(matrix, neighbor, visited, node_list)
8

What is User Story #1?

What is the requirement of the first test?

9

OMG. I can’t stand it when it’s a detail like that! Now it works.

2 Likes