Graph Algorithms – LeetCode Style (Python)
Only important graph algorithms, written in clean LeetCode-style Python. Assumes
graph as adjacency list unless stated.
0. Build Graph (Adjacency List – LeetCode Style)
from collections import defaultdict
# For unweighted graph
def build_graph(edges, n):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # remove for directed graph
return graph
# For weighted graph
def build_weighted_graph(edges, n):
graph = defaultdict(list)
for u, v, w in edges:
graph[u].append((v, w))
graph[v].append((u, w)) # remove for directed graph
return graph
1. Breadth First Search (BFS)
from collections import deque
def bfs(start, graph):
visited = set()
q = deque([start])
[Link](start)
while q:
node = [Link]()
for nei in graph[node]:
if nei not in visited:
[Link](nei)
[Link](nei)
1
2. Depth First Search (DFS – Recursive)
def dfs(node, graph, visited):
[Link](node)
for nei in graph[node]:
if nei not in visited:
dfs(nei, graph, visited)
3. Depth First Search (DFS – Iterative)
def dfs_iterative(start, graph):
visited = set()
stack = [start]
while stack:
node = [Link]()
if node not in visited:
[Link](node)
for nei in graph[node]:
[Link](nei)
4. Dijkstra’s Algorithm (Shortest Path)
import heapq
def dijkstra(n, graph, src):
dist = [float('inf')] * n
dist[src] = 0
pq = [(0, src)]
while pq:
d, node = [Link](pq)
if d > dist[node]:
continue
for nei, wt in graph[node]:
if dist[nei] > d + wt:
dist[nei] = d + wt
[Link](pq, (dist[nei], nei))
return dist
2
5. Topological Sort (Kahn’s Algorithm – BFS)
from collections import deque
def topo_sort(n, graph):
indegree = [0] * n
for u in graph:
for v in graph[u]:
indegree[v] += 1
q = deque([i for i in range(n) if indegree[i] == 0])
topo = []
while q:
node = [Link]()
[Link](node)
for nei in graph[node]:
indegree[nei] -= 1
if indegree[nei] == 0:
[Link](nei)
return topo if len(topo) == n else []
6. Topological Sort (DFS)
def topo_dfs(node, graph, visited, stack):
visited[node] = True
for nei in graph[node]:
if not visited[nei]:
topo_dfs(nei, graph, visited, stack)
[Link](node)
def topo_sort_dfs(n, graph):
visited = [False] * n
stack = []
for i in range(n):
if not visited[i]:
topo_dfs(i, graph, visited, stack)
return stack[::-1]
3
7. Cycle Detection (Directed Graph – DFS)
def has_cycle(n, graph):
vis = [0] * n # 0=unvisited, 1=visiting, 2=visited
def dfs(u):
if vis[u] == 1:
return True
if vis[u] == 2:
return False
vis[u] = 1
for v in graph[u]:
if dfs(v):
return True
vis[u] = 2
return False
for i in range(n):
if vis[i] == 0 and dfs(i):
return True
return False
8. Union Find (Disjoint Set Union – DSU)
class DSU:
def __init__(self, n):
[Link] = list(range(n))
[Link] = [0] * n
def find(self, x):
if [Link][x] != x:
[Link][x] = [Link]([Link][x])
return [Link][x]
def union(self, x, y):
px, py = [Link](x), [Link](y)
if px == py:
return False
if [Link][px] < [Link][py]:
[Link][px] = py
elif [Link][px] > [Link][py]:
[Link][py] = px
else:
[Link][py] = px
[Link][px] += 1
return True
4
9. Kruskal’s Algorithm (MST)
def kruskal(n, edges):
dsu = DSU(n)
[Link](key=lambda x: x[2])
mst = 0
for u, v, wt in edges:
if [Link](u, v):
mst += wt
return mst
10. Prim’s Algorithm (MST)
import heapq
def prim(n, graph):
visited = [False] * n
pq = [(0, 0)]
cost = 0
while pq:
wt, node = [Link](pq)
if visited[node]:
continue
visited[node] = True
cost += wt
for nei, w in graph[node]:
if not visited[nei]:
[Link](pq, (w, nei))
return cost
11. Bellman–Ford Algorithm
def bellman_ford(n, edges, src):
dist = [float('inf')] * n
dist[src] = 0
for _ in range(n - 1):
for u, v, wt in edges:
if dist[u] != float('inf') and dist[u] + wt < dist[v]:
dist[v] = dist[u] + wt
5
for u, v, wt in edges:
if dist[u] != float('inf') and dist[u] + wt < dist[v]:
return [] # negative cycle
return dist
12. Floyd–Warshall (All-Pairs Shortest Path)
def floyd_warshall(dist):
n = len(dist)
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
13. Bipartite Graph Check
from collections import deque
def is_bipartite(n, graph):
color = [-1] * n
for i in range(n):
if color[i] == -1:
q = deque([i])
color[i] = 0
while q:
u = [Link]()
for v in graph[u]:
if color[v] == -1:
color[v] = 1 - color[u]
[Link](v)
elif color[v] == color[u]:
return False
return True
14. Shortest Path in Unweighted Graph (BFS)
from collections import deque
def shortest_path(n, graph, src):
6
dist = [-1] * n
dist[src] = 0
q = deque([src])
while q:
u = [Link]()
for v in graph[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
[Link](v)
return dist
✅ This covers 99% graph problems on LeetCode.
If you want, I can: - Compress this to a 1‑page cheat sheet - Add templates for grid graphs - Add
time/space complexity notes