Patterns
Graph
Adjacency List
python G = defaultdict(list) for a, b in edges: G[a].append(b) G[b].append(a)
python G = defaultdict(list) for a, b in edges: G[a].append(b) Traversal
visited = set()
def dft(node: int) -> None:
if node in visited:
return
visited.add(node)
for nei in G[node]:
dft(nei)stack = [start]
visited = set()
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
for nei in G[node]:
stack.append(nei)q = deque([start])
visited = set([start])
while q:
node = q.popleft()
for nei in G[node]:
if nei not in visited:
visited.add(nei)
q.append(nei)