Definitions
- A graph has n nodes and m edges
- Each node’s degree is the number of its neighbors
- The sum of node degrees in a graph with n nodes and m edges is 2*m (since every edge increments two nodes’ degrees)
- Each “island” in the graph is called a component
- A graph is bipartite (2-colored) exactly when there’s no cycle with an odd number of edges
Key Interview Questions
When given a graph problem in an interview, always ask:
1) Are there any self-loops or duplicate edges?
2) Is the graph directional or weighted? Are there any negative weights?
3) Can there be disconnected components in the input graph?
4) Can there be any cycles in the input?
Graph Traversals
Depth-First Search (DFS)
DFS keeps going on a single path and backtracks to previous nodes when reaching an end.
adjList = {} # adjacency list representation
visited = set()
def dfs(node):
if node in visited:
return
visited.add(node) # Mark visited right after checking visited
for neighbour in adjList[node]:
dfs(neighbour)
- Time Complexity: O(n + m), as we visit every edge and node once
- Space Complexity: O(n), since we only store nodes in visited set
Breadth-First Search (BFS)
BFS traverses the graph level-wise and can find the shortest path in unweighted graphs.
from collections import deque
visited = set()
def bfs(node):
# 1. Put node in queue
q = deque()
visited.add(node) # You mark visit before adding to queue
q.append(node) # visited before q -> no dupes in queue
while q:
# 2. Process node in queue
cur = q.popleft()
# 3. Add valid neighbors
for neighbor in adjList[cur]:
if neighbor not in visited and is_valid:
visited.add(neighbor)
q.append(neighbor)
return
- Time complexity: O(n+m) as we will visit every edge and node once
- Space Complexity: O(n), since we only store nodes in visited set