A graph is a non-linear data structure used to represent relationships between objects. Graphs are everywhere: social networks, road maps, computer networks, recommendation systems, dependency management, and more.
A graph is made of:
- Vertices (Nodes): the entities (people, cities, computers)
- Edges (Connections): relationships between entities (friendship, roads, cables)
Graphs can model both simple and complex real-world systems, and many important algorithms (BFS, DFS, shortest path, MST) are built on graphs.
Introduction to Graphs (Terminology)
Vertex (Node)
A vertex represents an entity in the graph (like a person in a social network).
Edge
An edge connects two vertices and represents a relationship.
Directed vs Undirected Graph
- Undirected: edge goes both ways (A — B)
- Directed: edge has direction (A → B)
Example:
- Instagram follow: directed
- Facebook friendship: undirected
Weighted vs Unweighted Graph
- Unweighted: all edges have equal cost
- Weighted: edges have weights (distance, time, cost)
Example:
- Map roads with distance → weighted graph
Degree
- Degree (undirected): number of edges connected to a node
- In-degree (directed): edges coming into node
- Out-degree (directed): edges leaving node
Path
A path is a sequence of vertices connected by edges.
Cycle
A cycle occurs when you can start at a node and return to it by following edges.
Representation of Graphs
Graphs can be stored in different ways. The best choice depends on how dense the graph is and what operations you need.
Adjacency Matrix
A 2D matrix where:
matrix[u][v] = 1(or weight) if edge exists- otherwise 0 (or infinity)
Example:
# 4 nodes: 0,1,2,3
matrix = [
[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 1],
[0, 1, 1, 0]
]
Pros:
- Very fast edge lookup O(1)
Cons:
- Uses O(V^2) memory (bad for large sparse graphs)
Adjacency List (Most common)
Store for each node: list of its neighbors.
Example:
graph = {
0: [1, 2],
1: [0, 3],
2: [0, 3],
3: [1, 2]
}
Pros:
- Memory efficient for sparse graphs: O(V + E)
- Great for traversals (BFS/DFS)
Cons:
- Edge lookup can be slower than matrix
Implementing Graphs in Python
Using a Dictionary (Adjacency List)
from collections import defaultdict
graph = defaultdict(list)
# Add edges (undirected example)
graph[0].append(1)
graph[1].append(0)
graph[0].append(2)
graph[2].append(0)
Weighted Graph (Adjacency List)
Store pairs: (neighbor, weight)
graph = {
"A": [("B", 4), ("C", 2)],
"B": [("A", 4), ("D", 5)],
"C": [("A", 2), ("D", 1)],
"D": [("B", 5), ("C", 1)]
}
Graph Traversal Algorithms
Traversal means visiting all reachable nodes in a structured way.
Depth-First Search (DFS)
DFS explores as deep as possible before backtracking.
Use cases:
- Cycle detection
- Topological sorting
- Connected components
- Maze solving
DFS (Recursive)
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=" ")
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
DFS (Iterative using Stack)
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(node, end=" ")
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
Time complexity: O(V + E)
Breadth-First Search (BFS)
BFS explores level by level using a queue.
Use cases:
- Shortest path in unweighted graphs
- Level order traversal
- Finding minimum edges between nodes
BFS Implementation
from collections import deque
def bfs(graph, start):
visited = set([start])
q = deque([start])
while q:
node = q.popleft()
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
q.append(neighbor)
Time complexity: O(V + E)
Shortest Path Algorithms
Shortest path algorithms find the minimum distance between nodes in weighted graphs.
Dijkstra’s Algorithm
Dijkstra finds shortest path from a source node to all others when all weights are non-negative.
Core idea:
- Always expand the node with the smallest known distance
- Use a min-heap (priority queue)
Dijkstra Implementation (Using heapq)
import heapq
def dijkstra(graph, start):
distances = {node: float("inf") for node in graph}
distances[start] = 0
pq = [(0, start)] # (distance, node)
while pq:
current_dist, node = heapq.heappop(pq)
if current_dist > distances[node]:
continue
for neighbor, weight in graph[node]:
new_dist = current_dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
return distances
Time complexity: O((V + E) log V)
When not to use: If graph has negative edges.
Bellman-Ford Algorithm
Bellman-Ford works even if there are negative weights and can detect negative cycles.
Core idea:
Relax all edges V-1 times.
Bellman-Ford Implementation
def bellman_ford(vertices, edges, start):
dist = {v: float("inf") for v in vertices}
dist[start] = 0
for _ in range(len(vertices) - 1):
for u, v, w in edges:
if dist[u] != float("inf") and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Detect negative cycle
for u, v, w in edges:
if dist[u] != float("inf") and dist[u] + w < dist[v]:
raise ValueError("Graph contains a negative weight cycle")
return dist
Time complexity: O(V * E)
Applications of Graphs
- Networking: routing packets between routers
- Social networks: friend/follow relationships
- Maps: shortest route between locations
- Dependencies: build systems, course prerequisites
- Recommendation systems: graph-based suggestions
Summary
Graphs represent relationships and power many real-world systems. Adjacency lists are most common in Python. BFS and DFS are fundamental traversals, while Dijkstra and Bellman-Ford solve shortest path problems under different weight constraints.
Leave a Reply