Graph Intro

A graph represents connections between things.

Examples:

• roads between cities
• followers on social media
• dependencies in projects

Adjacency list (best common representation)

graph = {
  "A": ["B", "C"],
  "B": ["D"],
  "C": ["D"],
  "D": []
}

DFS traversal

def dfs(graph, start):
    visited = set()

    def visit(node):
        if node in visited:
            return
        visited.add(node)
        print(node)
        for nxt in graph.get(node, []):
            visit(nxt)

    visit(start)

dfs(graph, "A")

BFS traversal

from collections import deque

def bfs(graph, start):
    visited = set([start])
    q = deque([start])

    while q:
        node = q.popleft()
        print(node)
        for nxt in graph.get(node, []):
            if nxt not in visited:
                visited.add(nxt)
                q.append(nxt)

bfs(graph, "A")

Graph diagram

flowchart LR
  A --> B
  A --> C
  B --> D
  C --> D

Remember

• Graph = nodes + edges
• adjacency list is common in Python
• DFS and BFS are core traversal tools