Converting between Edge List and Adjacency List Graph Representation

In this article, we will explore on how to convert from edge list representation of a graph to adjacency list representation and vice versa.

What is an Edge List?

An edge list is a way of representing a graph by listing all the edges (connections) between the nodes (vertices) of the graph. Each edge is represented as a pair of node IDs, indicating the two nodes that are connected by that edge. The edge list is typically stored as a list or array of these node pairs.

For example, if we have a graph with nodes A, B, C, and D, and the edges (A, B), (B, C), and (C, D), the edge list would be:

[(A, B), (B, C), (C, D)]

Refer to this article for more information: Edge List representation of a Graph

What is an Adjacency List?

An adjacency list is another way of representing a graph, where each node is associated with a list of its neighboring nodes (the nodes it is connected to). This representation is often more efficient for sparse graphs, where each node has only a few connections.

For the same example graph above, the adjacency list would be:

A: [B]
B: [A, C]
C: [B, D]
D: [C]

Refer to this article for more information: Adjacency List representation of a Graph

Example Graph Used For Conversion

For the examples below, a graph with the following nodes/vertices and edges is considered:

vertices = ['A', 'B', 'C', 'D', 'E', 'F']

edges = [['A','B'], ['A','C'], ['B','C'], ['B','D'], ['C','E'], ['C','F']]

In programmatic representation of a graph, each node or vertex is typically assigned a number between 0 and N-1, where N is the total number of nodes in the graph. This numbering is efficient in terms of storage and also allows us to use an array to represent the adjacency list or matrix, rather than a dictionary or hash table. This approach is more efficient because accessing elements in an array using the node ID/number as index is generally faster than accessing elements in a hash table or dictionary. Below is how the vertices and edges look like after optimizing the representation:

            A  B  C  D  E  F
vertices = [0, 1, 2, 3, 4, 5]

edges = [[0,1], [0,2], [1,2], [1,3], [2,4], [2,5]]

Converting from Edge List to Adjacency List

To convert an edge list to an adjacency list, iterate through each edge in the edge list and build the adjacency list by adding the destination node to the neighbors list of the source node. If the graph is bidirectional, add the reverse edge as well, so an edge [source, destination] also implies that an edge [destination, source] is present. In the case of a directed graph, only add the edge as specified without the reverse.


# Function to convert edge representation to adjacency list
def convert_to_adjacency_list(edges, num_vertices):
  # Initialize an empty list of size "num_vertices"
  # To store the adjacency list of each vertex
  adjacency_list = [[] for _ in range(num_vertices)]
  
  # Iterate through the edges
  for edge in edges:
    # Get the source and destination nodes
    source = edge[0]
    destination = edge[1]
    
    # Add the destination node to the source node's list
    adjacency_list[source].append(destination)
    
    # Add the source node to the destination node's list
    # (since the graph is bidirectional)
    adjacency_list[destination].append(source)
  
  # Return the adjacency list
  return adjacency_list
  
edge_list = [[0, 1], [0, 2], [1, 2], [1, 3], [2, 4], [2, 5]]
# There are 6 vertices/nodes in total
# The first vertex/node is labelled as 0
# And the last vertex/node is labelled as 5
num_vertices = 6
adj_list = convert_to_adjacency_list(edge_list, 6)
print("For the following Edge list:")
print(edge_list)
print("Below is the Adjacency list:")
for vertex in range(num_vertices):
  print(f"{vertex} : {adj_list[vertex]}")


#include <iostream>
#include <vector>

// Function to convert edge representation to adjacency list
std::vector<std::vector<int>> convert_to_adjacency_list(const std::vector<std::pair<int, int>>& edges, int num_vertices) {
  // Initialize an empty list of size "num_vertices"
  // To store the adjacency list of each vertex
  std::vector<std::vector<int>> adjacency_list(num_vertices);
  
  // Iterate through the edges
  for (const auto& edge : edges) {
    // Get the source and destination nodes
    int source = edge.first;
    int destination = edge.second;
    
    // Add the destination node to the source node's list
    adjacency_list[source].push_back(destination);
    
    // Add the source node to the destination node's list
    // (since the graph is bidirectional)
    adjacency_list[destination].push_back(source);
  }
  
  // Return the adjacency list
  return adjacency_list;
}

