Traverse graphs to find components, islands, detect cycles, and test bipartite
Use recursion/stack for DFS or queue for BFS to explore connectivity and properties.
Use for flood fill, island counting, cycle checks, and bipartite tests.
Visited tracking with standard BFS/DFS templates for components/islands, cycle checks, and bipartite testing.
# Graph DFS/BFS Templates
from collections import deque
def bfs(n, adj, src):
dist=[-1]*n; dist[src]=0
q=deque([src])
while q:
u=q.popleft()
for v in adj[u]:
if dist[v]==-1:
dist[v]=dist[u]+1; q.append(v)
return dist
def dfs_util(u, adj, vis):
vis[u]=True
for v in adj[u]:
if not vis[v]: dfs_util(v, adj, vis)Traverse to mark visited nodes/cells
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 cntParent tracking (undirected) or DFS colors (directed)
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])Two-color via BFS/DFS
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 TrueVisit edges and vertices once.
Visited/queue/stack.