Algorithm Full-DFS output not as expected

I copied Python code DFS and full-DFS from 6.006 and this code make me confused, its result not run as expected, please help me, thank you

    def dfs(Adj, s, parent = None, order = None):
    if parent is None:
        parent = [None for v in Adj] 
        parent
展开收缩
 = s 
        order = [] 
    print(f's:{s}')
    print(f'Adj
展开收缩
:{Adj
展开收缩
}')
    for v in Adj
展开收缩
:
        if parent[v] is None:
            print(f'parent[{v}] is None:{parent[v]}')
            parent[v] = s 
            dfs(Adj, v, parent, order)
    order.append(s) 
    print(f'dfs order:{order}')
    print(f'dfs parent:{order}')
    return parent, order

def full_dfs(Adj):
    parent = [None for v in Adj] 
    order = [] 
    print(f'full_dfs:{parent}')
    print(f'full_dfs:{len(Adj)}')
    print(f'full_dfs:{range(len(Adj))}')
    for v in range(len(Adj)):
        print(f'{v}')
        if parent[v] is None:
            parent[v] = v
            dfs(Adj, v, parent, order)
    return parent, order

adj = [[1],[2,3],[4],[4],[]]
par,order = full_dfs(adj)
print(f'{par}')
print(f'{order}')
#
#*******************Output***************************
#full_dfs:[None, None, None, None, None]
#full_dfs:5
#full_dfs:range(0, 5)
#0
#s:0
#Adj
展开收缩
:[1]
#parent[1] is None:None
#s:1
#Adj
展开收缩
:[2, 3]
#parent[2] is None:None
#s:2
#Adj
展开收缩
:[4]
#parent[4] is None:None
#s:4
#Adj
展开收缩
:[]
#dfs order:[4]
#dfs parent:[4]
#dfs order:[4, 2]
#dfs parent:[4, 2]
#parent[3] is None:None
#s:3
#Adj
展开收缩
:[4]
#dfs order:[4, 2, 3]
#dfs parent:[4, 2, 3]
#dfs order:[4, 2, 3, 1]
#dfs parent:[4, 2, 3, 1]
#dfs order:[4, 2, 3, 1, 0]
#dfs parent:[4, 2, 3, 1, 0]
#1
#2
#3
#4
#[0, 0, 1, 1, 2]
#[4, 2, 3, 1, 0]
#
#
#** Process exited - Return Code: 0 **
#Press Enter to exit terminal

My question is, why its result is [4, 2, 3, 1, 0] rather than [4,2,1,0] or [4,3,1,0], because Depth first right?

In my opinion, [4, 2, 3, 1, 0] meaningless, do you agree?

First of all, your code visits all nodes. "depth-first" does not mean "first-only". It means that before looking to sibling nodes, it will first look to children nodes. But its purpose is to visit all nodes.

All nodes are visited by your code because parent records which nodes are visited, and which not yet, and if they are not yet visited, the loops in both full_dfs and dfs ensure they are. And when a node is given to dfs, it eventually gets appended to order, so it is expected that all nodes end up in that list.

Secondly, a node is only added to order when all other nodes that are reachable from that node have been visited (through recursion). This is what is called a post-order traversal, since the action on the node is performed after the same action has been done on all its successors/children.

Now to the example graph:

dfs recursive calls are made to go from node 0 to 1 to 2 to 4. At that stage there are no more successor nodes, so 4 is appended to order, and that deepest dfs call returns to get back to the execution context of dfs where the current node is 2. Also there we find there are no other successors, so 2 is appended to order and also that dfs call returns. We get back to the execution context of dfs where the current node is 1.

Here we have another successor (second iteration of the loop), and so another recursive call is made where 3 is the current node. Although this node has a successor (4), that node has already been visited (its parent has been set), so 3 is appended to order and execution returns to the execution context where 1 is the current node.

For node 1 there are no other successors, so 1 is appended to order and dfs returns to the original execution context of dfs where the current node is 0. This node has no other successors, so 0 is appended to order.

We can visualise this process a bit where each "box" represents an execution context of a function. Execution goes from top to bottom. When a function returns, its execution context ends (the box closes) and execution continues in the surrounding "box":

+-- full_dfs() --------------------------------+
|  parent[0] = 0                               | 
|  +-- dfs(s=0) ----------------------------+  |
|  |  parent[1] = 0                         |  |
|  |  +-- dfs(s=1) ----------------------+  |  |
|  |  |  parent[2] = 1                   |  |  |
|  |  |  +-- dfs(s=2) ----------------+  |  |  |
|  |  |  |  parent[4] = 2             |  |  |  |
|  |  |  |  +-- dfs(s=4) ----------+  |  |  |  |
|  |  |  |  | order.append(4)      |  |  |  |  |
|  |  |  |  +----------------------+  |  |  |  |
|  |  |  |  order.append(2)           |  |  |  |
|  |  |  +----------------------------+  |  |  |
|  |  |  parent[3] = 1                   |  |  |
|  |  |  +-- dfs(s=3) ----------------+  |  |  |
|  |  |  |  order.append(3)           |  |  |  |
|  |  |  +----------------------------+  |  |  |
|  |  |  order.append(1)                 |  |  |
|  |  +----------------------------------+  |  |
|  |  order.append(0)                       |  |
|  +----------------------------------------+  |
+----------------------------------------------+

Hope this clarifies the process and why you get [4, 2, 3, 1, 0] as output: it is the post-order DFS traversal for your graph when starting at 0.