DSA Tutorial
🔍
Types of Graphs
Why Graph Types Matter
Every graph algorithm works correctly only on specific graph types. Understanding graph types before choosing an algorithm prevents subtle bugs and wrong answers.
ALGORITHM → REQUIRED GRAPH TYPE: BFS shortest path → Unweighted graph (all edges equal) Dijkstra's → Weighted graph, NO negative weights Bellman-Ford → Weighted graph, negative weights OK, no negative cycles Topological Sort → Directed Acyclic Graph (DAG) ONLY Bipartite Check → Undirected graph Kruskal's / Prim's MST → Connected undirected weighted graph SCC (Kosaraju/Tarjan) → Directed graph Applying an algorithm to the wrong graph type: Topological sort on a cyclic graph → infinite loop / wrong result Dijkstra's with negative weights → incorrect shortest paths MST on disconnected graph → MST doesn't exist
Type 1: Undirected Graph
Every edge is bidirectional — if A connects to B, then B connects to A. Relationship is symmetric.
UNDIRECTED:
A ─── B ─── C
│ │
D ─────────┘
Edge (A,B) means BOTH:
A can reach B directly
B can reach A directly
REAL-WORLD EXAMPLES:
Road network (if road A→B exists, road B→A also exists)
Facebook friends (if A friends B, B friends A)
Computer network (cable between computers is bidirectional)
Telephone lines (you can call both ways)
KEY PROPERTIES:
Degree of v = number of edges incident to v
Adjacency matrix is SYMMETRIC: matrix[u][v] = matrix[v][u]
Sum of all degrees = 2 × E (handshaking lemma)
ALGORITHMS THAT WORK ON UNDIRECTED:
BFS, DFS, MST (Kruskal, Prim), Bipartite check,
Connected components, Euler path/circuit
Type 2: Directed Graph (Digraph)
Edges have a specific direction. A→B does not imply B→A.
DIRECTED:
A ──→ B ──→ C
↑ │
└─── D ←───┘
Edge A→B means:
A can reach B directly
B CANNOT reach A directly (unless edge B→A also exists)
REAL-WORLD EXAMPLES:
Web links (page A links TO page B — not necessarily back)
Twitter follows (A follows B doesn't mean B follows A)
Task dependencies (task A must complete BEFORE task B starts)
One-way streets (drive from A to B but not B to A)
Call graph (function A calls function B)
KEY PROPERTIES:
In-degree(v) = number of edges ARRIVING at v
Out-degree(v) = number of edges LEAVING from v
Sum of in-degrees = Sum of out-degrees = E
Adjacency matrix is NOT symmetric in general
ALGORITHMS FOR DIRECTED GRAPHS:
Topological sort (only on DAGs)
Strongly connected components (Kosaraju, Tarjan)
Shortest paths with direction (Dijkstra, Bellman-Ford)
Cycle detection in directed graphs
Type 3: Weighted Graph
Each edge carries a numerical value — cost, distance, time, capacity.
WEIGHTED:
A ──4── B ──2── C
│ │
7 3
│ │
D ──────5──────┘
Edge (A,B) has weight 4 — could mean:
4 km road between A and B
$4 flight cost
4 minutes travel time
4 units of capacity in a pipe
UNWEIGHTED (implicit weight = 1 for all edges):
A ─── B ─── C
│ │
D ──────────┘
NEGATIVE WEIGHTS:
Some edges can have negative weights (e.g., profit along a route)
Valid for Bellman-Ford, NOT for Dijkstra's
NEGATIVE CYCLE:
A cycle where sum of weights < 0
Makes shortest path UNDEFINED (keep going around cycle to decrease cost)
Bellman-Ford can DETECT negative cycles (but can't give shortest path)
A ──1── B
↑ │
└──(-3)─┘ ← negative cycle (1 + (-3) = -2 < 0)
ALGORITHM CHOICE BY WEIGHT TYPE:
Equal/unweighted → BFS (O(V+E))
Positive weights → Dijkstra's (O((V+E) log V))
Any weights, no neg cycle → Bellman-Ford (O(VE))
All-pairs, any weights → Floyd-Warshall (O(V³))
Type 4: Cyclic vs Acyclic Graph
A cyclic graph contains at least one cycle. An acyclic graph contains no cycles.
CYCLIC UNDIRECTED:
A ─── B
│ │
C ─── D Cycle: A─B─D─C─A
CYCLIC DIRECTED:
A ──→ B ──→ C
↑ │
└───────────┘ Directed cycle: A→B→C→A
ACYCLIC UNDIRECTED (= TREE or FOREST):
A ─── B ─── D
│
C ─── E No cycles — this is a tree/forest
ACYCLIC DIRECTED (= DAG):
A ──→ B ──→ D
│ ↑
└──→ C ─────┘ No directed cycles — DAG
KEY INSIGHT:
Undirected acyclic + connected = TREE (V-1 edges)
Undirected acyclic + possibly disconnected = FOREST
Directed acyclic = DAG
CYCLE DETECTION:
Undirected: DFS — if you reach a visited vertex (not the parent) → cycle
Directed: DFS — track recursion stack; if you revisit a node in
current DFS path → directed cycle
(visiting finished nodes is NOT a cycle in directed graphs)
Type 5: Directed Acyclic Graph (DAG)
A directed graph with no directed cycles. One of the most important graph types in computer science.
DAG EXAMPLE — Course prerequisites:
Math101 ──→ Math201 ──→ Math301
Math101 ──→ CS101 ──→ CS201
CS101 ──→ CS301
Math201 ──→ CS201
(Take Math101 before Math201, Math201 before Math301, etc.)
TOPOLOGICAL ORDER (one valid ordering):
Math101, Math201, CS101, CS301, CS201, Math301
OR: Math101, CS101, Math201, CS301, CS201, Math301
(Multiple valid orderings usually exist)
TOPOLOGICAL ORDER GUARANTEE:
For every edge u→v in the graph, u appears BEFORE v.
Only possible because there are no cycles.
PROPERTIES:
Has at least ONE vertex with in-degree 0 (source — no prerequisites)
Has at least ONE vertex with out-degree 0 (sink — no successors)
Always has a valid topological ordering
REAL-WORLD USES:
Build systems (compile A before B if B depends on A)
Task scheduling (task dependencies)
Spreadsheets (cell A depends on cell B's value)
Package managers (npm, pip — install dependencies first)
Git commit graph (each commit depends on parent commits)
UNIQUE SHORTEST PATH:
DAGs allow O(V+E) shortest path using topological order
(faster than Dijkstra's O((V+E) log V) for DAGs)
Type 6: Bipartite Graph
Vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to a vertex in V. No edges within U or within V.
BIPARTITE:
Set U: {A, B, C} Set V: {X, Y, Z}
A ─── X
A ─── Y
B ─── X
B ─── Z
C ─── Y
C ─── Z
All edges cross between U and V.
No edge connects A─B (both in U) or X─Y (both in V).
NOT BIPARTITE (odd cycle):
A ─── B
│ │
└─ C ─┘ Triangle A─B─C─A: odd cycle (length 3) → NOT bipartite
BIPARTITE ←→ NO ODD CYCLES:
A graph is bipartite if and only if it contains no odd-length cycle.
2-colorable (can color vertices with 2 colors, no two neighbors same color)
BFS BIPARTITE CHECK:
Start with any vertex, color it RED.
Color all neighbours BLUE.
Color their neighbours RED.
If any edge connects two same-colored vertices → NOT bipartite.
REAL-WORLD EXAMPLES:
Job assignment (workers U ↔ jobs V)
Movie-actor graphs (movies U ↔ actors V)
Student-course (students U ↔ courses V)
Dating apps (users U ↔ users V in heterogeneous matching)
ALGORITHMS ON BIPARTITE:
Maximum bipartite matching (Hungarian algorithm, Hopcroft-Karp)
Minimum vertex cover (König's theorem: min cover = max matching)
Maximum independent set
Java
1import java.util.*;
2
3public class BipartiteCheck {
4
5 // Returns true if graph is bipartite — BFS 2-coloring — O(V+E)
6 public static boolean isBipartite(List<List<Integer>> adj, int V) {
7 int[] color = new int[V];
8 Arrays.fill(color, -1); // -1 = uncolored
9
10 for (int start = 0; start < V; start++) {
11 if (color[start] != -1) continue; // Already colored
12
13 // BFS from this component
14 Queue<Integer> queue = new ArrayDeque<>();
15 queue.offer(start);
16 color[start] = 0; // Color 0
17
18 while (!queue.isEmpty()) {
19 int u = queue.poll();
20 for (int v : adj.get(u)) {
21 if (color[v] == -1) {
22 color[v] = 1 - color[u]; // Opposite color
23 queue.offer(v);
24 } else if (color[v] == color[u]) {
25 return false; // Same color → odd cycle → NOT bipartite
26 }
27 }
28 }
29 }
30 return true;
31 }
32
33 public static void main(String[] args) {
34 // Bipartite graph: 0-1-2-3 square
35 List<List<Integer>> bipartite = new ArrayList<>();
36 for (int i = 0; i < 4; i++) bipartite.add(new ArrayList<>());
37 bipartite.get(0).add(1); bipartite.get(1).add(0);
38 bipartite.get(1).add(2); bipartite.get(2).add(1);
39 bipartite.get(2).add(3); bipartite.get(3).add(2);
40 bipartite.get(3).add(0); bipartite.get(0).add(3);
41 System.out.println("Square (0-1-2-3-0): " + isBipartite(bipartite, 4)); // true
42
43 // Not bipartite: triangle 0-1-2-0
44 List<List<Integer>> triangle = new ArrayList<>();
45 for (int i = 0; i < 3; i++) triangle.add(new ArrayList<>());
46 triangle.get(0).add(1); triangle.get(1).add(0);
47 triangle.get(1).add(2); triangle.get(2).add(1);
48 triangle.get(2).add(0); triangle.get(0).add(2);
49 System.out.println("Triangle (0-1-2-0): " + isBipartite(triangle, 3)); // false
50 }
51}Output:
Square (0-1-2-3-0): true
Triangle (0-1-2-0): false
K2,3: true
Type 7: Complete Graph
Every pair of distinct vertices is connected by a unique edge. Maximum possible edges.
COMPLETE GRAPHS:
K₂: A─B (1 edge)
K₃: A─B K₃ = triangle
\│
C (3 edges)
K₄: A
/│\
/ │ \
B──┼──D (6 edges)
\ │ /
\│/
C
K₅: 10 edges, K₆: 15 edges, Kₙ: n(n-1)/2 edges
FORMULA:
Vertices: n
Edges: n(n-1)/2 (undirected)
n(n-1) (directed, one edge each way)
Each vertex degree: n-1
REAL-WORLD USES:
Network routing (every node can reach every other directly)
Cliques in social networks (everyone in the group knows everyone else)
Worst case for many graph algorithms
PROPERTY: Complete graph Kₙ is the densest simple graph possible.
Adding one more edge to Kₙ is impossible without a parallel edge.
Type 8: Connected vs Disconnected Graph
CONNECTED (one component):
A ─── B ─── C
│ │
D ─────────┘
From ANY vertex, you can reach EVERY other vertex.
DISCONNECTED (multiple components):
A ─── B E ─── F
│ │
C ─── D G ────┘ H
3 components: {A,B,C,D}, {E,F,G}, {H}
Cannot reach A from E. Cannot reach H from anywhere else.
WEAKLY vs STRONGLY CONNECTED (directed graphs):
WEAKLY CONNECTED:
Connected if you IGNORE edge directions.
A ──→ B ──→ C ──→ D (directed path A to D, but D can't reach A)
Weakly connected ✓ (undirected version is connected)
NOT strongly connected ✗
STRONGLY CONNECTED:
From EVERY vertex, can reach EVERY other vertex (following directions).
A ──→ B ──→ C
↑ │
└───────────┘ Cycle visits all — strongly connected ✓
STRONGLY CONNECTED COMPONENTS (SCCs):
Maximal subgraphs that are strongly connected.
Found using Kosaraju's or Tarjan's algorithm — O(V+E).
CONNECTED CHECK:
Run BFS/DFS from any vertex.
If ALL vertices are visited → connected.
Otherwise → disconnected (multiple components).
Type 9: Tree and Forest
A tree is a connected undirected acyclic graph. A forest is a collection of trees (disconnected acyclic graph).
TREE (connected acyclic):
A
/ \
B C
/ \ \
D E F
Properties:
n vertices, n-1 edges (EXACTLY)
Connected (one component)
No cycles
Exactly ONE path between any two vertices
Removing any edge DISCONNECTS the tree
Adding any edge CREATES a cycle
FOREST (disconnected acyclic):
A E ─── F
/ \ \
B C G
Two trees = one forest
n vertices, n-k edges where k = number of trees (components)
SPANNING TREE:
A subgraph of a graph G that:
Contains ALL vertices of G
Is a tree (connected, acyclic)
Uses exactly V-1 edges from G
A graph has a spanning tree iff it is CONNECTED.
MINIMUM SPANNING TREE (MST):
Spanning tree with minimum total edge weight.
Found by Kruskal's or Prim's algorithm — O(E log E).
Type 10: Sparse vs Dense Graph
SPARSE GRAPH (E much less than V²):
Rule of thumb: E ≈ O(V) or E ≈ O(V log V)
Most real-world graphs are sparse.
Examples:
Road network: ~2-4 edges per city E ≈ 2V
Social network: ~100-500 friends each E ≈ 200V
Web graph: ~10-30 links per page E ≈ 20V
Grid graph: 4 edges per cell E = 4V
DENSE GRAPH (E close to V²):
Rule of thumb: E ≈ O(V²)
Rare in practice; common in algorithm worst-case analysis.
Examples:
Complete graph Kₙ: E = n(n-1)/2 ≈ n²/2
Airline routes (hubs): most airports connect to most others
Small social cliques: friend groups where everyone knows everyone
WHY IT MATTERS:
Algorithm Sparse (E≈V) Dense (E≈V²)
──────────────────────────────────────────────────
BFS/DFS O(V+E) = O(V) O(V+V²) = O(V²)
Dijkstra (adj list) O(V log V) O(V² log V)
Dijkstra (matrix) O(V²) O(V²)
Floyd-Warshall O(V³) O(V³)
Kruskal's (adj list) O(V log V) O(V² log V)
REPRESENTATION CHOICE:
Sparse → Adjacency LIST (O(V+E) space — efficient)
Dense → Adjacency MATRIX (O(V²) space — comparable to list, O(1) lookup)
Type 11: Multigraph and Simple Graph
SIMPLE GRAPH:
No self-loops (edge from vertex to itself)
No parallel edges (multiple edges between same pair)
Most algorithms assume simple graphs.
A ─── B ─── C ← simple graph
│ │
D ──────────┘
MULTIGRAPH:
Allows parallel edges (multiple edges between same pair)
Allows self-loops (edge A─A)
A ═══ B ─── C ← double edge between A and B
│ │
A ──(self)──┘ ← self-loop at A
PSEUDOGRAPH:
Multigraph that also allows self-loops.
REAL-WORLD MULTIGRAPH EXAMPLES:
Road network (highway AND local road between same two cities)
Transportation (multiple train lines between two stations)
Electrical circuits (multiple wires/resistors in parallel)
Communication networks (redundant connections for reliability)
NOTE: Adjacency matrix cannot represent multigraphs with a single number
— you'd need matrix[u][v] = count of parallel edges (integer) or
a more complex structure. Adjacency list handles them naturally.
Type 12: Planar Graph
A graph that can be drawn on a plane without any edges crossing.
PLANAR: NOT PLANAR:
A K₅ (5 vertices, all connected)
/ \ — impossible to draw without crossing
B C edges in a plane
\ /
D
Can be drawn with no edge crossings.
EULER'S FORMULA for connected planar graphs:
V - E + F = 2
where F = number of faces (regions including outer infinite face)
Example: triangle A-B-C
V=3, E=3, F=2 (inner face + outer face)
3 - 3 + 2 = 2 ✓
PLANARITY CONSTRAINTS:
Any planar graph: E ≤ 3V - 6 (for V ≥ 3)
Bipartite planar: E ≤ 2V - 4
K₅ and K₃,₃ are the two fundamental NON-PLANAR graphs.
By Kuratowski's theorem: a graph is non-planar iff it contains
K₅ or K₃,₃ as a minor/subdivision.
REAL-WORLD USE:
Circuit board design (non-crossing wire routes)
Map coloring (four colors suffice for any planar map — Four Color Theorem)
Graph Types at a Glance
TYPE KEY PROPERTY MAIN USE / ALGORITHM ───────────────────────────────────────────────────────────────────────────── Undirected Symmetric edges BFS, DFS, MST, matching Directed One-way edges Topological sort, SCC Weighted Edge costs/distances Dijkstra, Bellman-Ford Unweighted All edges equal BFS shortest path Cyclic Contains a cycle Cycle detection Acyclic No cycles Trees, topological sort DAG Directed + Acyclic Scheduling, DP on graphs Bipartite Two-set partition Matching, coloring Complete Every pair connected Worst-case analysis Sparse E << V² Adjacency list Dense E ≈ V² Adjacency matrix Connected One component Most algorithms assume Disconnected Multiple components Component analysis Tree Connected + acyclic Hierarchy, spanning tree Forest Disjoint trees Union-Find structure Multigraph Parallel edges / self-loops Transport, circuits Planar No crossing edges Circuit design, maps
Real-World Graph Type Mapping
PROBLEM GRAPH TYPE KEY ALGORITHM ────────────────────────────────────────────────────────────────────────── Shortest route (Google Maps) Weighted directed Dijkstra's Social connections (Facebook) Undirected unweighted BFS Twitter follows Directed unweighted DFS, SCC Course prerequisites DAG Topological sort Job-worker assignment Bipartite Max bipartite matching Network reliability Undirected weighted MST (Kruskal/Prim) Deadlock detection (OS) Directed Cycle detection Web page ranking (PageRank) Directed Random walk, eigenvector Circuit board wiring Planar Planarity testing Package dependencies DAG Topological sort Virus spread (epidemiology) Undirected weighted BFS with weights
Common Mistakes
Applying topological sort to a cyclic graph. Topological sort is ONLY defined for DAGs. If you run Kahn's algorithm (BFS-based) on a cyclic graph, not all vertices will be processed — the remaining unprocessed vertices form the cycle. If you use DFS-based topological sort, you'll get a wrong ordering. Always detect cycles first or verify the graph is a DAG.
Using Dijkstra's on a graph with negative weights. Dijkstra's greedy approach assumes once a vertex is settled, its shortest path is finalized. Negative edges can create shorter paths through "longer" routes discovered later — violating Dijkstra's assumption. Use Bellman-Ford for graphs with negative weights (O(VE)).
Confusing weak and strong connectivity for directed graphs. A directed path graph A→B→C is weakly connected (undirected version is connected) but NOT strongly connected (you can't reach A from C). SCC algorithms find strongly connected components. For problems asking "can every node reach every other node," you need strong connectivity.
Assuming all graphs are connected. Many problems give disconnected graphs. Always run BFS/DFS for EACH unvisited vertex (outer loop over all vertices) to handle all components. Starting from only one vertex misses isolated components.
Treating a tree as a special structure separate from graphs. A tree is a graph — a connected acyclic undirected graph. Graph algorithms (BFS, DFS) work on trees. Trees have the special property of V-1 edges. Confusing "tree" (data structure with parent pointers) and "tree" (graph theory definition) is common — in graph theory, a tree has no explicit root and all edges are undirected unless specified otherwise.
Summary
Graph types are not mutually exclusive — a graph can simultaneously be directed, weighted, cyclic, and sparse.
The two primary dimensions:
- ›Direction: undirected (symmetric) vs directed (one-way)
- ›Weight: unweighted (equal edges) vs weighted (numeric edge values)
Special structural types:
- ›Acyclic: no cycles — enables topological sort, DAG shortest path
- ›DAG: directed + acyclic — scheduling, dependency, DP on graphs
- ›Bipartite: two-set partition, no odd cycles — matching algorithms
- ›Complete: every pair connected — densest possible graph
- ›Tree: connected acyclic — unique paths, MST, hierarchical structures
Density determines representation:
- ›Sparse (E << V²) → adjacency list — O(V+E) space
- ›Dense (E ≈ V²) → adjacency matrix — O(1) edge lookup
Algorithm selection by graph type:
| Algorithm | Requires |
|---|---|
| BFS shortest path | Unweighted |
| Dijkstra's | Weighted, no negative edges |
| Bellman-Ford | Weighted, negative edges OK, no negative cycle |
| Topological sort | DAG only |
| Bipartite check | Undirected |
| Kruskal's / Prim's | Connected undirected weighted |
| SCC (Kosaraju/Tarjan) | Directed |
In the next topic you will explore Graph DFS — depth-first traversal, recursive and iterative implementations, cycle detection, and connected components.
Suggested Quiz
A Directed Acyclic Graph (DAG) is used for topological sort. What property makes topological sort ONLY possible on DAGs?
1/6