Card 06/ 08
Graph Representations in Python, Java and TypeScript
One edge list turned into an adjacency list and an adjacency matrix in each language.
No standard library among Python, Java and TypeScript has a graph type, so a graph is stored in the collections each language already has. This card covers building an adjacency list and an adjacency matrix from the same edge list in all three languages, and the choices each version makes.
An edge list is a plain list of the pairs of vertices that are joined. An adjacency list keeps one list of neighbours per vertex, and an adjacency matrix is a V by V grid, V being the number of vertices, with a 1 in row u, column v when an edge joins them.
Each listing takes the undirected graph with vertices A to E and edges A-B, A-C, B-C, B-D, C-E and D-E, prints both representations, checks two edges and lists the neighbours of B. Python keeps the lists in a dictionary of lists, Java in a LinkedHashMap of ArrayList, and TypeScript in a Map of arrays. The matrix is a list of lists in Python, an int[][] in Java and an array of arrays in TypeScript, and a second map turns each vertex name into its row and column number.
The same graph stored both ways in each language
def build_adjacency_list(vertices, edges):
neighbours = {vertex: [] for vertex in vertices}
for u, v in edges:
neighbours[u].append(v)
neighbours[v].append(u)
return neighbours
def build_adjacency_matrix(vertices, edges):
index = {vertex: i for i, vertex in enumerate(vertices)}
matrix = [[0] * len(vertices) for _ in vertices]
for u, v in edges:
matrix[index[u]][index[v]] = 1
matrix[index[v]][index[u]] = 1
return index, matrix
vertices = ["A", "B", "C", "D", "E"]
edges = [("A", "B"), ("A", "C"), ("B", "C"), ("B", "D"), ("C", "E"), ("D", "E")]
neighbours = build_adjacency_list(vertices, edges)
print("adjacency list:")
for vertex in vertices:
print(f"{vertex}: {', '.join(neighbours[vertex])}")
index, matrix = build_adjacency_matrix(vertices, edges)
print("adjacency matrix:")
print(" " + " ".join(vertices))
for vertex in vertices:
print(vertex + " " + " ".join(str(cell) for cell in matrix[index[vertex]]))
print("edge B-D:", matrix[index["B"]][index["D"]] == 1)
print("edge A-E:", matrix[index["A"]][index["E"]] == 1)
print("neighbours of B:", ", ".join(neighbours["B"]))adjacency list:
A: B, C
B: A, C, D
C: A, B, E
D: B, E
E: C, D
adjacency matrix:
A B C D E
A 0 1 1 0 0
B 1 0 1 1 0
C 1 1 0 0 1
D 0 1 0 0 1
E 0 0 1 1 0
edge B-D: True
edge A-E: False
neighbours of B: A, C, Dimport java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public class GraphCode {
static Map<String, List<String>> buildAdjacencyList(List<String> vertices, String[][] edges) {
Map<String, List<String>> neighbours = new LinkedHashMap<>();
for (String vertex : vertices) {
neighbours.put(vertex, new ArrayList<>());
}
for (String[] edge : edges) {
neighbours.get(edge[0]).add(edge[1]);
neighbours.get(edge[1]).add(edge[0]);
}
return neighbours;
}
static int[][] buildAdjacencyMatrix(Map<String, Integer> index, String[][] edges) {
int[][] matrix = new int[index.size()][index.size()];
for (String[] edge : edges) {
int u = index.get(edge[0]);
int v = index.get(edge[1]);
matrix[u][v] = 1;
matrix[v][u] = 1;
}
return matrix;
}
public static void main(String[] args) {
List<String> vertices = List.of("A", "B", "C", "D", "E");
String[][] edges = {{"A", "B"}, {"A", "C"}, {"B", "C"}, {"B", "D"}, {"C", "E"}, {"D", "E"}};
Map<String, List<String>> neighbours = buildAdjacencyList(vertices, edges);
System.out.println("adjacency list:");
for (String vertex : vertices) {
System.out.println(vertex + ": " + String.join(", ", neighbours.get(vertex)));
}
Map<String, Integer> index = new HashMap<>();
for (int i = 0; i < vertices.size(); i++) {
index.put(vertices.get(i), i);
}
int[][] matrix = buildAdjacencyMatrix(index, edges);
System.out.println("adjacency matrix:");
System.out.println(" " + String.join(" ", vertices));
for (String vertex : vertices) {
StringBuilder row = new StringBuilder(vertex);
for (int cell : matrix[index.get(vertex)]) {
row.append(' ').append(cell);
}
System.out.println(row);
}
System.out.println("edge B-D: " + (matrix[index.get("B")][index.get("D")] == 1));
System.out.println("edge A-E: " + (matrix[index.get("A")][index.get("E")] == 1));
System.out.println("neighbours of B: " + String.join(", ", neighbours.get("B")));
}
}adjacency list:
A: B, C
B: A, C, D
C: A, B, E
D: B, E
E: C, D
adjacency matrix:
A B C D E
A 0 1 1 0 0
B 1 0 1 1 0
C 1 1 0 0 1
D 0 1 0 0 1
E 0 0 1 1 0
edge B-D: true
edge A-E: false
neighbours of B: A, C, Dtype Edge = readonly [string, string];
function buildAdjacencyList(vertices: readonly string[], edges: readonly Edge[]): Map<string, string[]> {
const neighbours = new Map<string, string[]>();
for (const vertex of vertices) {
neighbours.set(vertex, []);
}
for (const [u, v] of edges) {
neighbours.get(u)!.push(v);
neighbours.get(v)!.push(u);
}
return neighbours;
}
function buildAdjacencyMatrix(index: Map<string, number>, edges: readonly Edge[]): number[][] {
const size = index.size;
const matrix = Array.from({ length: size }, () => new Array<number>(size).fill(0));
for (const [u, v] of edges) {
matrix[index.get(u)!][index.get(v)!] = 1;
matrix[index.get(v)!][index.get(u)!] = 1;
}
return matrix;
}
const vertices = ["A", "B", "C", "D", "E"];
const edges: Edge[] = [["A", "B"], ["A", "C"], ["B", "C"], ["B", "D"], ["C", "E"], ["D", "E"]];
const neighbours = buildAdjacencyList(vertices, edges);
console.log("adjacency list:");
for (const vertex of vertices) {
console.log(`${vertex}: ${neighbours.get(vertex)!.join(", ")}`);
}
const index = new Map(vertices.map((vertex, i) => [vertex, i] as const));
const matrix = buildAdjacencyMatrix(index, edges);
console.log("adjacency matrix:");
console.log(` ${vertices.join(" ")}`);
for (const vertex of vertices) {
console.log(`${vertex} ${matrix[index.get(vertex)!].join(" ")}`);
}
console.log(`edge B-D: ${matrix[index.get("B")!][index.get("D")!] === 1}`);
console.log(`edge A-E: ${matrix[index.get("A")!][index.get("E")!] === 1}`);
console.log(`neighbours of B: ${neighbours.get("B")!.join(", ")}`);adjacency list:
A: B, C
B: A, C, D
C: A, B, E
D: B, E
E: C, D
adjacency matrix:
A B C D E
A 0 1 1 0 0
B 1 0 1 1 0
C 1 1 0 0 1
D 0 1 0 0 1
E 0 0 1 1 0
edge B-D: true
edge A-E: false
neighbours of B: A, C, DThe highlighted lines come in pairs because every undirected edge is written twice, once from each end, in the list and in the matrix alike. Dropping the second line of either pair stores each edge in one direction only, which is how a directed graph is stored.
Java uses a LinkedHashMap so the vertices print in the order they were added; a HashMap would print them in an order set by their hash codes. Python's dictionary and TypeScript's Map keep insertion order on their own.
The matrix sizes itself from the number of vertices when it is created, so a vertex added later needs a new, larger grid, while the adjacency list takes a new vertex with one more map entry. Both versions build in one pass over the edges: O(V + E) for the list, and O(V²) for the matrix, because creating the grid fills every cell with 0 before the first edge is read.
← → move through sections and cards