Is my postorder traversal of this graph correct?

I am trying to implement an algorithm that requires a post-order traversal. Here is my graph (taken from here, pg. 8):

When I try to do a postorder traversal of this, the order I get is:

[3, 2, 1, 5, 4, 6]

The problem with this order is that the algorithm won't work in this order. This is the code I am using to get it (pseudocode):

function PostOrder(root, out_list) {
    root.visited = true
    for child in root.Children {
        if not child.visited {
            PostOrder(child, out_list)
        }
    }
    out_list.append(root)
}

Is the postorder correct?

Yes, the post order traversal of your algorithm is correct. The expected output is indeed as you provided it.

Your confusion may come from the fact that the graph is not a binary tree, and not even a tree. It is a directed graph.

In general postorder means that you first perform a postorder traversal on the node behind the first outgoing edge, then on the node behind its next outgoing edge, ...etc, and only after all outgoing edges have been traversed, the node itself is output.

Since at node 1 you are not at the end yet, and still can go to 2, and from there to 3, you need to follow those edges before outputting anything. And only then backtrack.

For reference, here is your algorithm implemented in python:

def postorder(root, out_list, children, visited):
    visited[root] = True
    for child in children[root]:
        if not visited[child]:
            postorder(child, out_list, children, visited)
    out_list.append(root)

children = [
    [],      # dummy for node 0
    [2],     # 1
    [1,3],   # 2
    [2],     # 3
    [2,3],   # 4
    [1],     # 5
    [5,4]    # 6 
]

nodes = []
postorder(6, nodes, children, [False] * len(children))

print(nodes) # [3, 2, 1, 5, 4, 6]