BeginnerGraphs

Graph DFS/BFS

Traverse graphs to find components, islands, detect cycles, and test bipartite

Time: O(V+E)
Space: O(V)
Pattern Overview

Core Idea

Use recursion/stack for DFS or queue for BFS to explore connectivity and properties.

When to Use

Use for flood fill, island counting, cycle checks, and bipartite tests.

General Recognition Cues
General indicators that this pattern might be applicable
  • Connected components
  • Grid islands
  • Cycle detection
  • Two-coloring
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Components/Islands

Traverse to mark visited nodes/cells

When to Use This Variant
  • Count groups
Use Case
Connectivity
Advantages
  • Linear in V+E
Implementation
def num_islands(grid):
    if not grid: return 0
    R,C=len(grid),len(grid[0]); vis=[[False]*C for _ in range(R)]
    def dfs(r,c):
        if r<0 or c<0 or r>=R or c>=C or grid[r][c]=='0' or vis[r][c]: return
        vis[r][c]=True
        for dr,dc in [(1,0),(-1,0),(0,1),(0,-1)]: dfs(r+dr,c+dc)
    cnt=0
    for r in range(R):
        for c in range(C):
            if grid[r][c]=='1' and not vis[r][c]: cnt+=1; dfs(r,c)
    return cnt
2

Cycle Detection

Parent tracking (undirected) or DFS colors (directed)

When to Use This Variant
  • Detect cycles
Use Case
Graph validity
Advantages
  • Simple checks
Implementation
def has_cycle_undirected(n, edges):
    adj=[[] for _ in range(n)]
    for u,v in edges: adj[u].append(v); adj[v].append(u)
    vis=[False]*n
    def dfs(u,p):
        vis[u]=True
        for v in adj[u]:
            if v==p: continue
            if vis[v] or dfs(v,u): return True
        return False
    return any(dfs(i,-1) for i in range(n) if not vis[i])
3

Bipartite Check

Two-color via BFS/DFS

When to Use This Variant
  • Odd cycle?
Use Case
Partitioning
Advantages
  • O(V+E)
Implementation
def is_bipartite(graph):
    n=len(graph); color=[0]*n
    for i in range(n):
        if color[i]: continue
        stack=[i]; color[i]=1
        while stack:
            u=stack.pop()
            for v in graph[u]:
                if color[v]==0: color[v]=-color[u]; stack.append(v)
                elif color[v]==color[u]: return False
    return True
Common Pitfalls
Watch out for these common mistakes
  • Visited set placement
  • Directed vs undirected cycle rules
  • Grid bounds and diagonals
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(V+E)

Visit edges and vertices once.

Space Complexity
O(V)

Visited/queue/stack.

Ready to test your knowledge?

Test your pattern recognition with interactive questions