DSA Graphs, BFS and DFS
A graph is a set of points connected by lines. It can model roads, friendships, flights and networks.
What is a Graph?
Think of a map of areas in Karachi. Each area is a point and each road between two areas is a line.
| Word | Meaning | Example |
|---|---|---|
| Vertex (node) | A point | An area such as Saddar |
| Edge | A connection between two vertices | A road |
| Neighbour | A vertex directly connected to another | Areas one road apart |
| Path | A route along edges | Orangi to Saddar via Nazimabad |
| Weighted graph | Edges have a value, such as distance | A road of 12 km |
| Directed graph | Edges go one way only | A one-way street, or "follows" on social media |
A tree is a special graph with no cycles (no way to go round in a loop).
Storing a Graph: Adjacency List
The most common way is an adjacency list: a dictionary where each vertex maps to a list of its neighbours.
Example
graph = {
"Orangi": ["Nazimabad", "Baldia"],
"Nazimabad": ["Orangi", "Saddar", "Gulshan"],
"Baldia": ["Orangi"],
"Saddar": ["Nazimabad", "Clifton"],
"Gulshan": ["Nazimabad"],
"Clifton": ["Saddar"],
}
print(graph["Nazimabad"])
print(len(graph), "areas")
edges = sum(len(n) for n in graph.values()) // 2
print(edges, "roads")['Orangi', 'Saddar', 'Gulshan'] 6 areas 5 roads
Each road appears twice (once from each end), which is why we divide by 2. Another option is an adjacency matrix, a table of 0s and 1s, which is simple but uses O(V^2) memory.
Breadth-First Search (BFS)
BFS explores the graph level by level: first all neighbours of the start, then their neighbours, and so on. It uses a queue.
Example
from collections import deque
graph = {
"Orangi": ["Nazimabad", "Baldia"],
"Nazimabad": ["Orangi", "Saddar", "Gulshan"],
"Baldia": ["Orangi"],
"Saddar": ["Nazimabad", "Clifton"],
"Gulshan": ["Nazimabad"],
"Clifton": ["Saddar"],
}
def bfs(start):
visited = [start]
queue = deque([start])
while queue:
place = queue.popleft()
for nxt in graph[place]:
if nxt not in visited:
visited.append(nxt)
queue.append(nxt)
return visited
print(bfs("Orangi"))['Orangi', 'Nazimabad', 'Baldia', 'Saddar', 'Gulshan', 'Clifton']
In a graph where every edge counts the same, BFS finds the path with the fewest edges. Apps use this idea to find routes with the fewest stops.
Shortest Path with BFS
By remembering where we came from, BFS can rebuild the route:
Example
from collections import deque
graph = {
"Orangi": ["Nazimabad", "Baldia"],
"Nazimabad": ["Orangi", "Saddar", "Gulshan"],
"Baldia": ["Orangi"],
"Saddar": ["Nazimabad", "Clifton"],
"Gulshan": ["Nazimabad"],
"Clifton": ["Saddar"],
}
def shortest_path(start, goal):
came_from = {start: None}
queue = deque([start])
while queue:
place = queue.popleft()
if place == goal:
break
for nxt in graph[place]:
if nxt not in came_from:
came_from[nxt] = place
queue.append(nxt)
path = []
while goal is not None:
path.append(goal)
goal = came_from[goal]
return path[::-1]
print(" -> ".join(shortest_path("Baldia", "Clifton")))Baldia -> Orangi -> Nazimabad -> Saddar -> Clifton
Depth-First Search (DFS)
DFS goes as deep as possible along one path before coming back to try another. It uses recursion (or a stack).
Example
graph = {
"A": ["B", "C"],
"B": ["D", "E"],
"C": ["F"],
"D": [],
"E": ["F"],
"F": [],
}
def dfs(node, visited=None):
if visited is None:
visited = []
visited.append(node)
for nxt in graph[node]:
if nxt not in visited:
dfs(nxt, visited)
return visited
print(dfs("A"))['A', 'B', 'D', 'E', 'F', 'C']
BFS vs DFS
| BFS | DFS | |
|---|---|---|
| Uses | A queue | A stack or recursion |
| Explores | Level by level | One branch fully, then the next |
| Good for | Fewest-edge paths, nearby friends | Finding any path, detecting cycles, puzzles and mazes |
| Time | O(V + E) | O(V + E) |
V is the number of vertices and E the number of edges. For roads with distances (weighted graphs), Dijkstra's algorithm finds the shortest total distance.
Exercise
Exercise
Which data structure does breadth-first search (BFS) use to decide which vertex to visit next?