Intermediate·1 min read
Graph Fundamentals & BFS/DFS
Representations, BFS, DFS, and their applications.
Graph Fundamentals & BFS/DFS
A graph is a set of vertices (nodes) connected by edges (links).
Graph Terminology
- Directed vs Undirected: Edges have direction or not
- Weighted vs Unweighted: Edges have costs or not
- Degree: Number of edges connected to a vertex
- Path: Sequence of vertices connected by edges
- Cycle: A path that starts and ends at the same vertex
- Connected: Every vertex can reach every other vertex
Representations
Adjacency Matrix (O(V²) space):``
0 1 2 3
0 [0, 1, 1, 0]
1 [1, 0, 1, 0]
2 [1, 1, 0, 1]
3 [0, 0, 1, 0]
`
Adjacency List (O(V + E) space):
`
0: [1, 2]
1: [0, 2]
2: [0, 1, 3]
3: [2]
``
BFS (Breadth-First Search)
Explores level by level using a queue.
- Start at source, enqueue it
- Dequeue a vertex, visit unvisited neighbors
- Enqueue unvisited neighbors
- Repeat until queue is empty
DFS (Depth-First Search)
Explores as deep as possible using recursion/stack.
- Visit a vertex
- Recursively visit an unvisited neighbor
- Backtrack when no unvisited neighbors remain
Code Example
python
from collections import deque
class Graph:
def __init__(self, vertices):
self.V = vertices
self.adj = [[] for _ in range(vertices)]
def add_edge(self, u, v, directed=False):
self.adj[u].append(v)
if not directed:
self.adj[v].append(u)
def bfs(self, start):
visited = [False] * self.V
queue = deque([start])
visited[start] = True
order = []
while queue:
vertex = queue.popleft()
order.append(vertex)
for neighbor in self.adj[vertex]:
if not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)
return order
def dfs(self, start, visited=None):
if visited is None:
visited = [False] * self.V
visited[start] = True
order = [start]
for neighbor in self.adj[start]:
if not visited[neighbor]:
order.extend(self.dfs(neighbor, visited))
return order
def has_cycle(self):
visited = [False] * self.V
for i in range(self.V):
if not visited[i]:
if self._dfs_cycle(i, visited, -1):
return True
return False
def _dfs_cycle(self, node, visited, parent):
visited[node] = True
for neighbor in self.adj[node]:
if not visited[neighbor]:
if self._dfs_cycle(neighbor, visited, node):
return True
elif neighbor != parent:
return True
return False
g = Graph(6)
edges = [(0,1), (0,2), (1,3), (1,4), (2,4), (3,5), (4,5)]
for u, v in edges:
g.add_edge(u, v)
print("BFS from 0:", g.bfs(0))
print("DFS from 0:", g.dfs(0))Practice Problems
- 01Find the number of connected components in an undirected graph
- 02Detect a cycle in an undirected graph using DFS
- 03Find the shortest path in an unweighted graph using BFS