A graph G = (V, E) is a data structure consisting of a set of vertices (nodes) V and a set of edges E connecting pairs of vertices. Graphs model real-world relationships: social networks, road maps, computer networks, dependency trees, and more.
Type
Description
Example
Undirected
Edges have no direction
Facebook friendships
Directed (Digraph)
Edges have direction (A→B ≠B→A)
Twitter follows, web links
Weighted
Edges have a cost/weight
Road distances, network latency
Unweighted
All edges have equal weight
Social connections
Cyclic
Contains at least one cycle
Road network
Acyclic (DAG)
No cycles
Task scheduling, Git commits
Graph Representations
Representation
Space
Add Edge
Check Edge
Best for
Adjacency Matrix
O(V²)
O(1)
O(1)
Dense graphs
Adjacency List
O(V + E)
O(1)
O(degree)
Sparse graphs
Edge List
O(E)
O(1)
O(E)
Kruskal's MST
Graph Representations — Adjacency List and Matrix
import java.util.*;
public class Graph {
// Adjacency List representation — O(V + E) space
static class GraphList {
int V;
List<List<Integer>> adj;
GraphList(int v) {
V = v;
adj = new ArrayList<>();
for (int i = 0; i < v; i++) adj.add(new ArrayList<>());
}
void addEdge(int u, int v) {
adj.get(u).add(v);
adj.get(v).add(u); // undirected: add both directions
}
void printGraph() {
for (int i = 0; i < V; i++) {
System.out.print(i + " → " + adj.get(i));
System.out.println();
}
}
}
// Adjacency Matrix representation — O(V²) space
static class GraphMatrix {
int V;
int[][] matrix;
GraphMatrix(int v) {
V = v;
matrix = new int[v][v];
}
void addEdge(int u, int v) {
matrix[u][v] = 1;
matrix[v][u] = 1; // undirected
}
void printMatrix() {
System.out.print(" ");
for (int i = 0; i < V; i++) System.out.print(i + " ");
System.out.println();
for (int i = 0; i < V; i++) {
System.out.print(i + " ");
for (int j = 0; j < V; j++) System.out.print(matrix[i][j] + " ");
System.out.println();
}
}
}
public static void main(String[] args) {
// Graph: 0-1, 0-2, 1-2, 1-3, 2-4
GraphList gl = new GraphList(5);
gl.addEdge(0, 1); gl.addEdge(0, 2);
gl.addEdge(1, 2); gl.addEdge(1, 3); gl.addEdge(2, 4);
System.out.println("Adjacency List:");
gl.printGraph();
GraphMatrix gm = new GraphMatrix(5);
gm.addEdge(0, 1); gm.addEdge(0, 2);
gm.addEdge(1, 2); gm.addEdge(1, 3); gm.addEdge(2, 4);
System.out.println("\nAdjacency Matrix:");
gm.printMatrix();
}
}