Graph Representation in Data Structures – When we work with graphs in programming, we need a way to store the graph inside the computer. This is called Graph Representation. There are two main ways to represent a graph:
- Adjacency Matrix
- Adjacency List
Why do we need Graph Representation?
A graph is made of:
- Nodes (vertices)
- Connections (edges)
But a computer cannot directly understand a diagram. So we convert the graph into a format that a program can use.
1. Adjacency Matrix
An Adjacency Matrix is a 2D array (table).
- Rows → Nodes
- Columns → Nodes
- Value → Shows connection (0 or 1)
Example Graph:
A — B
| |
C — DMatrix Representation:
A B C D
A [ 0 1 1 0 ]
B [ 1 0 0 1 ]
C [ 1 0 0 1 ]
D [ 0 1 1 0 ]- 1 means a connection exists
- 0 means no connection
Java Code – Adjacency Matrix
public class GraphMatrix {
int vertices;
int[][] matrix;
public GraphMatrix(int v) {
vertices = v;
matrix = new int[v][v];
}
// Add edge
public void addEdge(int source, int destination) {
matrix[source][destination] = 1;
matrix[destination][source] = 1; // undirected graph
}
// Print matrix
public void printGraph() {
System.out.println("Adjacency Matrix:");
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
GraphMatrix g = new GraphMatrix(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.printGraph();
}
}
Advantages of Adjacency Matrix
- Easy to understand
- Fast edge checking
- Good for small graphs
Disadvantages
- Uses more memory
- Not good for large graphs
2. Adjacency List
Instead of storing a full matrix, we only store connections. An Adjacency List stores:
Each node → list of its neighbors
Example Graph:
A — B
| |
C — DAdjacency List:
A → B, C
B → A, D
C → A, D
D → B, C Java Code – Adjacency List
import java.util.*;
public class GraphList {
int vertices;
LinkedList<Integer>[] list;
public GraphList(int v) {
vertices = v;
list = new LinkedList[v];
for (int i = 0; i < v; i++) {
list[i] = new LinkedList<>();
}
}
// Add edge
public void addEdge(int source, int destination) {
list[source].add(destination);
list[destination].add(source); // undirected
}
// Print graph
public void printGraph() {
System.out.println("Adjacency List:");
for (int i = 0; i < vertices; i++) {
System.out.print(i + " → ");
for (int node : list[i]) {
System.out.print(node + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
GraphList g = new GraphList(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.printGraph();
}
}
Advantages of Adjacency List
- Uses less memory
- Best for large graphs
- Most commonly used
Disadvantages
- Slightly complex
- Edge checking takes more time
Adjacency Matrix vs List
| Feature | Matrix | List |
|---|---|---|
| Memory | High | Low |
| Speed (check edge) | Fast | Slower |
| Use case | Small graph | Large graph |
FAQ: Quick Answer
What is graph representation?
Graph representation is a way to store a graph in a computer using structures like an adjacency matrix or adjacency list.
Which graph representation is better?
An adjacency list is better for large graphs, while an adjacency matrix is easier for small graphs.