Confused about DFS algorithm in action (not an issue with the pseudocode)

[shivajikobardan]

Homework Statement

Depth first search

Relevant Equations

there is a pseudocode below.

The DFS in action doesn't relate to the pseudocode as you can see it. My confusion starts from dfs in action, step 4. I could write essay about it, but you can see it yourself as well and spot that algorithm and dfs in action doesn't match up properly. or is it only me?

This is not a homework, SO I don't know what attempt I need to do. But I got confused and I think this fits here. So..
Full slide is here-:

https://slidetodoc.com/tree-and-graph-traversal-algorithms-breadthfirst-search-bfs/

 

[Mark44]

The algorithm shown is recursive. Starting at the root (node 7), it calls itself on each child node, starting with node 19. At node 19, it calls itself again for each child node, starting at node 1.
Since node 1 doesn't have any children, the function returns to its caller and prints the value at node 1 -- 1. At this point, the current node is the 19 node, which has another child node -- node 12. The function calls itself and visits node 12. Since node 12 has no children, the value at this node is printed -- 12, and the function returns, back to node 19. Node 19 has one more child, so the function calls itself once more to visit node 1. This node has no children, so its value gets printed -- 1.

The function returns, back to node 19, which has no more children, so its value gets printed -- 19. The function returns back to the root, node 7, which has two more children, and continues on in the same fashion to exhaust the tree, going all the way down each branch to the leaf nodes (the nodes that don't have children).

The order of traversal here is 1, 12, 31, 19, 21, 23, 6, 14, 7, the same as shown in the slide.

If it helps, here is a Python implementation that is an elaboration of the algorithm in your slide. I found this code at https://favtutor.com/blogs/depth-first-search-python, but have modified it in a few places. The graph dictionary exactly duplicates the tree shown in your slide, and the output order of traversal is the same as shown above.

# Python dictionary to act as an adjacency list
graph = {
  '7' : ['19','21', '14'],
  '19': ['1', '12', '31'],
  '21': [],
  '14': ['23', '6'],
  '1' : [],
  '12': [],
  '31': [],
  '23': [],
  '6' : []
}

visited = [] # List of visited nodes of graph.

def dfs(visited, graph, node): 
     """ Depth-first search
     visited - list of nodes that have been visited
     graph - the graph (a dictionary) of nodes and their neighbor nodes
     node - the current node
    """
    if node not in visited:
        visited.append(node)
        for neighbor in graph[node]:
            dfs(visited, graph, neighbor)
        print(node)

# Driver Code
print("Following is the Depth-First Search")
dfs(visited, graph, '7')
print(visited)

 

[shivajikobardan]

The order of traversal here is 1, 12, 31, 19, 21, 23, 6, 14, 7, the same as shown in the slide.

IDK if I am wrong or right. but IMO order of traversal of dfs should be 7,19,1,12,31,21,14,23,6

If it helps, here is a Python implementation that is an elaboration of the algorithm in your slide. I found this code at https://favtutor.com/blogs/depth-first-search-python, but have modified it in a few places. The graph dictionary exactly duplicates the tree shown in your slide, and the output order of traversal is the same as shown above.

# Python dictionary to act as an adjacency list
graph = {
  '7' : ['19','21', '14'],
  '19': ['1', '12', '31'],
  '21': [],
  '14': ['23', '6'],
  '1' : [],
  '12': [],
  '31': [],
  '23': [],
  '6' : []
}

visited = [] # List of visited nodes of graph.

def dfs(visited, graph, node):
     """ Depth-first search
     visited - list of nodes that have been visited
     graph - the graph (a dictionary) of nodes and their neighbor nodes
     node - the current node
    """
    if node not in visited:
        visited.append(node)
        for neighbor in graph[node]:
            dfs(visited, graph, neighbor)
        print(node)

# Driver Code
print("Following is the Depth-First Search")
dfs(visited, graph, '7')
print(visited)

this arouse me lots of confusions..

i will try to connect ppt to code

ppt========> program

stack=======>?

output=======>node (what does this mean? the output should be traversal as I said above am I missing sth?)

not given=======>actual answer ie visited. this too makes little sense to me..and is confusing from my previous experience with bfs.

looks like i need to stop doing this and learn the iterative approach where queue of bfs is replaced by stack..still learning this would be a huge milestone.

edit-: I forgot to ask..if I add goal state and search for it. which part of code will change

# Python dictionary to act as an adjacency list
graph = {
  '7' : ['19','21', '14'],
  '19': ['1', '12', '31'],
  '21': [],
  '14': ['23', '6'],
  '1' : [],
  '12': [],
  '31': [],
  '23': [],
  '6' : []
}
visited = [] # List of visited nodes of graph.
goal="23"
def dfs(visited, graph, node):
    if(node==goal):
        print("end goal found ",node)
        exit()
    if node not in visited:
        visited.append(node)

    for neighbor in graph[node]:
        dfs(visited, graph, neighbor)
    print(node)
# Driver Code
print("Following is the Depth-First Search")
dfs(visited, graph, '7')
print("visited=",visited)

 

[pbuk]

Edit: the code posted here does not work as @Mark44 points out below; I don't think fixing it is germane to the topic of the thread (I wish I hadn't posted it in the first place ).

