In the last post, we used a 2D matrix to represent the graph. But found it inefficient when our graph consists of a huge number of vertices.

Another way to represent graph is using adjacency list. Here we store the adjacent vertices of a given vertex as a list.

Unweighted Undirected Graph

 

 

 

In the case of the adjacency matrix, we store 1 when there is an edge between two vertices else we store infinity. If you notice, we are storing those infinity values unnecessarily, as they have no use for us. So what we can do is just store the edges from a given vertex as an array or list. To store all the vertices and their adjacent lists we can either use a hashmap or an array or a list or a set.

A better option is to store the 1’s and skip the 0’s, which will reduce the space. We can do that by storing the adjacent nodes in a list/array of the given node.

We can either use a hashmap or an array or a list or a set to implement graph using adjacency list.

Consider the undirected unweighted graph in figure 1. For the vertex 1, we only store 2, 4, 5 in our adjacency list, and skip 1,3,6 (no edges to them from 1). Similarly, for vertex 2, we store 1,3,5,6 and skip 2,4. And do the same for the remaining vertices.

For our example, we will use a hashmap with vertices id(1, 2, 3, etc) as keys and an object node storing the vertex id and its adjacency list. The adjacency list is implemented using ArrayList.

 

private static HashMap<Integer,Node> graph = new HashMap<Integer,Node>();

 

The class Node is like this:

 

        /**
	* Node --- class to store each vertex along with its adjacent vertices
	*/
	static class Node{		
		
		private int id;
		private ArrayList<Node> adjacent;
		
		public Node(int id){
			this.id = id;
			adjacent = new ArrayList<Node>();
		}
		
		//Getter method for start vertex
		public int getId(){
			return id;
		}
		
		//Getter method for end vertex
		public ArrayList<Node> getAdjacent(){
			return adjacent;
		}
		
		//add node to the adajcent list
		public void addAdjacent(Node vertex){
			adjacent.add(vertex);
		}

	}

 

 

Add an edge

In an undirected graph if we have an edge from a to b then we also have an edge b to a. Hence for an edge {a, b} we add b to the adjacency list of a, and a to the adjacency list of b.

Note, we have an integer value for our source and destination as input but our adjacency list is of type Node. Therefore, first, we access the node corresponding to that integer using getNode() function and then add destination node to the adjacency list by calling the Node’s addAdjacent() method.

 

        public void add(int source, int destination){

		//Get nodes corresponding to source and destination vertices.
		Node s = getNode(source);
		Node d = getNode(destination);

		//add nodes to adjacent list
		s.addAdjacent(d);
		d.addAdjacent(s);
	}

 

The getNode() method first checks whether that integer is present in our graph’s keys. If it is present it returns the node object associated with that key inside the graph. But if it isn’t present, then it creates a new node using the integer and adds it to the graph with the integer as key. Every time, a new vertex comes, it’s id is first added to the graph along with its node and then we add the adjacent vertices to the node’s adjacent list.

 

private static Node getNode(int id){
		if(graph.containsKey(id))
		    return graph.get(id);
                else{
        	    Node node = new Node(id);
        	    graph.put(id, node);
        	    return node;
                }
}

 

Consider an example: Our graph is currently empty. We call the method add(1, 2). First, we create Node s, by calling the getNode(1) method. The getNode(1) method checks whether 1 is present in our graph(hashmap). Since it is not present, it creates a new node with id 1 and puts the pair (1, Node(1)) inside the hashmap and returns Node(1). A similar process is followed by 2 to get Node d. Now we have both our nodes s and d as Node(1) and Node(2). We add Node(2) to the adjacent list of Node(1) and vice versa.

 

Find Adjacent Vertices

 

Finding adjacent vertices inside a graph using HashMap is easy. First, we get the node corresponding to the given index using the getNode method and then return that node’s adjacent list. The whole operation takes O(1) time, as accessing an object using the key in HashMap is constant time operation.

For example: When we call findAdjacent(1). We will get an output of [2 4 5] as an ArrayList of type nodes.

 

public ArrayList<Node> findAdjacent(int index){
		Node node = getNode(index);
		return node.getAdjacent();
}

 

Find whether two nodes are connected

 

To find whether two nodes source and destination are connected or not, we just need to check whether source’s adjacent list contains destination or destination’s adjacent list contains source. If either of the conditions is true, source and destination are connected.

