forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathtraversal.py
More file actions
94 lines (75 loc) · 2.18 KB
/
traversal.py
File metadata and controls
94 lines (75 loc) · 2.18 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
"""
Graph Traversal Algorithms
Provides DFS and BFS traversal of a graph represented as an adjacency
dictionary.
Complexity:
Time: O(V + E)
Space: O(V)
"""
from __future__ import annotations
from typing import Any
def dfs_traverse(graph: dict[Any, list[Any]], start: Any) -> set[Any]:
"""Traverse the graph from *start* using iterative DFS.
Args:
graph: Adjacency list.
start: Starting node.
Returns:
Set of visited nodes.
Examples:
>>> sorted(dfs_traverse({'a': ['b'], 'b': []}, 'a'))
['a', 'b']
"""
visited: set[Any] = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
for next_node in graph[node]:
if next_node not in visited:
stack.append(next_node)
return visited
def bfs_traverse(graph: dict[Any, list[Any]], start: Any) -> set[Any]:
"""Traverse the graph from *start* using BFS.
Args:
graph: Adjacency list.
start: Starting node.
Returns:
Set of visited nodes.
Examples:
>>> sorted(bfs_traverse({'a': ['b'], 'b': []}, 'a'))
['a', 'b']
"""
visited: set[Any] = set()
queue = [start]
while queue:
node = queue.pop(0)
if node not in visited:
visited.add(node)
for next_node in graph[node]:
if next_node not in visited:
queue.append(next_node)
return visited
def dfs_traverse_recursive(
graph: dict[Any, list[Any]],
start: Any,
visited: set[Any] | None = None,
) -> set[Any]:
"""Traverse the graph from *start* using recursive DFS.
Args:
graph: Adjacency list.
start: Starting node.
visited: Already-visited set (internal use).
Returns:
Set of visited nodes.
Examples:
>>> sorted(dfs_traverse_recursive({'a': ['b'], 'b': []}, 'a'))
['a', 'b']
"""
if visited is None:
visited = set()
visited.add(start)
for next_node in graph[start]:
if next_node not in visited:
dfs_traverse_recursive(graph, next_node, visited)
return visited