Passing (a pointer to) an empty list to act as a return value is a C idiom that is out of place in Python code. A more Pythonic implementation would be:

def dfs(graph, node):
     """ Depth-first search
     graph - the graph (a dictionary) of nodes and their neighbor nodes
     node - the current node
    """
    # Start with an empty list of visited nodes of graph.
    visited = []
    if node not in visited:
        visited.append(node)
        for neighbor in graph[node]:
            dfs(visited, graph, neighbor)
        print(node)

    # Return the populated list.
    return visited

# Driver Code
print("Following is the Depth-First Search")
visited = dfs(graph, '7')
print(visited)

 

[Mark44]

Passing (a pointer to) an empty list to act as a return value is a C idiom that is out of place in Python code.

Blame the guy whose code I cribbed.
BTW, you forgot to delete the visited parameter in the recursive call to dfs().

 

[pbuk]

BTW, you forgot to delete the visited parameter in the recursive call to dfs().

Oops, good point. In this case we can't easily use a return value and your code is probably the simplest (although not necessarily best) solution. I will follow up when I'm back at a proper keyboard.

 

[Mark44]

IDK if I am wrong or right. but IMO order of traversal of dfs should be 7,19,1,12,31,21,14,23,6

You are correct. The order of traversal is as you wrote. The list that I wrote shows the order in which the Python dfs() implementation prints the nodes, which is not the same as the traversal order.

In a nutshell, what the code does is to look at a node. If the node has a child, it looks at that node, and continues in this way until it finds a node that has no child.
The code I showed starts at node 7, the root, visits node 19, then visits node 1. Since node 1 doesn't have any children (it's a leaf node), the code prints 1.

The code then goes to node 12, another child of node 19. Node 12 is a leaf node, so the code prints 12.

The code then goes to node 31, the last child of node 19, and prints 31, since node 31 is also a leaf node.

The code then goes back up to node 19, and prints its value. At this point, the subtree headed by the 19 node has been completely traversed, and the code continues on to the other two subtrees under the root node.

The order in which the nodes are printed is 1 12 31 19 21 23 6 14 7
The order of traversal is 7 19 1 12 31 21 14 23 6

 

[Mark44]

stack=======>?

The dfs() function is recursive, as opposed to the bfs() routine described in the PPT slide deck in the link you provided. When a recursive function calls itself, it pushes its parameters and other information onto the stack. In most programming languages, this is something that happens below the surface, that programmers don't have access to.

In contrast, the bfs() algorithm shown in the slide deck uses iteration rather than recursion to loop through a queue of nodes. With a loop, the stack isn't involved.

output=======>node (what does this mean? the output should be traversal as I said above am I missing sth?)

The numbers shown in your slide of the tree are not the order of traversal -- they represent the order in which node values are printed. I hope that my explanation in my previous post clears up the difference between traversal order and order in which node values are printed.

 

[shivajikobardan]

Edit: the code posted here does not work as @Mark44 points out below; I don't think fixing it is germane to the topic of the thread (I wish I hadn't posted it in the first place ).

Passing (a pointer to) an empty list to act as a return value is a C idiom that is out of place in Python code. A more Pythonic implementation would be:

def dfs(graph, node):
     """ Depth-first search
     graph - the graph (a dictionary) of nodes and their neighbor nodes
     node - the current node
    """
    # Start with an empty list of visited nodes of graph.
    visited = []
    if node not in visited:
        visited.append(node)
        for neighbor in graph[node]:
            dfs(visited, graph, neighbor)
        print(node)

    # Return the populated list.
    return visited

# Driver Code
print("Following is the Depth-First Search")
visited = dfs(graph, '7')
print(visited)

indentation doesn't correct..can you send the code that you ran in your laptop?

 

[shivajikobardan]

The code I showed starts at node 7, the root, visits node 19, then visits node 1. Since node 1 doesn't have any children (it's a leaf node), the code prints 1.

The code then goes to node 12, another child of node 19. Node 12 is a leaf node, so the code prints 12.

Can you explain this
visited=7,19,1 upto here dry run makes sense.(IMO this should be a different question as it is related to programming basics, but I hope this thread is ok as well)
Then as you can see the code is-:

