Some Useful Links:
[Android Tutorial #1] Introduction
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.
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); } }
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.
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(); }
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.
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.
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.
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).
In our previous post, we stored the graph in Edges List and Vertices List. And we saw that time complexity of performing operations in this representation is very high. So, we need another representation which can perform operations in less time.
Another representation of the graph is a 2D array of size V x V called Adjacency Matrix. Let’s call that matrix adjacencyMatrix. If we have an edge between nodes s and d, then adjacencyMatrix[s][d] is set to 1 or weight, else set to infinity.
Consider the following graph
The adjacency matrix of above graph is
There is an edge between 1 and 2, so we put 1 in adjacencyMatrix[1][2] and also in adjacencyMatrix[2][1] as this is an undirected graph. We give value 1 here because there is no weight for an edge. There is no edge between 1 and 3, so we put infinity in adjacencyMatrix[1][3].
In Java, we initialize a 2D array adjacencyMatrix[size+1][size+1], where size is the total number of vertices in the graph. For the above graph, the matrix will have a size of 7. We assign Integer.MIN_VALUE which is equivalent to negative infinity to adjacencyMatrix.
(Note: We can assign an index from 0 to 6 to all the vertices, but that creates confusion. Here, we use node names as the array index in this implementation. Since there is no node 0, and node start from 1, we increase the matrix size by 1. If you have string nodes, you can give them indices from zero and use size instead of size+1.)
public class GraphAdjacencyMatrix{ //2-D array to store adjacency matrix private int[][] adjacencyMatrix; //variable to store size of 2-D array/adjacency matrix private int size; //Constructor to initialize the matrix and size public GraphAdjacencyMatrix(int size){ this.size = size; adjacencyMatrix = new int[size][size]; for(int[] single : adjacencyMatrix) Arrays.fill(single, Integer.MIN_VALUE); } }
Now we add edges between two nodes using the following method. Since the graph in fig 1 is undirected, we add an edge from source to destination and destination to source by assigning one to adjacencyMatrix[destination] and adjacencyMatrix[destination].
public void add(int source, int destination){ adjacencyMatrix[destination] = 1; adjacencyMatrix[destination] = 1; }
The findAdjacent method takes an index as input and returns anArrayList of vertices adjacent to the index. To find all adjacent vertices of the index, we need to traverseadjacencyMatrix[vertex] and add those vertices to list whose value is 1.
Since we traverse adjacencyMatrix[vertex] linearly, whose size is V (V being the number of vertices in the graph), the time complexity of this operation is O(V).
public ArrayList<Integer> findAdjacent(int index){ ArrayList<Integer> adjacent = new ArrayList<Integer>(); for(int i=1;i<size;i++){ if(adjacencyMatrix[index][i] == 1) adjacent.add(i); } return adjacent; }
To find whether source and destination are connected, we just check whether adjacencyMatrix[destination] or adjacencyMatrix[destination] is equal to 1. If any of them is equal to 1, source and destination are connected else they are not connected. The time complexity of this operation is O(1) as we only access a position in a 2D matrix.
public boolean isConnected(int source, int destination){ if(adjacencyMatrix[destination] == 1 || adjacencyMatrix[destination] == 1) return true; return false; }
The entire code for a unweighted undirected graph is available here.
If an edge between source and destination has a weight then we assign value of weight to adjacencyMatrix[destination] and adjacencyMatrix[destination].
public void add(int source, int destination, int weight){ adjacencyMatrix[destination] = weight; adjacencyMatrix[destination] = weight; }
To find adjacent nodes of a given node, we add all those nodes to the list whose value is not equal to Integer.MIN_VALUE.
public ArrayList<Integer> findAdjacent(int index){ ArrayList<Integer> adjacent = new ArrayList<Integer>(); for(int i=1;i<size;i++){ if(adjacencyMatrix[index][i] != Integer.MIN_VALUE) adjacent.add(i); } return adjacent; }
Similarly to check whether two nodes are connected or not, we check whether adjacencyMatrix[destination] or adjacencyMatrix[destination] is not equal to Integer.MIN_VALUE.
public boolean isConnected(int source, int destination){ if(adjacencyMatrix[destination] != Integer.MIN_VALUE || adjacencyMatrix[destination] != Integer.MIN_VALUE) return true; return false; }
The whole code for the weighted undirected graph can be found here.
In case of directed weighted graph, we assign weight to only adjacencyMatrix[destination] and not to adjacencyMatrix[destination]. Other operations are same as those for the above graphs. The whole code for directed weighted graph is available here.
If we have a graph with million nodes, then the space this graph takes is square of million, as adjacency matrix is a 2D array. That’s a lot of space. It is good when we have a large number of vertices and equally large number of edges between them, as then we will have a dense matrix. But If we have a graph with a lot of vertices and very few edges, resulting in a sparse matrix, we store a lot of infinite values which are unnecessary and take a lot of space. The next implementation Adjacency List, which we cover in next post improves upon this.
A large number of vertices and equally large number of edges between them will produce a dense matrix. Here, using adjacency matrix is efficient. But a large number of vertices and very few edges between them will produce a sparse matrix. Here, using adjacency matrix is inefficient as we store a lot of infinite values (taking up large space) which are unnecessary. The next implementation Adjacency List, which we cover in next post improves upon this.