Post-order List

The post-order list algorithm records vertices in the order they are completed by DFS — each vertex is added to the list AFTER processing ALL its neighbors (at function exit).

Sredni

O(V+E)O(V)OIJOI

Select programming language

Choose the language to see the post-order list implementation.

Select example

Small, Medium, and Large show recursion code generation. Very large shows only the call stack.

Post-order List (Python): Small graph (5 vertices, DAG)

Graph

1/0

Animation speed1.0x

Source codePython
1graph = {
2    1: [2, 3],
3    2: [4],
4    3: [5],
5    4: [],
6    5: []
7}
8visited = set()
9post_order = []
10
11def dfs(vertex):
12    """DFS-based post-order list."""
13    visited.add(vertex)
14
15    for neighbor in graph[vertex]:
16        if neighbor not in visited:
17            dfs(neighbor)
18
19    post_order.append(vertex)
20
21# Iterate over all vertices (handles disconnected graphs)
22for w in graph:
23    if w not in visited:
24        dfs(w)
25print(f"Post-order list: {post_order}")

Variables0 variables

No variables at this step

1/0

Animation speed1.0x

1	graph = {
2	1: [2, 3],
3	2: [4],
4	3: [5],
5	4: [],
6	5: []
7	}
8	visited = set()
9	post_order = []
10
11	def dfs(vertex):
12	"""DFS-based post-order list."""
13	visited.add(vertex)
14
15	for neighbor in graph[vertex]:
16	if neighbor not in visited:
17	dfs(neighbor)
18
19	post_order.append(vertex)
20
21	# Iterate over all vertices (handles disconnected graphs)
22	for w in graph:
23	if w not in visited:
24	dfs(w)
25	print(f"Post-order list: {post_order}")