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

In summary, 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.
  • #1
shivajikobardan
674
54
Homework Statement
Depth first search
Relevant Equations
there is a pseudocode below.
1643534522672.png


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/
 
Physics news on Phys.org
  • #2
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:
# 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)
 
Last edited:
  • Like
  • Love
Likes pbuk, shivajikobardan and jim mcnamara
  • #3
Mark44 said:
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
Mark44 said:
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:
# 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

added goal test:
# 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)
 
Last edited:
  • #4
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 o:)).

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:
Python:
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)
 
Last edited:
  • #5
pbuk said:
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().
 
  • Like
Likes pbuk
  • #6
Mark44 said:
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.
 
  • Like
Likes shivajikobardan
  • #7
shivajikobardan said:
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
 
  • Like
Likes sysprog
  • #8
shivajikobardan said:
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.
shivajikobardan said:
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.
 
  • Like
Likes sysprog, shivajikobardan and pbuk
  • #9
pbuk said:
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 o:)).

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:
Python:
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?
 
  • #10
Mark44 said:
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:
# 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?
 
  • #11
shivajikobardan said:
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.
shivajikobardan said:
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:
Python:
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).
Code:
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.
 
  • Like
Likes sysprog and pbuk
  • #12
shivajikobardan said:
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.
Python:
# 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:

Python:
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:

Code:
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
 
Last edited:
  • Like
  • Sad
Likes sysprog and shivajikobardan
  • #13
pbuk said:
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:
Python:
# 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:

Python:
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:

Code:
[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.
 
  • #14
shivajikobardan said:
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.
 
  • Like
Likes sysprog
  • #15
very last question.
1643780559132.png

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.
 
  • #16
shivajikobardan said:
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.
 
  • #17
pbuk said:
These slides don't explain anything well.
bro these were the best slides i found on internet.
 

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

1. What is DFS algorithm?

DFS (Depth-First Search) algorithm is a graph traversal algorithm that explores a graph by starting at a designated source vertex and following a path until it reaches a dead end. It then backtracks to the last vertex with unexplored paths and continues until all vertices have been visited.

2. How does DFS algorithm work?

DFS algorithm works by maintaining a stack of vertices to be visited. It starts at a designated source vertex and marks it as visited. Then, it explores its adjacent vertices and adds them to the stack. It continues this process until it reaches a dead end, then it backtracks to the last vertex with unexplored paths and repeats the process until all vertices have been visited.

3. What is the difference between DFS and BFS algorithm?

The main difference between DFS (Depth-First Search) and BFS (Breadth-First Search) algorithm is the order in which they explore the graph. DFS explores the graph by going deep into a path until it reaches a dead end, while BFS explores the graph by going wide and visiting all adjacent vertices before moving on to the next level.

4. What are the applications of DFS algorithm?

DFS algorithm has many applications in computer science, such as finding connected components in a graph, detecting cycles in a graph, and solving maze problems. It is also used in data compression, garbage collection, and topological sorting.

5. What are the advantages of using DFS algorithm?

DFS algorithm has several advantages, including simplicity, efficiency, and the ability to find a path between two vertices. It also requires less memory compared to BFS as it only needs to store the path from the source to the current vertex. Additionally, it can be easily implemented using recursion, making it easier to understand and debug.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
1
Views
999
  • Programming and Computer Science
Replies
3
Views
783
  • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
2K
  • Quantum Physics
Replies
1
Views
893
Replies
9
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Programming and Computer Science
Replies
3
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
3K
Back
Top