**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") n = len(adjLists) for v in range(0,n): print(v, ":", adjLists[v])

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 adjLists_dict = {} # insert (vertex, list) pairs into dictionary adjLists_dict[0] = [1,2] adjLists_dict[1] = [2,3] adjLists_dict[2] = [4] adjLists_dict[3] = [4,5] adjLists_dict[4] = [5] adjLists_dict[5] = [] # 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") n = len(adjLists_dict) for v in range(0,n): print(v, ":", adjLists_dict[v])

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 class AdjacencyList { public static void main(String[] args) { // empty ArrayList ArrayList<ArrayList<Integer>> adjLists = new ArrayList<ArrayList<Integer>>(); // insert n=6 ArrayLists int n = 6; for(int i=0; i<n; i++){ adjLists.add(new ArrayList<Integer>()); } // insert neighbors into list for vertex 0 adjLists.get(0).add(1); adjLists.get(0).add(2); // insert neighbors into list for vertex 1 adjLists.get(1).add(2); adjLists.get(1).add(3); // insert neighbors into list for vertex 2 adjLists.get(2).add(4); // insert neighbors into list for vertex 3 adjLists.get(3).add(4); adjLists.get(3).add(5); // insert neighbors into list for vertex 4 adjLists.get(4).add(5); // 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 class AdjacencyList_Dict { 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++){ adjLists_dict.put(v, new ArrayList<Integer>()); } // insert (vertex, list) pairs into dictionary // insert neighbors into list for vertex 0 adjLists_dict.get(0).add(1); adjLists_dict.get(0).add(2); // insert neighbors into list for vertex 1 adjLists_dict.get(1).add(2); adjLists_dict.get(1).add(3); // insert neighbors into list for vertex 2 adjLists_dict.get(2).add(4); // insert neighbors into list for vertex 3 adjLists_dict.get(3).add(4); adjLists_dict.get(3).add(5); // insert neighbors into list for vertex 4 adjLists_dict.get(4).add(5); // 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

Pingback: Depth First Search – Java and Python implementation | Programming, algorithms and data structures

Can we make the array implementation of java code read the input from a text file, Where the first line has the number of vertices and edges and each edge is given in a new line ?

simple code

Thanks