Edge List
About
An Edge List is a simple way to represent a graph using a list of edges, where:
Each edge is stored as a pair (or triplet for weighted graphs) representing the two connected vertices.
It is best for sparse graphs because it stores only edges and not all possible connections.
Why Use an Edge List?
Space Efficient for Sparse Graphs: Only stores the edges, making it O(E) space complexity.
Simple Representation: Easier to implement and manipulate compared to adjacency matrices.
Best for Edge-Centric Operations: Useful when iterating over edges rather than neighbours.
Structure of an Edge List
An Edge List consists of a list of edges, where each edge is stored as a pair (u, v) for an unweighted graph or triplet (u, v, w) for a weighted graph.
Example Graph Representation
Consider a graph with 4 vertices (V = 4) and 4 edges (0→1, 0→2, 1→3, 2→3):
Edges
Start Vertex
End Vertex
Weight (if weighted)
(0, 1)
0
1
-
(0, 2)
0
2
-
(1, 3)
1
3
-
(2, 3)
2
3
-
For a weighted version of the graph with edge weights:
Edges
Start Vertex
End Vertex
Weight
(0, 1, 10)
0
1
10
(0, 2, 20)
0
2
20
(1, 3, 30)
1
3
30
(2, 3, 40)
2
3
40
Implementation using an Edge List
Code
import java.util.*;
class Edge {
int src, dest, weight;
// Constructor for an unweighted edge
public Edge(int src, int dest) {
this.src = src;
this.dest = dest;
this.weight = 1; // Default weight (for unweighted graphs)
}
// Constructor for a weighted edge
public Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
}
class Graph {
private List<Edge> edgeList; // List of edges
private int vertices; // Number of vertices
public Graph(int vertices) {
this.vertices = vertices;
this.edgeList = new ArrayList<>();
}
// Method to add an unweighted edge
public void addEdge(int src, int dest) {
edgeList.add(new Edge(src, dest));
}
// Method to add a weighted edge
public void addEdge(int src, int dest, int weight) {
edgeList.add(new Edge(src, dest, weight));
}
// Method to remove an edge
public void removeEdge(int src, int dest) {
edgeList.removeIf(edge -> edge.src == src && edge.dest == dest);
}
// Method to check if an edge exists
public boolean hasEdge(int src, int dest) {
for (Edge edge : edgeList) {
if (edge.src == src && edge.dest == dest) {
return true;
}
}
return false;
}
// Method to get all neighbors of a vertex
public List<Integer> getNeighbors(int vertex) {
List<Integer> neighbors = new ArrayList<>();
for (Edge edge : edgeList) {
if (edge.src == vertex) {
neighbors.add(edge.dest);
}
}
return neighbors;
}
// Method to print the graph
public void printGraph() {
System.out.println("Graph (Edge List Representation):");
for (Edge edge : edgeList) {
System.out.println(edge.src + " --(" + edge.weight + ")--> " + edge.dest);
}
}
public static void main(String[] args) {
Graph graph = new Graph(5);
// Add unweighted edges
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
// Add weighted edges
graph.addEdge(1, 4, 10);
graph.addEdge(2, 4, 15);
// Print the graph
graph.printGraph();
// Check if an edge exists
System.out.println("Edge (1 -> 4) exists? " + graph.hasEdge(1, 4));
// Remove an edge and print the graph again
graph.removeEdge(1, 4);
System.out.println("After removing edge (1 -> 4):");
graph.printGraph();
// Get neighbors of vertex 3
System.out.println("Neighbors of vertex 3: " + graph.getNeighbors(3));
}
}Output
Graph (Edge List Representation):
0 --(1)--> 1
0 --(1)--> 2
1 --(1)--> 3
2 --(1)--> 3
3 --(1)--> 4
1 --(10)--> 4
2 --(15)--> 4
Edge (1 -> 4) exists? true
After removing edge (1 -> 4):
Graph (Edge List Representation):
0 --(1)--> 1
0 --(1)--> 2
1 --(1)--> 3
2 --(1)--> 3
3 --(1)--> 4
2 --(15)--> 4
Neighbors of vertex 3: [4]
Time Complexity Analysis
Adding an Edge
O(1)
Removing an Edge
O(E)
Checking if an Edge Exists
O(E)
Getting Neighbours
O(E)
Iterating All Edges
O(E)
Space Complexity
O(E)
Weighted Graph Implementation
If the graph is weighted, we store (src, dest, weight) instead of just (src, dest).
Code
import java.util.*;
class Edge {
int src, dest, weight;
// Constructor for a weighted edge
public Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
}
class Graph {
private List<Edge> edgeList; // List of edges
private int vertices; // Number of vertices
public Graph(int vertices) {
this.vertices = vertices;
this.edgeList = new ArrayList<>();
}
// Method to add a weighted edge
public void addEdge(int src, int dest, int weight) {
edgeList.add(new Edge(src, dest, weight));
}
// Method to remove an edge
public void removeEdge(int src, int dest) {
edgeList.removeIf(edge -> edge.src == src && edge.dest == dest);
}
// Method to check if an edge exists
public boolean hasEdge(int src, int dest) {
for (Edge edge : edgeList) {
if (edge.src == src && edge.dest == dest) {
return true;
}
}
return false;
}
// Method to get the weight of an edge
public int getEdgeWeight(int src, int dest) {
for (Edge edge : edgeList) {
if (edge.src == src && edge.dest == dest) {
return edge.weight;
}
}
return -1; // Return -1 if the edge doesn't exist
}
// Method to get all neighbors of a vertex
public List<Integer> getNeighbors(int vertex) {
List<Integer> neighbors = new ArrayList<>();
for (Edge edge : edgeList) {
if (edge.src == vertex) {
neighbors.add(edge.dest);
}
}
return neighbors;
}
// Method to print the graph
public void printGraph() {
System.out.println("Graph (Weighted Edge List Representation):");
for (Edge edge : edgeList) {
System.out.println(edge.src + " --(" + edge.weight + ")--> " + edge.dest);
}
}
public static void main(String[] args) {
Graph graph = new Graph(5);
// Add weighted edges
graph.addEdge(0, 1, 5);
graph.addEdge(0, 2, 10);
graph.addEdge(1, 3, 2);
graph.addEdge(2, 3, 4);
graph.addEdge(3, 4, 7);
// Print the graph
graph.printGraph();
// Check if an edge exists
System.out.println("Edge (1 -> 3) exists? " + graph.hasEdge(1, 3));
// Get the weight of an edge
System.out.println("Weight of edge (2 -> 3): " + graph.getEdgeWeight(2, 3));
// Remove an edge and print the graph again
graph.removeEdge(2, 3);
System.out.println("After removing edge (2 -> 3):");
graph.printGraph();
// Get neighbors of vertex 3
System.out.println("Neighbors of vertex 3: " + graph.getNeighbors(3));
}
}Output
Graph (Weighted Edge List Representation):
0 --(5)--> 1
0 --(10)--> 2
1 --(2)--> 3
2 --(4)--> 3
3 --(7)--> 4
Edge (1 -> 3) exists? true
Weight of edge (2 -> 3): 4
After removing edge (2 -> 3):
Graph (Weighted Edge List Representation):
0 --(5)--> 1
0 --(10)--> 2
1 --(2)--> 3
3 --(7)--> 4
Neighbors of vertex 3: [4]
Time Complexity Analysis
Operation
Time Complexity
Explanation
addEdge(int src, int dest, int weight)
O(1)
Adding an edge to an ArrayList is a constant-time operation (appending to the list).
removeEdge(int src, int dest)
O(E)
The removeIf() method checks each edge, so it may iterate over all edges in the list.
hasEdge(int src, int dest)
O(E)
It iterates over all edges to check if a specific edge exists.
getEdgeWeight(int src, int dest)
O(E)
Similar to hasEdge(), it checks each edge to find the weight of a matching edge.
getNeighbours(int vertex)
O(E)
Checks all edges to find neighbours of the given vertex.
printGraph()
O(E)
Iterates through all edges to print them, making it linear in the number of edges.
Last updated