/
bfs.py
26 lines (19 loc) · 776 Bytes
/
bfs.py
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
from typing import Any, Dict, List
Graph = Dict[int, List[int]]
TrackedGraph = Dict[int, Dict[str, Any]]
def bfs(graph: Graph) -> TrackedGraph:
all_nodes = list(graph.keys())
graph_tracker: TrackedGraph = {
node: {"nodes": graph[node], "is_explored": False} for node in all_nodes
}
start_node = all_nodes[0]
queue = [start_node]
graph_tracker[start_node]["is_explored"] = True
while queue:
current_node = queue.pop(0)
adjacent_nodes = graph_tracker[current_node]["nodes"]
for adjacent_node in adjacent_nodes:
if not graph_tracker[adjacent_node]["is_explored"]:
graph_tracker[adjacent_node]["is_explored"] = True
queue.append(adjacent_node)
return graph_tracker