Category: Graphs
Topics: networks, dependencies, routing, social graphs
A non-linear data structure consisting of vertices (nodes) and edges (connections between nodes), used to represent relationships and networks.
| Operation | Adj List | Adj Matrix | Description |
|---|---|---|---|
| Add vertex | O(1) | O(V²) | Add new node |
| Add edge | O(1) | O(1) | Connect two nodes |
| Remove vertex | O(V+E) | O(V²) | Remove node and edges |
| Remove edge | O(E) | O(1) | Remove connection |
| Check edge | O(V) | O(1) | Check if edge exists |
| Get neighbors | O(1) | O(V) | Get adjacent nodes |
| BFS/DFS | O(V+E) | O(V²) | Traverse graph |
from collections import defaultdict, deque
# Adjacency List (most common for sparse graphs)
class Graph:
def __init__(self, directed=False):
self.graph = defaultdict(list)
self.directed = directed
def add_edge(self, u, v, weight=1):
self.graph[u].append((v, weight))
if not self.directed:
self.graph[v].append((u, weight))
def get_neighbors(self, v):
return self.graph[v]
def bfs(self, start):
"""Breadth-first search - O(V+E)"""
visited = set([start])
queue = deque([start])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor, _ in self.graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
def dfs(self, start):
"""Depth-first search - O(V+E)"""
visited = set()
result = []
def dfs_helper(node):
visited.add(node)
result.append(node)
for neighbor, _ in self.graph[node]:
if neighbor not in visited:
dfs_helper(neighbor)
dfs_helper(start)
return result
def has_path(self, src, dst):
"""Check if path exists between two nodes"""
visited = set()
stack = [src]
while stack:
node = stack.pop()
if node == dst:
return True
if node not in visited:
visited.add(node)
for neighbor, _ in self.graph[node]:
stack.append(neighbor)
return False
# Adjacency Matrix (for dense graphs)
class GraphMatrix:
def __init__(self, num_vertices):
self.V = num_vertices
self.matrix = [[0] * num_vertices for _ in range(num_vertices)]
def add_edge(self, u, v, weight=1):
self.matrix[u][v] = weight
self.matrix[v][u] = weight # Remove for directed
def has_edge(self, u, v):
return self.matrix[u][v] != 0
# Usage
g = Graph(directed=False)
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'D')
print(g.bfs('A')) # ['A', 'B', 'C', 'D']
print(g.dfs('A')) # ['A', 'B', 'D', 'C']
Adjacency List (V vertices, E edges):
Adjacency Matrix (V vertices):
Adjacency List:
Adjacency Matrix: