Graph theory provides the mathematical foundation for modeling relationships and connections in software systems. From network routing to social media analysis, understanding graphs and their algorithms is essential for modern software engineers.
What is Graph Theory?
A graph is a collection of vertices (also called nodes) and edges that connect pairs of vertices. Graphs can be directed (edges have a direction) or undirected (edges are bidirectional), and they may be weighted (edges carry a cost or value).
Key Terminology
- Vertex (Node): The fundamental unit representing an entity.
- Edge (Link): A connection between two vertices.
- Degree: Number of edges incident to a vertex (out-degree/in-degree for directed graphs).
- Path: A sequence of edges connecting a series of vertices.
- Cycle: A path that starts and ends at the same vertex without repeating edges.
- Connected Graph: A graph where there is a path between every pair of vertices.
- Tree: A connected acyclic graph.
Graph Representations
Choosing an appropriate representation affects both the time and space complexity of graph algorithms.
| Representation | Description | When to Use | Space Complexity |
|---|---|---|---|
| Adjacency Matrix | 2‑D array where cell (i,j) indicates presence/weight of edge i→j. | Dense graphs (many edges). | O(V²) |
| Adjacency List | Array of lists; each list contains neighboring vertices (and optionally weights). | Sparse graphs (few edges). | O(V + E) |
| Edge List | Flat list of (source, destination, weight) tuples. | When edges need to be processed independently, e.g., in Kruskal's algorithm. | O(E) |
Fundamental Graph Algorithms
Breadth‑First Search (BFS)
BFS explores vertices layer by layer, guaranteeing the shortest path (in terms of edge count) from the start vertex to every reachable vertex in an unweighted graph.
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
order = []
while queue:
vertex = queue.popleft()
order.append(vertex)
for neighbour in graph[vertex]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
return order
# Example usage
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print(bfs(graph, 'A'))import java.util.*;
public class BFS {
public static List<String> bfs(Map<String, List<String>> graph, String start) {
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
List<String> order = new ArrayList<>();
visited.add(start);
queue.add(start);
while (!queue.isEmpty()) {
String vertex = queue.poll();
order.add(vertex);
for (String neighbour : graph.getOrDefault(vertex, Collections.emptyList())) {
if (!visited.contains(neighbour)) {
visited.add(neighbour);
queue.add(neighbour);
}
}
}
return order;
}
public static void main(String[] args) {
Map<String, List<String>> graph = new HashMap<>();
graph.put("A", Arrays.asList("B", "C"));
graph.put("B", Arrays.asList("A", "D", "E"));
graph.put("C", Arrays.asList("A", "F"));
graph.put("D", Arrays.asList("B"));
graph.put("E", Arrays.asList("B", "F"));
graph.put("F", Arrays.asList("C", "E"));
System.out.println(bfs(graph, "A"));
}
}Depth‑First Search (DFS)
DFS explores as far as possible along each branch before backtracking. It can be implemented recursively or with an explicit stack.
def dfs(graph, start, visited=None, order=None):
if visited is None:
visited = set()
if order is None:
order = []
visited.add(start)
order.append(start)
for neighbour in graph[start]:
if neighbour not in visited:
dfs(graph, neighbour, visited, order)
return order
# Example usage
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
print(dfs(graph, 'A'))import java.util.*;
public class DFS {
public static List<String> dfs(Map<String, List<String>> graph, String start) {
Set<String> visited = new HashSet<>();
List<String> order = new ArrayList<>();
dfsHelper(graph, start, visited, order);
return order;
}
private static void dfsHelper(Map<String, List<String>> graph, String vertex,
Set<String> visited, List<String> order) {
visited.add(vertex);
order.add(vertex);
for (String neighbour : graph.getOrDefault(vertex, Collections.emptyList())) {
if (!visited.contains(neighbour)) {
dfsHelper(graph, neighbour, visited, order);
}
}
}
public static void main(String[] args) {
Map<String, List<String>> graph = new HashMap<>();
graph.put("A", Arrays.asList("B", "C"));
graph.put("B", Arrays.asList("D", "E"));
graph.put("C", Arrays.asList("F"));
graph.put("D", Collections.emptyList());
graph.put("E", Arrays.asList("F"));
graph.put("F", Collections.emptyList());
System.out.println(dfs(graph, "A"));
}
}Shortest Path – Dijkstra’s Algorithm
Dijkstra’s algorithm finds the minimum‑cost path from a source vertex to all other vertices in a weighted graph with non‑negative edge weights.
import heapq
def dijkstra(graph, start):
# graph: {vertex: [(neighbour, weight), ...]}
distances = {v: float('inf') for v in graph}
distances[start] = 0
pq = [(0, start)] # priority queue of (distance, vertex)
while pq:
current_dist, u = heapq.heappop(pq)
if current_dist > distances[u]:
continue
for v, weight in graph[u]:
distance = current_dist + weight
if distance < distances[v]:
distances[v] = distance
heapq.heappush(pq, (distance, v))
return distances
# Example usage
graph = {
'A': [('B', 5), ('C', 1)],
'B': [('C', 2), ('D', 1)],
'C': [('B', 3), ('D', 4), ('E', 8)],
'D': [('E', 2)],
'E': []
}
print(dijkstra(graph, 'A'))Choosing the Right Representation
Practical Example: Social Network Friend Recommendations
Imagine a social media platform where we want to suggest "friends of friends" to a user. This can be modeled as an undirected, unweighted graph where each vertex is a user and each edge represents a friendship.
- Represent the social network as an adjacency list.
- Run BFS starting from the target user up to depth 2.
- Collect all vertices reached at depth 2 that are not already direct friends.
- Return the collected vertices as recommendation candidates.
def recommend_friends(graph, user):
visited = {user}
queue = [(user, 0)] # (vertex, depth)
recommendations = set()
while queue:
vertex, depth = queue.pop(0)
if depth == 2:
recommendations.add(vertex)
continue
for neighbour in graph[vertex]:
if neighbour not in visited:
visited.add(neighbour)
queue.append((neighbour, depth + 1))
# Remove direct friends and the user itself
recommendations -= set(graph[user])
recommendations.discard(user)
return recommendations
# Sample social graph
social = {
'Alice': ['Bob', 'Carol'],
'Bob': ['Alice', 'Dave'],
'Carol': ['Alice', 'Eve'],
'Dave': ['Bob', 'Eve'],
'Eve': ['Carol', 'Dave']
}
print(recommend_friends(social, 'Alice')) # Output: {'Dave', 'Eve'}Graphs are the lingua franca of many complex systems; mastering them unlocks powerful problem‑solving tools.
🎥 Video
Q: When should I use an adjacency matrix instead of an adjacency list?
A: An adjacency matrix is preferable for dense graphs where the number of edges approaches V², or when you need constant‑time edge existence checks.
Q: Can Dijkstra’s algorithm handle negative edge weights?
A: No. Dijkstra assumes non‑negative weights. For graphs with negative edges (but no negative cycles), use the Bellman‑Ford algorithm.
Q: Is BFS guaranteed to find the shortest path in a weighted graph?
A: BFS finds the shortest path in terms of the number of edges only for unweighted graphs. For weighted graphs, algorithms like Dijkstra or A* are required.
Q. Which graph representation offers O(1) time complexity for checking if an edge exists between two vertices?
- Adjacency List
- Edge List
- Adjacency Matrix
- Incidence List
Answer: Adjacency Matrix
In an adjacency matrix, the cell at (i, j) directly tells whether an edge i→j exists, giving O(1) lookup.
Q. What is the time complexity of BFS on a graph represented with an adjacency list?
- O(V²)
- O(V + E)
- O(E log V)
- O(V log V)
Answer: O(V + E)
BFS visits every vertex once and traverses each edge once, leading to linear complexity in the size of the graph.