Confused about DFS in action as it don't relates with the pseudocode, please help me.

[shivajikobardan]

Tree and Graph Traversal Algorithms BreadthFirst Search BFS

slidetodoc.com

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?

 

[Cubist]

The pseudo code is correct. Try performing a dry run of the code (by hand). In particular what happens when DFS(node"19") is called?

 

[shivajikobardan]

I am surprised you called that the pseudocode is correct. It looks wrong from many aspects. I have done upto step 7...As after that it is just the

repetition of same steps...(forgot spelling of repitition or repetition whatever lol so had to copy it.)​

 

[JeffM]

I have not written code in a long time. Nor do I know if there is a universally agreed syntax for pseudo-code.

What strikes me as strange in this code is that the definition of this function refers to itself. Seems like risky technique.

Anyway, I interpret code as follows.

Invoke function with 19 as argument.

Find children of 19 giving 1, 12, 31.

Invoke function with 1 as argument

Find children of 1.

No success.

Output 1.

Invoke function with 12 as argument

Find children of 12.

No success.

Output 12.

Invoke function with 31 as argument

Find children of 31.

No success.

Output 31.

No more children

Output 19.

 

[Cubist]

What strikes me as strange in this code is that the definition of this function refers to itself. Seems like risky technique.

Yes, recursion can be risky. For example node "19" has "1" listed as a child, AND IF "1" had "19" listed as a child (an arrow pointing up in the diagram, creating a loop in the data) this would lead to an infinite loop in the code, leading to a stack overflow and then the program would crash.

 

[Cubist]

Perhaps some indentation will make it easier to see what happens (but this may not be a standard way to show a dry run)...

DFS function called, with parameter (node"7") {
  for each (node"19", node"21", node"14") call DFS {
    DFS function called, with parameter (node"19") {
    | for each (node"1", node"12", node"31") call DFS {
    |   DFS function called, with parameter (node"1") {
    |     for () - no children
    |     print "1"
    |   }
    |   DFS function called, with parameter (node"12") {
    |     for () - no children
    |     print "12"
    |   }
    |   DFS function called, with parameter (node"31") {
    |     for () - no children
    |     print "31"
    |   }
    | }
    | print "19"
    }
    DFS function called, with parameter (node"21") {
      for () - no children
      print "21"
    }
    DFS function called, with parameter (node"14") {
      ...
    }
  }
  print "7"
}

 

[blamocur]

Yes, recursion can be risky. For example node "19" has "1" listed as a child, AND IF "1" had "19" listed as a child (an arrow pointing up in the diagram, creating a loop in the data) this would lead to an infinite loop in the code, leading to a stack overflow and then the program would crash.

Yes, recursion can be risky. For example node "19" has "1" listed as a child, AND IF "1" had "19" listed as a child (an arrow pointing up in the diagram, creating a loop in the data) this would lead to an infinite loop in the code, leading to a stack overflow and then the program would crash.

While I agree that recursion can be risky it is also the most natural way to traverse trees.

 

[JeffM]

While I agree that recursion can be risky it is also the most natural way to traverse trees.

Of course you could add code that prevents infinite loops, but that would increase run time

 

[blamocur]

View attachment 30939

I am surprised you called that the pseudocode is correct. It looks wrong from many aspects. I have done upto step 7...As after that it is just the

repetition of same steps...(forgot spelling of repitition or repetition whatever lol so had to copy it.)​

Regarding your questions about the stack ("where is stack...", "no code to pop the stack"): in most languages the parameter of the function calls are pushed automatically onto the call stack, and are automatically popped when the function exits. Usually it is the same stack where the local (sometime called "automatic") variables are kept. Your pseudo-code does not contain any local variables, but the "c" parameter is pushed onto the stack when "DFS(c)" is executed.

 

[JeffM]

I really should not answer questions about coding. When I actually was paid to do it and did it every working day (back in the 1960’s), we had no pre-built software to do stacking, and tree structures were rare. I think software people today have little idea how cumbersome it was to get a computer to do anything the least bit clever in the first decades of computers.

 

[Cubist]

Here's some Python that OP can play with. There are several online websites that allow you to run Python without installing it.

Spoiler: show code

class Node:
    def __init__(self, id, children):
        self.id = id
        self.children = children

# Depth first search code
def DFS(n):
    for c in n.children:
        DFS(c)
    print(n.id)

# Version that shows a string that represents the call stack
def DFS_with_stack(n, stack):
    stack += " -> " + str(n.id)
    for c in n.children:
        DFS_with_stack(c, stack)
    print(stack, " Output:", n.id)

    
###################################
# Set up data
# leaf nodes
n1=Node(1, [])
n12=Node(12, [])
n31=Node(31, [])
n23=Node(23, [])
n6=Node(6, [])
n21=Node(21, [])
# other nodes
n19=Node(19, [n1, n12, n31])
n14=Node(14, [n23, n6])
n7=Node(7, [n19, n21, n14])
###################################

DFS(n7)
print()
DFS_with_stack(n7, "")

Spoiler: show output

1
12
31
19
21
23
6
14
7

 -> 7 -> 19 -> 1  Output: 1
 -> 7 -> 19 -> 12  Output: 12
 -> 7 -> 19 -> 31  Output: 31
 -> 7 -> 19  Output: 19
 -> 7 -> 21  Output: 21
 -> 7 -> 14 -> 23  Output: 23
 -> 7 -> 14 -> 6  Output: 6
 -> 7 -> 14  Output: 14
 -> 7  Output: 7