The time complexity of this operation is O(k), k being the number of adjacent vertices of a given vertex. The time complexity of accessing a node in HashMap is O(1) but the complexity of searching an object in ArrayList is O(n) (where n is the size of the ArrayList. In the worst case, a vertex is connected to all vertices in the graph, then the complexity of this operation becomes O(V).

For example: When we call isConnected(1,2), first we get the Nodes(1) and Node(2) using the getNode() method. Node(1) contains its adjacent as [2, 4, 5] and Node(2) contains its adjacent as [1, 3, 5, 6]. We check whether 2 is present in Node(1)’s adjacent. We see that it is present and return true.

 

public boolean isConnected(int source, int destination){
		Node s = getNode(source);
		Node d = getNode(destination);

		if(s.getAdjacent().contains(d) || d.getAdjacent().contains(s))
			return true;
		return false;
	}

 

The entire code for a unweighted undirected graph is available here.

 

Weighted Undirected Graph

 

The edges have a weight in the above graph. We notice it is a bit difficult to store weight of an edge as an instance of Node’s object in the present implementation of the node. Node object just stores all the adjacent nodes and no weights. What we can do is create another class Edge which stores the endVertex along with the weight and then add that Edge object to the adjacent list of the Node.

 

        /**
	* Edge --- class to store an edge between End vertex and weight of the edge
	*/
	static class Edge{		
		
		private int endVertex;
		private int weight;
		
		public Edge(int endVertex, int weight){
			this.endVertex = endVertex;
			this.weight = weight;
		}
		
		//Getter method for start vertex
		public int getEndVertex(){
			return endVertex;
		}
		
		//Getter method for end vertex
		public int getWeight(){
			return weight;
		}
		
	}

 

The Node class becomes:

 

        /**
	* Node --- class to store each vertex along with adjacent vertices and weight of the edges.
	*/
	static class Node{		
		
		private int id;
		private ArrayList<Edge> adjacent;
		
		public Node(int id){
			this.id = id;
			adjacent = new ArrayList<Edge>();
		}
		
		//Getter method for start vertex
		public int getId(){
			return id;
		}
		
		//Getter method for end vertex
		public ArrayList<Edge> getAdjacent(){
			return adjacent;
		}
		
		//add node to the adajcent list
		public void addAdjacent(int endVertex, int weight){
			adjacent.add(new Edge(endVertex,weight));
		}
        }

 

The implementation of the graph using the HashMap remains same. There is a little difference while adding the edge between source and destination now. As now we add the weight also. You can see the addAdjacent method of Node class. It now takes an extra parameter weight. And we create an edge object using the endVertex and weight and then add that object to our adjacent list.

The adjacent list of Node(1) is [ (2, 5), (4, 6), (5, 10)]. Here 2, 4, 5 are the adjacent vertices and 5, 6, 10 are the weights of edges to those vertices.

 

public void add(int source, int destination, int weight){

		//Get nodes corresponding to source and destination vertices.
		Node s = getNode(source);
		Node d = getNode(destination);

		//add nodes to adjacent list
		s.addAdjacent(destination,weight);
		d.addAdjacent(source,weight);
	}

 

The logic for finding all the adjacent vertices is still the same and can be done in O(1) time. Let’s have a look on the logic of finding whether two nodes are connected or not.

 

public boolean isConnected(int source, int destination){
		Node s = getNode(source);
		Node d = getNode(destination);

		ArrayList<Edge> sourceList = s.getAdjacent();
		for(Edge edge: sourceList){
			if(edge.endVertex == destination)
				return true;
		}
		return false;
	}

 

Suppose we need to find whether source and destination are connected or not. Next, we access the nodes corresponding to source and destination. Then we traverse the adjacent list of edges of source node linearly and check which edge has endVertex same as the destination. If there is a match, return true, else return false.

The entire code for the weighted undirected graph is available here.

 

Weighted Directed Graph

 

Implementation for a weighted directed graph is same as that of the weighted undirected graph. The only difference is in the way we create the adjacent list for each node. Now we just add a destination to the source’s adjacent list. We do not add the source to destination’s adjacent list.

 

public void add(int source, int destination, int weight){

		//Get nodes corresponding to source and destination vertices.
		Node s = getNode(source);

		//add nodes to adjacent list
		s.addAdjacent(destination,weight);
	}

 

The whole code for directed weighted graph is available here.

Conclusion

The space complexity of using adjacency list is O(E), improves upon O(V*V) of the adjacency matrix. (E is the total number of edges, V is the total number of vertices). We store adjacent nodes of all nodes equivalent to storing all the edges. Hence the complexity is O(E).