Adjacency list representation of a graph (Python, Java)

1. Adjacency list representation – Example

Here, I will talk about the adjacency list representation of a graph. Take for example the graph below.

For each vertex v we will store a list that contains the neighbors of v:

0: [1, 2]
1: [2, 3]
2: [4]
3: [4, 5]
4: [5]
5: []

Here, 0: [1,2] means vertex 0 has the neighbors 1,2. Similarly, 5:[] means vertex 5 has no neighbors.

2. Python implementation

2a. Python implementation using a list of lists

Let’s implement this in Python:

# list of lists
adjLists = [ [1,2], [2,3], [4], [4,5], [5], [] ]

# testing
print("Neighbors of vertex 0: ", adjLists[0])
print("Neighbors of vertex 3: ", adjLists[3])

print("\nPrint all adjacency lists with corresponding vertex")
for v in range(0,n):

The output of that program is:

Neighbors of vertex 0:  [1, 2]
Neighbors of vertex 3:  [4, 5]

Print all adjacency lists with corresponding vertex
0 : [1, 2]
1 : [2, 3]
2 : [4]
3 : [4, 5]
4 : [5]
5 : []

2b. Python implementation using a dictionary

Alternatively, we can also use a dictionary which contains the pair (key, record) = (node, adjList). This is in particular useful if the nodes are not integers but for example strings.

# empty dictionary

# insert (vertex, list) pairs into dictionary

# testing
print("Neighbors of vertex 0: ", adjLists_dict[0])
print("Neighbors of vertex 3: ", adjLists_dict[3])

print("\nPrint all adjacency lists with corresponding vertex")
for v in range(0,n):

The output is the same as with the previous program:

Neighbors of vertex 0:  [1, 2]
Neighbors of vertex 3:  [4, 5]

Print all adjacency lists with corresponding vertex
0 : [1, 2]
1 : [2, 3]
2 : [4]
3 : [4, 5]
4 : [5]
5 : []

3. Java implementation

3a. Java implementation using an ArrayList of ArrayLists

import java.util.*;

public static void main(String[] args) {

// empty ArrayList
// insert n=6 ArrayLists
int n = 6;
for(int i=0; i<n; i++){
}

// insert neighbors into list for vertex 0

// insert neighbors into list for vertex 1

// insert neighbors into list for vertex 2

// insert neighbors into list for vertex 3

// insert neighbors into list for vertex 4

// insert neighbors into list for vertex 5
// -> nothing to do since 5 has no neighbors

// testing
System.out.println("Neigbors of vertex 0: " + adjLists.get(0));
System.out.println("Neigbors of vertex 5: " + adjLists.get(5));

System.out.println("\nPrint all adjacency lists with corresponding vertex:");
for(int v=0; v<n; v++){
System.out.println(v + ": " + adjLists.get(v));
}
}

}

The output of that program is:

Neigbors of vertex 0: [1, 2]
Neigbors of vertex 5: []

Print all adjacency lists with corresponding vertex:
0: [1, 2]
1: [2, 3]
2: [4]
3: [4, 5]
4: [5]
5: []

3b. Java implementation using a dictionary (HashMap)

Here is the Java code for using a dictionary (HashMap):

import java.util.*;

public static void main(String[] args) {
// empty dictionary
HashMap<Integer, ArrayList<Integer>> adjLists_dict = new HashMap<Integer, ArrayList<Integer>>();

// insert empty lists for each node
int n = 6;
for(int v=0; v<n; v++){
}

// insert (vertex, list) pairs into dictionary
// insert neighbors into list for vertex 0

// insert neighbors into list for vertex 1

// insert neighbors into list for vertex 2

// insert neighbors into list for vertex 3

// insert neighbors into list for vertex 4

// insert neighbors into list for vertex 5
// -> nothing to do since 5 has no neighbors

// testing
System.out.println("Neighbors of vertex 0: " + adjLists_dict.get(0));
System.out.println("Neighbors of vertex 3: " + adjLists_dict.get(3));

System.out.println("\nPrint all adjacency lists with corresponding vertex:");
for(int v=0; v<n; v++){
System.out.println(v + ": " + adjLists_dict.get(v));
}

}

}

The output is:

Neighbors of vertex 0: [1, 2]
Neighbors of vertex 3: [4, 5]

Print all adjacency lists with corresponding vertex:
0: [1, 2]
1: [2, 3]
2: [4]
3: [4, 5]
4: [5]
5: []

The code in Python looks very clean and simple. The Java code isn’t as short as the Python one (mainly because there is no inherent Java notation for the creation of lists such as [2,3].

Note: In 3a it is important to insert the empty lists into the ArrayList. In 3b you must not forget to insert the empty lists into the dictionary (HashMap).

4. References

1. Adjacency List representation in C++ using the stl vector (youtube video)

2. Adjacency list representation using a HashMap (TopCoder)

3. Adjacency list representation using a HashMap (Stackoverflow)

4. Another article on stackoverflow using a Map for the adjacency list representation