DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Compare adjacency matrix, adjacency list, and edge list representations with code implementations and space-time tradeoff analysis.
The Representation Problem
Before running any graph algorithm, you need to store the graph in memory. The choice of representation dramatically affects both performance and code simplicity. There are three main approaches, and choosing wrong can turn an O(V+E) algorithm into O(V²).
Adjacency Matrix
An adjacency matrix is a 2D array of size V×V where matrix[i][j] = 1 if there is an edge from vertex i to vertex j, and 0 otherwise. For weighted graphs, store the weight instead of 1.
Example
Graph: Matrix:
0 --- 1 0 1 2 3
| | 0 [ 0, 1, 1, 0 ]
2 --- 3 1 [ 1, 0, 0, 1 ]
2 [ 1, 0, 0, 1 ]
3 [ 0, 1, 1, 0 ]
Python Implementation
Example
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 graph
def has_edge(self, u, v):
return self.matrix[u][v] != 0
def get_neighbors(self, u):
return [v for v in range(self.V) if self.matrix[u][v] != 0]
# Usage
g = GraphMatrix(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
print(g.get_neighbors(0)) # [1, 2]
C++ Implementation
Example
#include <vector>
using namespace std;
class GraphMatrix {
int V;
vector<vector<int>> matrix;
public:
GraphMatrix(int v) : V(v), matrix(v, vector<int>(v, 0)) {}
void addEdge(int u, int v, int weight = 1) {
matrix[u][v] = weight;
matrix[v][u] = weight;
}
bool hasEdge(int u, int v) {
return matrix[u][v] != 0;
}
};
When to Use Adjacency Matrix
- Dense graphs where |E| ≈ V²
- Need O(1) edge existence check
- Small graphs (V < 1000 typically)
- Floyd-Warshall algorithm (needs all-pairs access)
Adjacency List
An adjacency list stores, for each vertex, a list of its neighbors. This is the most common representation and works well for sparse graphs.
| Graph | Adjacency List: |
| 0 --- 1 0 | [1, 2] |
| | | 1 | [0, 3] |
| 2 --- 3 2 | [0, 3] |
| 3 | [1, 2] |
Python Implementation
Example
from collections import defaultdict
class GraphList:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v, weight=1):
self.graph[u].append((v, weight))
self.graph[v].append((u, weight)) # Remove for directed
def get_neighbors(self, u):
return self.graph[u]
def has_edge(self, u, v):
return any(neighbor == v for neighbor, _ in self.graph[u])
# Usage
g = GraphList()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
print(g.get_neighbors(0)) # [(1, 1), (2, 1)]
C++ Implementation
Example
#include <vector>
#include <list>
using namespace std;
class GraphList {
int V;
vector<list<pair<int,int>>> adj;
public:
GraphList(int v) : V(v), adj(v) {}
void addEdge(int u, int v, int weight = 1) {
adj[u].push_back({v, weight});
adj[v].push_back({u, weight});
}
const list<pair<int,int>>& getNeighbors(int u) {
return adj[u];
}
};
When to Use Adjacency List
- Sparse graphs (most real-world graphs)
- BFS/DFS traversals
- Need to iterate over neighbors efficiently
- Memory is a concern
Edge List
An edge list simply stores all edges as a list of (u, v, weight) tuples. It is the simplest representation but the least efficient for most operations.
python example
class GraphEdgeList:
def __init__(self):
self.edges = []
self.vertices = set()
def add_edge(self, u, v, weight=1):
self.edges.append((u, v, weight))
self.vertices.add(u)
self.vertices.add(v)
def get_neighbors(self, u):
# O(E) - inefficient!
neighbors = []
for a, b, w in self.edges:
if a == u: neighbors.append((b, w))
elif b == u: neighbors.append((a, w))
return neighborsWhen to Use Edge List
- Kruskal's algorithm (sort edges by weight)
- Bellman-Ford (iterate over all edges)
- When you just need to store/transmit the graph
- Very simple problems with few operations
Comparison Table
| Operation | Adj. Matrix | Adj. List | Edge List |
|---|---|---|---|
| Space | O(V²) | O(V + E) | O(E) |
| Add Edge | O(1) | O(1) | O(1) |
| Remove Edge | O(1) | O(degree) | O(E) |
| Check Edge | O(1) | O(degree) | O(E) |
| All Neighbors | O(V) | O(degree) | O(E) |
| Iterate All Edges | O(V²) | O(V + E) | O(E) |
Practical Advice
For competitive programming and interviews, adjacency list is your default choice. It works efficiently with BFS, DFS, Dijkstra, and most graph algorithms. Switch to adjacency matrix only for dense graphs or when you need O(1) edge lookup. Use edge list only for algorithms that explicitly process edges (Kruskal's, Bellman-Ford).
In Python, defaultdict(list) is the quickest way to set up an adjacency list. In C++, vector<vector<pair<int,int>>> is the standard choice for competitive programming due to cache friendliness.
Space Complexity in Practice
For a graph with 10,000 vertices and 50,000 edges:
- Adjacency Matrix: 10,000 × 10,000 = 100 million entries (~400 MB for int)
- Adjacency List: ~10,000 + 100,000 entries (~1 MB)
- Edge List: 50,000 entries (~600 KB)
The difference is dramatic. Most real-world graphs are sparse, which is why adjacency lists dominate in practice.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Graph Representation Methods.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, graphs, graph, representation
Related Data Structures & Algorithms Topics
Continue learning this concept
GraphsGraph Interview ProblemsMaster 12 essential graph interview problems with clear approaches, patterns, and solutions for coding interviews at top tech companies.GraphsGraph Data Structure FundamentalsMaster graph theory basics including vertices, edges, types of graphs, degree, paths, cycles, and connected components with clear examples.GraphsBellman-Ford AlgorithmLearn Bellman-Ford shortest path algorithm that handles negative edge weights, detects negative cycles, with complete implementation and analysis.GraphsBreadth-First Search (BFS) AlgorithmLearn BFS traversal with queue-based implementation, level-order processing, shortest path in unweighted graphs, and real applications.GraphsDepth-First Search (DFS) AlgorithmMaster DFS traversal using recursion and stack, understand pre/post ordering, cycle detection, and connected component discovery.GraphsDijkstra\Master Dijkstra\