int main() {
  // Example usage
  std::vector<std::pair<int, int>> edge_list = {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 4}, {2, 5}};
  int num_vertices = 6;
  
  std::vector<std::vector<int>> adj_list = convert_to_adjacency_list(edge_list, num_vertices);
  
  std::cout << "For the following Edge list:" << std::endl;
  for (const auto& edge : edge_list) {
    std::cout << "(" << edge.first << ", " << edge.second << ")" << std::endl;
  }
  
  std::cout << "Below is the Adjacency list:" << std::endl;
  for (int vertex = 0; vertex < num_vertices; ++vertex) {
    std::cout << vertex << " : ";
    for (int neighbor : adj_list[vertex]) {
      std::cout << neighbor << " ";
    }
    std::cout << std::endl;
  }
  
  return 0;
}


// Function to convert edge representation to adjacency list
function convertToAdjacencyList(edges, numVertices) {
  // Initialize an empty list of size "numVertices"
  // To store the adjacency list of each vertex
  let adjacencyList = Array.from({ length: numVertices }, () => []);

  // Iterate through the edges
  for (let edge of edges) {
    // Get the source and destination nodes
    let source = edge[0];
    let destination = edge[1];

    // Add the destination node to the source node's list
    adjacencyList[source].push(destination);

    // Add the source node to the destination node's list
    // (since the graph is bidirectional)
    adjacencyList[destination].push(source);
  }

  // Return the adjacency list
  return adjacencyList;
}

let edgeList = [[0, 1], [0, 2], [1, 2], [1, 3], [2, 4], [2, 5]];
// There are 6 vertices/nodes in total
// The first vertex/node is labelled as 0
// And the last vertex/node is labelled as 5
let numVertices = 6;
let adjList = convertToAdjacencyList(edgeList, 6);

console.log("For the following Edge list:");
console.log(edgeList);
console.log("Below is the Adjacency list:");
for (let vertex = 0; vertex < numVertices; vertex++) {
  console.log(`${vertex} : ${adjList[vertex]}`);
}


import java.util.ArrayList;
import java.util.List;

public class Main {
  // Function to convert edge representation to adjacency list
  public static List<List<Integer>> convertToAdjacencyList(int[][] edges, int numVertices) {
    // Initialize an empty list of size "numVertices"
    // To store the adjacency list of each vertex
    List<List<Integer>> adjacencyList = new ArrayList<>();
    for (int i = 0; i < numVertices; i++) {
      adjacencyList.add(new ArrayList<>());
    }

    // Iterate through the edges
    for (int[] edge : edges) {
      // Get the source and destination nodes
      int source = edge[0];
      int destination = edge[1];

      // Add the destination node to the source node's list
      adjacencyList.get(source).add(destination);

      // Add the source node to the destination node's list
      // (since the graph is bidirectional)
      adjacencyList.get(destination).add(source);
    }

    // Return the adjacency list
    return adjacencyList;
  }

  public static void main(String[] args) {
    int[][] edgeList = {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 4}, {2, 5}};
    // There are 6 vertices/nodes in total
    // The first vertex/node is labelled as 0
    // And the last vertex/node is labelled as 5
    int numVertices = 6;
    List<List<Integer>> adjList = convertToAdjacencyList(edgeList, numVertices);

    System.out.println("For the following Edge list:");
    for (int[] edge : edgeList) {
      System.out.println(edge[0] + " - " + edge[1]);
    }
    System.out.println("Below is the Adjacency list:");
    for (int vertex = 0; vertex < numVertices; vertex++) {
      System.out.println(vertex + " : " + adjList.get(vertex));
    }
  }
}

Converting from Adjacency List to Edge List

To convert from an adjacency list to an edge list, we iterate through each node and its list of neighbors in the adjacency list. For each neighbor of a node, we create an edge pair [source, destination] and add it to the edge list. Here source refers to the for which neighbors are being iterated and destination refers to the current neighbor.


# Function to convert adjacency list to edge representation
def convert_to_edge_list(adjacency_list):
  # Initialize an empty list to store the edges
  edges = []
  
  # Iterate through the adjacency list
  for vertex, neighbors in enumerate(adjacency_list):
    # Iterate through the vertices reachable from the current vertex
    for neighbor in neighbors:
      # Add the edge (vertex, neighbor) to the edges list
      edges.append((vertex, neighbor))
  
  # Return the list of edges
  return edges

adj_list = [[1, 2], [0, 2, 3], [0, 1, 4, 5], [1], [2], [2]]
edge_list = convert_to_edge_list(adj_list)
print("For the following Adjacency list:")
for vertex in range(len(adj_list)):
  print(f"{vertex} : {adj_list[vertex]}")
