Pre-order List

The pre-order list algorithm records vertices in the order they are first discovered by DFS — each vertex is added to the list upon entry, BEFORE checking neighbors.

Sredni

O(V+E)O(V)OIJOI

Select programming language

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

Select example

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

Pre-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()
9pre_order = []
10
11def dfs(vertex):
12    """DFS-based pre-order list."""
13    visited.add(vertex)
14    pre_order.append(vertex)
15
16    for neighbor in graph[vertex]:
17        if neighbor not in visited:
18            dfs(neighbor)
19
20# Iterate over all vertices (handles disconnected graphs)
21for w in graph:
22    if w not in visited:
23        dfs(w)
24print(f"Pre-order list: {pre_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	pre_order = []
10
11	def dfs(vertex):
12	"""DFS-based pre-order list."""
13	visited.add(vertex)
14	pre_order.append(vertex)
15
16	for neighbor in graph[vertex]:
17	if neighbor not in visited:
18	dfs(neighbor)
19
20	# Iterate over all vertices (handles disconnected graphs)
21	for w in graph:
22	if w not in visited:
23	dfs(w)
24	print(f"Pre-order list: {pre_order}")