# Python dictionary to act as an adjacency list
graph = {
  '7' : ['19','21', '14'],
  '19': ['1', '12', '31'],
  '21': [],
  '14': ['23', '6'],
  '1' : [],
  '12': [],
  '31': [],
  '23': [],
  '6' : []
}

visited = [] # List of visited nodes of graph.
def dfs(visited, graph, node):
    
    if node not in visited:
        visited.append(node)    for neighbor in graph[node]:
        dfs(visited, graph, neighbor)
    print(node)

# Driver Code
print("Following is the Depth-First Search")
dfs(visited, graph, '7')
print("visited=",visited)

imo as soon as your print(1) the code should end here. How does it continues to go to 12? I know it is a basic question but still asking as I don't understand. I was at first confused at the same thing(with pseudocode).
is there sth different that happens in recursion?

 

[Mark44]

Then as you can see the code is-:

What you copied above isn't really the code, per se. It's the data that the code uses -- it is a dictionary data structure that tells which nodes are adjacent to (meaning, children of) the nodes that are keys in the dictionary.

imo as soon as your print(1) the code should end here. How does it continues to go to 12? I know it is a basic question but still asking as I don't understand. I was at first confused at the same thing(with pseudocode).

This is a good question, and not really all that basic. Students often struggle when they're trying to understand recursion. To answer the question, you need to understand how recursion works. In the code for dfs(), nothing gets printed until the code reaches a node without any children or if all children of a parent node have already been processed.

The heart of the implementation is this loop:

for neighbor in graph[node]:
      dfs(visited, graph, neighbor)
print(node, end=' ')

graph[node] accesses the graph dictionary. node is a key in the dictionary, and graph[node] is the value associated with that key -- a list of nodes that are children of node.

The for loop above iterates through the list of child nodes, and for each one it calls dfs(). When the list of child nodes is exhausted, the code returns, going back to the parent node. The only time a value is printed is when a node is a child node, or if all of the child nodes of a node have been visited. Another way to look at it is that a node's value gets printed only when the code returns from a call to dfs().

For the tree in this thread, here's what happens for the left-most subtree:
The code starts with node 7.
Node 7 has three children, so graph[node] == ['19', '21', '14']
The for loop calls dfs() on the 19 node.
Node 19 also has three children, so graph[node] == ['1', '12', '31']
The for loop calls dfs() on the 1 node.
Node 1 has no children, so the for loop doesn't execute, and the code prints 1.
The code returns to the 19 node.
The next child of the 19 node is node 12.
Node 12 has no children, so the for loop doesn't execute, and the code prints 12.
The code returns to the 19 node.
The next child of the 19 node is node 31.
Node 31 has no children, so the for loop doesn't execute, and the code prints 31.
The code returns to the 19 node. All of its children have been visited, so the code prints 19.
At this point, the left subtree has been processed.
The code returns to the 7 node, and in a like manner processes the middle subtree, and the right subtree, and eventually processes the root of the tree, node 7.I added a few lines of code to what I posted previously to help explain what the code does. The extra lines I added keep track of how many times dfs() gets called, and when this function returns to its caller (which most of the time is itself).

Call to dfs() #1, node = 7
Call to dfs() #2, node = 19
Call to dfs() #3, node = 1
Returning from dfs()
1
Call to dfs() #4, node = 12
Returning from dfs()
12
Call to dfs() #5, node = 31
Returning from dfs()
31
Returning from dfs()
19
Call to dfs() #6, node = 21
Returning from dfs()
21
Call to dfs() #7, node = 14
Call to dfs() #8, node = 23
Returning from dfs()
23
Call to dfs() #9, node = 6
Returning from dfs()
6 Returning from dfs()
14 Returning from dfs()
7

Hope this helps.

 

[pbuk]

indentation doesn't correct..can you send the code that you ran in your laptop?

