note: a TREE is an acyclic connected graph (see L10 BST and L11 AVL Tree for tree-based data structures)
Terminologies
- Sparse / Dense
- Sparse = not so many edges
- Dense = many edges
- Complete Graph
- Simple graph with N vertices and NC2 edges
- In/Out Degree of a vertex
- number of in/out edges from a vertex
- (Simple) Cycle
- path that starts and ends with the same vertex and with no repeated vertices except start/end vertex and no repeated edges
- involves 3 or more unique vertices
- (Simple) Directed Cycle
- same but the edges in the cycle are directed and in the same direction
- involves 2 or more unique vertices
- Component
- maximal group of vertices in an undirected graph that can visit each other via some path
- Connected graph
- undirected graph with 1 component
- NOTE: undirected simple graph DISCONNECTED if E ≤ V-1
- Tree
- connected graph - one unique path between any pair of vertices
- Bipartite graph
- undirected graph where we can partition the vertices into two sets so that there are no edges between members of the same set
Graph Data Structures
| Description | Uses | |
|---|---|---|
| Adjacency Matrix | - if graph is undirected, matrix will be mirrored diagonally - space complexity: O(V^2) - better for dense graphs / Floyd Warshall’s → L17 APSP → if sparse, a lot of space wasted | ✅ counting number of vertices (num of rows) ✅ if edge(u,v) exist = O(1) - enumerating neighbours = O(V) where v is number of vertices - counting number of edges = O(V^2) (count all non-zero entries) |
| Adjacency List | - for each vertex i, AdjList[i] stores list of i’s neighbours - for weighted graphs, it stores pair(neighbour, weight) - sum of list.lengths for undirected = 2E - space complexity = O(V+E) ✅ O(V+E) to traverse each vertex and its neighbours worst case = O(V^2) - better for sparse graphs / Dijkstra’s → L15-16 SSSP / DFS BFS → L13 Graph Traversal / Prim’s / Kruskal’s → L14 MST | ✅ counting number of vertices (num of rows) ✅ enumerating neighbours O(k) / O(deg(v)) where k is num of neighbours - if edge(u, v) exists = O(k) / O(deg(v)) - counting number of edges = O(V) (sum the length of all V lists) |
| Edge List | - For each edge i, EdgeList[i] stores (u, v, weight) - space complexity O(E) / O(V+E)? - used in Kruskal’s → L14 MST and Bellman-Ford → L15-16 SSSP | ✅ counting num of edges = O(1) |
Adjacency Matrix
int v = NUM_V;
int[][] AdjMatrix = new int[V][V];Adjacency List
- fyi: each list of neighbours in ascending order
ArrayList<ArrayList<IntegerPair>> AdjList =
new ArrayList<ArrayList<IntegerPair>>();Edge List
ArrayList<IntegerTriple> EdgeList =
new ArrayList<IntegerTriple>();