DSA
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)

On this page