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.

graph1

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

Advertisements

3 thoughts on “Adjacency list representation of a graph (Python, Java)

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

  2. 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 ?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s