There was more to it than just indentation. Anyway I have looked at this again, those slides are terrible. Here is some code that attempts to explain it better (edited with some improvements regarding pre/postordering etc.

# The slide is called 'depth first search' but the code actually
# performs a traversal, not a search, so I have named it accordingly
# also respecting the convention that function names should be verbs
# (and so not depthFirstTraversal).
def traverseDepthFirst(graph, nodeIndex, visited = []):
    """ Recursively traverse a graph depth first.

    Returns a preordered list of the indices of visited nodes.

    graph - the graph (a list) of nodes; each node is a dict with
            entries 'value' and 'children'.
    nodeIndex - the index of the current node.
    """

    # If we have already visited the node the graph must be recursive
    # which is not allowed for a simple graph.
    if nodeIndex in visited:
        raise Exception('The graph must not be recursive')

    node = graph[nodeIndex]

    # For a preordered list append now and print it if you want to.
    visited.append(nodeIndex)
    # print('Pre', node['value'])

    for childIndex in node['children']:
        traverseDepthFirst(graph, childIndex, visited)

    # For a postordered list append now and print it if you want to.
    # visited.append(nodeIndex)
    # The original code printed a postordered list so we will do the
    # same.
    print('Post', node['value'])

    # Return the populated list.
    return visited

Here is a demonstration, using the same graph as in the slides:

testGraph = ([
    None, # Node 0: not used.
    {'value': 1, 'children': []}, # Node 1.
    {'value': 12, 'children': []}, # Node 2.
    {'value': 31, 'children': []}, # Node 3.
    {'value': 19, 'children': [1, 2, 3]}, # Node 4.
    {'value': 21, 'children': []}, # Node 5.
    {'value': 23, 'children': []}, # Node 6.
    {'value': 6, 'children': []}, # Node 7.
    {'value': 14, 'children': [6, 7]}, # Node 8.
    {'value': 7, 'children': [4, 5, 8]}, # Node 9.
])

# Traverse the graph starting at the head (node 9).
traversed = traverseDepthFirst(testGraph, 9)
print(traversed)
for i in traversed:
    print('Node', i, ':', testGraph[i]['value'])

Which outputs:

Post 1
Post 12
Post 31
Post 19
Post 21
Post 23
Post 6
Post 14
Post 7
[9, 4, 1, 2, 3, 5, 8, 6, 7]
Node 9 : 7
Node 4 : 19
Node 1 : 1
Node 2 : 12
Node 3 : 31
Node 5 : 21
Node 8 : 14
Node 6 : 23
Node 7 : 6

 

[shivajikobardan]

There was more to it than just indentation. Anyway I have looked at this again, those slides are terrible. Here is some code that attempts to explain it better:

# The slide is called 'depth first search' but the code actually
# performs a traversal, not a search, so I have named it accordingly
# also respecting the convention that function names should be verbs
# (and so not depthFirstTraversal).
def traverseDepthFirst(graph, nodeIndex, visited = []):
    """ Recursively traverse a graph depth first.
    graph - the graph (a list) of nodes; each node is a dict with
            entries 'value' and 'children'.
    node - the current node.
    """

    # If we have already visited the node the graph must be recursive
    # which is not allowed for a simple graph.
    if nodeIndex in visited:
        raise Exception('The graph must not be recursive')

    visited.append(nodeIndex)

    # If we want to print the node it should be done here before
    # we traverse its children.
    # print(node)

    for childIndex in graph[nodeIndex]['children']:
        traverseDepthFirst(graph, childIndex, visited)

    # Printing the node here is wrong.
    # print(node)

    # Return the populated list.
    return visited

Here is a demonstration, using the same graph as in the slides:

testGraph = ([
    None, # Node 0: not used.
    {'value': 1, 'children': []}, # Node 1.
    {'value': 12, 'children': []}, # Node 2.
    {'value': 31, 'children': []}, # Node 3.
    {'value': 19, 'children': [1, 2, 3]}, # Node 4.
    {'value': 21, 'children': []}, # Node 5.
    {'value': 23, 'children': []}, # Node 6.
    {'value': 6, 'children': []}, # Node 7.
    {'value': 14, 'children': [6, 7]}, # Node 8.
    {'value': 7, 'children': [4, 5, 8]}, # Node 9.
])

# Traverse the graph starting at the head (node 9).
traversed = traverseDepthFirst(testGraph, 9)
print(traversed)
for i in traversed:
    print('Node', i, ':', testGraph[i]['value'])

Which outputs:

[9, 4, 1, 2, 3, 5, 8, 6, 7]
Node 9 : 7
Node 4 : 19
Node 1 : 1
Node 2 : 12
Node 3 : 31
Node 5 : 21
Node 8 : 14
Node 6 : 23
Node 7 : 6

this code doesn't really runs in my laptop vs code idk why ...shows some error.

 

[pbuk]

this code doesn't really runs in my laptop vs code idk why ...shows some error.

What error? It works when copied into my PC, and in this repl.

 

[shivajikobardan]

very last question.

in the slide instead of printing visited, we have printed node...what does that mean? shouldn't output of depth first search be how we traverse? i m not getting this last point.

 

[pbuk]

very last question.
View attachment 296399
in the slide instead of printing visited, we have printed node...what does that mean? shouldn't output of depth first search be how we traverse? i m not getting this last point.

Well now we have introduced a disconnected cyclic graph which does not have any ordering so it doesn't matter. These slides don't explain anything well.

 

[shivajikobardan]

These slides don't explain anything well.

bro these were the best slides i found on internet.