1

I wrote the recursive code to get the path taken in a DFS traversal, but I want to get the output into a string variable. Recursion is not my strong suit so I'm having a lot of trouble figuring out the what to return. Here's the code I wrote for the algorithm

adj_lst = [None, [3, 4], [3], [1, 2], [1]]
size = len(adj_lst)
visited = [False] * size

def dfs(starting_node, a_lst, output):
    visited[starting_node] = True
    output += str(starting_node)

    for vertex in a_lst[starting_node]:

        if visited[vertex] == False:
            visited[vertex] = True
            dfs(vertex, a_lst, output)

    return output


print(dfs(1,adj_lst,''))

I give an adjacency list of an undirected graph where the index corresponds to the parent node and the list inside contains the child nodes. Every time a node gets visited, I add that node to the output variable and return it in the end.

In this case the desired output is "1 3 2 4" but what I get is "1"

buhtz
  • 10,774
  • 18
  • 76
  • 149
Mosheur Rahman Wolied
  • 13
  • 3
  • `for vertex in a_lst[starting_node]:` here is bug I think. You just look at the starting node, disregarding all the others – dankal444 Nov 02 '22 at 13:46
  • It is a bad idea to use recursion for DFS. It can be made to work for small graphs, but it is not saleable to large graphs since you run out of memory. Take a look ay DFS algorithms using a stack or queue which are both simpler and scalable to huge graphs. – ravenspoint Nov 02 '22 at 13:50
  • 1
    `dfs(vertex, a_lst, output)` - this won't return a result to the calling function. Try `return dfs(vertex, a_lst, output)`. – wwii Nov 02 '22 at 13:56
  • A good IDE will allow you to trace a recursive process. – wwii Nov 02 '22 at 13:58
  • [How to step through Python code to help debug issues?](https://stackoverflow.com/questions/4929251/how-to-step-through-python-code-to-help-debug-issues) If you are using an IDE **now** is a good time to learn its debugging features Or the built-in [Python debugger](https://docs.python.org/3/library/pdb.html). Printing *stuff* at strategic points in your program can help you trace what is or isn't happening. [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – wwii Nov 02 '22 at 13:58

1 Answers1

0
adj_lst = [None, [3, 4], [3], [1, 2], [1]]
size = len(adj_lst)
visited = [False] * size

def dfs(starting_node, a_lst, output):
    visited[starting_node] = True
    output += str(starting_node)

    for vertex in a_lst[starting_node]:
        if visited[vertex] == False:
            visited[vertex] = True
            output = dfs(vertex, a_lst, output)

    return output


print(dfs(1,adj_lst,''))
aramcpp
  • 339
  • 1
  • 8