print("Below is the Edge list:")
print(edge_list)


#include <vector>
#include <iostream>

// Function to convert adjacency list to edge representation
std::vector<std::pair<int, int>> convert_to_edge_list(const std::vector<std::vector<int>>& adjacency_list) {
  // Initialize an empty list to store the edges
  std::vector<std::pair<int, int>> edges;

  // Iterate through the adjacency list
  for (int vertex = 0; vertex < adjacency_list.size(); vertex++) {
    // Iterate through the vertices reachable from the current vertex
    for (int neighbor : adjacency_list[vertex]) {
      // Add the edge (vertex, neighbor) to the edges list
      edges.emplace_back(vertex, neighbor);
    }
  }

  // Return the list of edges
  return edges;
}

int main() {
  // Example adjacency list
  std::vector<std::vector<int>> adj_list = {{1, 2}, {0, 2, 3}, {0, 1, 4, 5}, {1}, {2}, {2}};

  // Convert the adjacency list to an edge list
  std::vector<std::pair<int, int>> edge_list = convert_to_edge_list(adj_list);

  // Print the adjacency list
  std::cout << "For the following Adjacency list:" << std::endl;
  for (int vertex = 0; vertex < adj_list.size(); vertex++) {
    std::cout << vertex << " : ";
    for (int neighbor : adj_list[vertex]) {
      std::cout << neighbor << " ";
    }
    std::cout << std::endl;
  }

  // Print the edge list
  std::cout << "Below is the Edge list:" << std::endl;
  for (const auto& edge : edge_list) {
    std::cout << "(" << edge.first << ", " << edge.second << ")" << std::endl;
  }

  return 0;
}


// Function to convert adjacency list to edge representation
function convertToEdgeList(adjacencyList) {
  // Initialize an empty list to store the edges
  let edges = [];

  // Iterate through the adjacency list
  for (let vertex = 0; vertex < adjacencyList.length; vertex++) {
    // Iterate through the vertices reachable from the current vertex
    for (let neighbor of adjacencyList[vertex]) {
      // Add the edge (vertex, neighbor) to the edges list
      edges.push([vertex, neighbor]);
    }
  }

  // Return the list of edges
  return edges;
}

let adjList = [[1, 2], [0, 2, 3], [0, 1, 4, 5], [1], [2], [2]];
let edgeList = convertToEdgeList(adjList);
console.log("For the following Adjacency list:");
for (let vertex = 0; vertex < adjList.length; vertex++) {
  console.log(`${vertex} : ${adjList[vertex]}`);
}
console.log("Below is the Edge list:");
console.log(edgeList);


import java.util.*;

public class Main {
  // Function to convert adjacency list to edge representation
  public static List<int[]> convertToEdgeList(List<List<Integer>> adjacencyList) {
    // Initialize an empty list to store the edges
    List<int[]> edges = new ArrayList<>();
    
    // Iterate through the adjacency list
    for (int vertex = 0; vertex < adjacencyList.size(); vertex++) {
      // Iterate through the vertices reachable from the current vertex
      for (int neighbor : adjacencyList.get(vertex)) {
        // Add the edge (vertex, neighbor) to the edges list
        edges.add(new int[] {vertex, neighbor});
      }
    }
    
    // Return the list of edges
    return edges;
  }

  public static void main(String[] args) {
    // Example adjacency list
    List<List<Integer>> adjacencyList = new ArrayList<>();
    adjacencyList.add(Arrays.asList(1, 2));
    adjacencyList.add(Arrays.asList(0, 2, 3));
    adjacencyList.add(Arrays.asList(0, 1, 4, 5));
    adjacencyList.add(Arrays.asList(1));
    adjacencyList.add(Arrays.asList(2));
    adjacencyList.add(Arrays.asList(2));
    
    // Convert adjacency list to edge list
    List<int[]> edgeList = convertToEdgeList(adjacencyList);
    
    // Print the adjacency list and the edge list
    System.out.println("For the following Adjacency list:");
    for (int vertex = 0; vertex < adjacencyList.size(); vertex++) {
      System.out.println(vertex + " : " + adjacencyList.get(vertex));
    }
    System.out.println("Below is the Edge list:");
    for (int[] edge : edgeList) {
      System.out.println(Arrays.toString(edge));
    }
  }
}