From starting June to end of August, I completed nine challenges of varying complexity as part of Google foobar. This is the decoded message I received at the end of the final challenge.
I was going through graph algorithms for a personal project. As usual, I was searching for their code online. It was during one of those searches, I got an invitation in my browser for this challenge.
And I accepted.
The Challenges
There were five levels. With each level, the complexity of challenges increased. The distribution of challenges was like this for me-
Level 1: 1 Challange
Level 2: 2 Challenges
Leve 3: 3 Challenges
Level 4: 2 Challenges
Leve 5: 1 Challange
Major Concepts
These challenges were a learning roller coaster for me with lots of bumps and falls. There were many sleepless nights, late lunches and dinners, too many cups of tea and coffee involved to finish each challenge.
Each question gave me a better understanding of a new concept. Here are few of them –
Graph Search Algorithms
Dynamic programming
Graph Theory and Mathematics concepts
Matrix and its operations implementation
Debugging
Time and Space complexity.
Conclusion
The day I received these running bunnies, I felt both relief and proud. Relief because I finally completed the last and toughest challenge. And proud because I was successful in saving the bunnies. Apart from solving all these challenges, I was publishing video tutorials on this blog and written posts on my other blog.
In the previous post, we discussed Depth First Search and its implementation in Java. In this post, we learn how to use Breadth First Search to find whether there exists a path between two vertices in a graph.
Again for this post also, we will create a graph for a directed unweighted graph as an adjacency list using the concepts discussed in this previous post. Then apply BFS on it.
How does Breadth First Search (BFS) work?
We have source node and a destination node in a graph. Our motive is to find a path between them. So we call BFS on our source and destination. In DFS, we traverse from node to its child, then to its grandchild and so on. In BFS we go level by level. First, we go through the first node(first layer), then it’s children (second layer) followed by its grandchildren(third layer) and so on until we reach the destination or we have traversed every node.
Here we first add the first node to a queue. Then check whether the first node in our queue is the destination. If yes, it returns true. Else remove the node from the queue. If the node is not in the visited set, add them to the visited set. Then we add the node’s children to our queue. Repeat the above process for every node in queue. If after traversing all nodes we don’t get a path, we return false.
Fig 1: Directed Graph
Fig 2: Adjacency List of Graph in Fig 1.
Consider the graph in Fig 4. We have to find whether a path exists between A and H.
First, we check if start is destination ie A is a destination. It is not. So we move on to A’s children B and F and check them sequentially whether they are the destination (Orange Color). They are not, so we traverse B’s children followed by F’s children i.e., C, F (Green Color), and G(Yellow Color). Next we traverse C’s, F’s and G’s children. We continue in this way till we reach our destination node H.
Fig. 3: BFS on the graph in FIg 1. Each color representing a level. Blue representing the source and destination node.
Implementation
Now we code the above concept in Java. I will break down the code into few simple steps for ease in understanding
Step 1: Create a Node class, which stores the Node’s id of primitive type along with a LinkedList/ArrayList to store adjacency list of that node.
Step 2: Create a HashMap/ArrayList to store the vertices of a graph as Node objects. Here we can create a global variable to store graph or locally in methods and then pass them as parameters. Till now, we created a global variable for the graph, for the next two videos we will create a graph in a method and pass it as parameters.
Step 3: Add all the edges into the graph by updating the adjacency list of source nodes.
Step 4: Write method to find whether a path exists between source and destination using BFS.
Now we go through each step in detail:
Step 1:
Create a Node class, which stores the Node id/name/label of primitive type along with a LinkedList/ArrayList to store adjacency list of that node. For a detailed explanation refer to this post.
/**
* Node --- class to store each vertex along with its adjacent vertices
*/
static class Node{
private String id;
private LinkedList<Node> adjacent;
public Node(String id){
this.id = id;
adjacent = new LinkedList<Node>();
}
//Getter method for start vertex
public String getId(){
return id;
}
//Getter method for end vertex
public LinkedList<Node> getAdjacent(){
return adjacent;
}
//add node to the adajcent list
public void addAdjacent(Node vertex){
adjacent.add(vertex);
}
//To print Node
public String toString(){
String msg = id + " : ";
for(Node node: adjacent)
msg = msg + node.id + " ";
return msg;
}
}
Step 2:
Create a HashMap/ArrayList to store the vertices of a graph as Node objects.
In our example graph in Fig 1, we have string nodes. So our HashMap will have keys of type String and Values of type Node.
/**
* Creates a HashMap with string key and Node value
* @param input list of edges
* @return HashMap<String,Node>
*/
public static HashMap<String, Node> createGraph(String[] input){
HashMap<String, Node> graph = new HashMap<String, Node>();
Node node;
for(String s: input){
String first = String.valueOf(s.charAt(0));
String second = String.valueOf(s.charAt(1));
add(graph, first, second);
}
return graph;
}
Step 3:
Add all the edges into the graph by updating the adjacency list of source nodes.
Our input is an array of strings where each string “XY” represents an edge from X to Y. So we traverse our list and do the following three steps on each of the string values.
//Input edges of the graph.
{"AB","AE","BC","BF","CG","CD","EF","FG","GH","DH"};
Part 1: First we separate X and Y from our string “XY”. We can do that by using the String’s charAt(index) method and assign them to a first and second variable. Then add the edge to our graph by calling the add method.
public static void add(HashMap<String, Node> graph, String source, String destination){
//Get nodes corresponding to source and destination vertices.
Node s = getNode(graph, source);
Node d = getNode(graph, destination);
//add nodes to adjacent list
s.addAdjacent(d);
}
Part 2: We access the node corresponding to string X and Y in the graph. If there is no such node in our graph then we create one. This method getNode() does exactly that. It checks whether string K is present in our graph, if yes, then returns the corresponding node, else creates a new node with id K and adds it to our graph with key K.
Part 3: Once we have both the nodes, we can add the destination node to source node’s adjacent list. Now our graph is created.
Step 4:
Write method to find whether a path exists between source and destination.
Here we need to traverse nodes in the order they come in. So we use a LinkedListqueue of type Nodes. We add them as they come and always remove the first one in the list. To keep track of visited nodes, so that we don’t go inside an infinite loop, we use a HashSetvisited.
We start by adding the first node to the queue. Then we loop over this queue until the queue becomes empty. Inside the loop, we remove the first node in the list. Then check whether the node is same as the destination. If yes, we return true. If no, we add the node to visited set if it has not been added. Next, we loop through the node’s adjacent list to add all its children to the queue. If we didn’t find destination even after traversing all nodes, we return false.
public static boolean pathExists(HashMap<String, Node> graph, String source, String destination){
//To store the children of nodes visited
LinkedList<Node> queue = new LinkedList<Node>();
//To store the visited nodes
HashSet<String> visited = new HashSet<String>();
//adding node of startId in the linkedlist
queue.add(getNode(graph, source));
while(!queue.isEmpty()){
Node parent = queue.remove();
//Check if current node is the destination node
if(parent.getId().equals(destination))
return true;
//add source to visited set
if(visited.contains(parent.getId()))
continue;
visited.add(parent.getId());
//add children to the queue
for(Node children: parent.getAdjacent())
queue.add(children);
}
return false;
}
Example
Consider the graph in Fig 1. We will apply the above BFS method on
Graph search or finding whether one vertex is reachable from another vertex in a graph is one of the operations we can apply on graphs. There are two basic methods for this:
Depth First Search
Breadth First Search
In this post, we will study Depth First Search. We will create a graph for a directed unweighted graph as an adjacency list using the concepts discussed in this previous post. Then apply DFS on it.
What does reachability mean?
One vertex is reachable from another vertex if and only if there exists a path between them. For example in the directed graph given below, there exists a pathbetween 1 and 6 but not between 3 and 4.
Fig 1: Directed Graph
We can either go directly from node 1 to node 6 or go from node 1 to node 5 and then to node 6. The blue color highlights the path. And the gray color highlights the lack of path between 3 and 4 in the above graph.
How does Depth First Search (DFS) work?
We have source node and a destination node in a graph. Our motive is to find a path between them. So we call DFS on our source and destination. DFS then checks whether there is a path from any of the node’s children to the destination. If there is a path it returns true. Else it continues on the current node’s children until either we reach the destination (return true) or we reach a node already traversed ( return false).
The following example will clarify this more.
Fig 2: Path does not exist
Fig 2 shows a directed unweighted graph along with adjacencylist of each node. Suppose we want to find whether a path exists between 3 and 4. As per DFS, we check whether a path exists between 3’s child i.e. 6 and 4. Which further checks whether a path exists between 6’s child i.e. 2 and 4. This then checks whether a path exists between 2’s child i.e. 3 and 4. 3 is our node already traversed and so we return false. Let’s look at an example where a path exists.
Fig 3: Path exists
Suppose we want to find whether a path exists between 1 and 6. Again, we start with 1’s child i.e 2 and call our method pathExists on 2 and 6. Then again we call method pathExists method on 2’s child i.e. 3and 6 and then finally on 6 and 6 which returns true. This True goes all the way back to our first call and we return the final result ie True.
Implementation
Now we code the above concept in Java. I will break down the code into few simple steps for ease in understanding
Step 1: Create a Node class, which stores the Node’s id of primitive type along with a LinkedList/ArrayList to store adjacency list of that node.
Step 2: Create a hashmap/ArrayList to store the vertices of a graph as Node objects. Here we can create a global variable to store graph or locally in methods and then pass them as parameters. Till now, we created a global variable for the graph, for the next two videos we will create a graph in a method and pass it as parameters.
Step 3: Add all the edges into the graph by updating the adjacency list of source nodes.
Step 4: Write method to find whether a path exists between source and destination using DFS.
Now we go through each step in detail:
Step 1:
Create a Node class, which stores the Node id/name/label of primitive type along with a LinkedList/ArrayList to store adjacency list of that node. For a detailed explanation refer to this post.
/**
* Node --- class to store each vertex along with its adjacent vertices
*/
static class Node{
private String id;
private LinkedList<Node> adjacent;
public Node(String id){
this.id = id;
adjacent = new LinkedList<Node>();
}
//Getter method for start vertex
public String getId(){
return id;
}
//Getter method for end vertex
public LinkedList<Node> getAdjacent(){
return adjacent;
}
//add node to the adajcent list
public void addAdjacent(Node vertex){
adjacent.add(vertex);
}
//To print Node
public String toString(){
String msg = id + " : ";
for(Node node: adjacent)
msg = msg + node.id + " ";
return msg;
}
}
Fig 4: Directed Graph
Step 2:
Create a HashMap/ArrayList to store the vertices of a graph as Node objects.
In our example graph in Fig 4, we have string nodes. So our HashMap will have keys of type String and Values of type Node.
/**
* Creates a HashMap with string key and Node value
* @param input list of edges
* @return HashMap<String,Node>
*/
public static HashMap<String, Node> createGraph(String[] input){
HashMap<String, Node> graph = new HashMap<String, Node>();
Node node;
for(String s: input){
String first = String.valueOf(s.charAt(0));
String second = String.valueOf(s.charAt(1));
add(graph, first, second);
}
return graph;
}
Step 3:
Add all the edges into the graph by updating the adjacency list of source nodes.
Our input is an array of strings where each string “XY” represents an edge from X to Y. So we traverse our list and do the following three steps on each of the string values.
//Input edges of the graph.
String[] input = {"AB","BC","BE","CF","DE","EF"};
Part 1: First we separate X and Y from our string “XY”. We can do that by using the String’s charAt(index) method and assign them to a first and second variable. Then add the edge to our graph by calling the add method.
public static void add(HashMap<String, Node> graph, String source, String destination){
//Get nodes corresponding to source and destination vertices.
Node s = getNode(graph, source);
Node d = getNode(graph, destination);
//add nodes to adjacent list
s.addAdjacent(d);
}
Part 2: We access the node corresponding to string X and Y in the graph. If there is no such node in our graph then we create one. This method getNode() does exactly that. It checks whether string K is present in our graph, if yes, then returns the corresponding node, else creates a new node with id K and adds it to our graph with key K.
Part 3: Once we have both the nodes, we can add the destination node to source node’s adjacent list. Now our graph is created.
Step 4:
Write method to find whether a path exists between source and destination.
We know that path exists between source and destination when the source becomes equal to the destination while traversing the graph. And we also know that if we encounter a node already visited while searching the destination then we don’t have a path between source and destination. So we need to keeptrack of the nodes visited so far. We do that using a HashSet visited.
We create an empty HashSet in our helper method and pass it and the source and the destination node to our main recursive method. We can get the nodes from the hashmap using getNode() method described above.
Once we are on a node, we check whether that node exists in our visited set. If it exists, we return false (no path between source and destination). If it doesn’t exist in visited, we add the node to the visited set.
Then we check whether the current node is equal to our destination. If yes, we have found a path, so we return true. Else we traverse the adjacent list of the current node and check if a path exists between its children and the destination node. If a path does exist we return true, else we return false.
/**
* Helper method for pathExists recursive method
* @param HashMap<String, Node> graph
* @param source start index
* @param destinations end index
* @return true or false
*/
public static boolean pathExists(HashMap<String, Node> graph, String source, String destination){
HashSet<Node> visited = new HashSet<Node>();
return pathExists(getNode(graph, source), getNode(graph, destination), visited);
}
/**
* pathExists recursive method to find path between source and destination
* @param source start index
* @param destinations end index
* @param visited set to store visited nodes
* @return true or false
*/
public static boolean pathExists(Node source, Node destination, HashSet<Node> visited){
if(visited.contains(source))
return false;
visited.add(source);
if(source == destination)
return true;
for(Node neighbor : source.getAdjacent()){
if(pathExists(neighbor, destination, visited))
return true;
}
return false;
}
Example
We see recursive calls on two examples for the graph in Fig 4.
pathExists(graph, “A”, “F”)
pathExists(graph, “A”, “D”)
The adjacency list of all nodes in the graph of Fig 4 is:
Fig 5: Adjacency list of each node in the graph of Fig 4.
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
Fig 1: Unweighted Undirected Graph
Fig 2: Adjacency List
Fig 3: Adjacency Matrix
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 typeNode. 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.
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’sadjacentlist. 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.
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
Fig 4: 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
Fig 5: 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).
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.
Unweighted Undirected Graph
Consider the following graph
Fig 1: Undirected Graph
The adjacency matrix of above graph is
Fig 2: Adjacency Matrix of the graph in Fig 1.
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);
}
}
Add an edge
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;
}
Find Adjacent Vertices
The findAdjacent method takes an index as input and returns anArrayList of verticesadjacent 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;
}
Find whether two nodes are connected
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.
Weighted Undirected Graph
Fig 3: Weighted Undirected Graph
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.
Weighted Directed Graph
Fig 4:Weighted Directed Graph
In case of directed weighted graph, we assign weight to onlyadjacencyMatrix[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.
Problems in this approach
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.
In the previous post, we explained what are graphs and how the graph is represented mathematically. In this post, we see how to represent that Graph in computer’s memory (means which data structures to use to implement graphs).
Graphs can be represented in three ways:
Edges and Vertices List.
Adjacency Matrix
Adjacency List
In this post, we start with the first method Edges and Vertices list to represent a graph.
Edges and Vertices List
Here a graph is represented as a vertices list and edges list. The list here means we can use an Array or an ArrayList in Java to store the vertices and edges separately.
Fig 1: Undirected Graph
Consider above graph, the vertices can be stored in a vertices array and the edges can be stored in a separate array.
Fig 2 – Edges and Vertices List of graph in fig 1
Vertices are stored using an array of integers directly. But an edge {u,v} has two values which can’t be stored directly in an array. Therefore we create a class Edge with two instance variables to store the name of the two vertices. Here {1,2,3,4,5,6} are names of our vertices. We could use strings also instead of integers for the names of vertices.
/**
* Edge --- class to store an edge between Start vertex and End vertex
*/
class Edge{
private int startVertex;
private int endVertex;
public Edge(int startVertex, int endVertex){
this.startVertex = startVertex;
this.endVertex = endVertex;
}
//Getter method for start vertex
public int getStartVertex(){
return startVertex;
}
//Getter method for end vertex
public int getEndVertex(){
return endVertex;
}
}
We know that the graph is undirected, so if an edge {u.v} exists, then edge {v,u} exists. But to store edge {v,u} is futile as that will take only extra space. We assume that if we add an edge {u, v} we are also accounting for the edge {v, u}.
Instead of arrays, we are using ArrayList in our implementation as it is more dynamic. So there are two ArrayLists, one of Integer type to store vertices and another of Edge type to store edges.
//List verticesList to store vertices
private static ArrayList<Integer> verticesList;
//List edgesList to store edges
private static ArrayList<Edge> edgesList;
Add an edge
Next, we see how to add an edge from any vertex to another vertex. The following add method does exactly that. First, we check whether the start vertex is present in our verticesList, if not we add it. Then we add an edge object containing both start and end vertex to the edgesList. This way both our verticesList and edgesList are filled simultaneously, ie. stored our entire graph.
public void add(int start, int end){
if(!verticesList.contains(start)){
verticesList.add(start);
}
edgesList.add(new Edge(start, end));
}
Find Adjacent Vertices
Now that we have created our graph lets perform some operations on them. The first one is to find adjacent vertices of a given vertex. Adjacent vertices are those vertices to which we have an edge from the given vertex. For example, in the above graph, adjacent vertices of 1 are 2, 4, 5 as there are edges to 2, 4 and 5 respectively from 1.
The findAdjacent method takes a vertex as input and returns an ArrayList of verticesadjacent to the vertex. To find all adjacent vertices of vertex, we need to traverse all edges in the edgesList to check which edge contains vertex. If an edge contains vertex, we add the corresponding vertex of that edge to our adjacent list.
If startVertex is equal to vertex we add the endVertex to the list and if endVertex is equal to vertex we add startVertex to the list. In the end, we return the adjacent list.
If there are E edges then the worst case time complexity of this method will be O(E). Because to find adjacent of any vertex we are traversing through all the edges.
Find whether two nodes are connected
Two nodes are connected when they have an edge between them. Here also we traverse the whole edgesList and check whether vertices of each edge are equal to the given set of nodes or not. If we have a match then the two nodes are connected, otherwise, the two nodes are not connected.
public boolean isConnected(int start, int end){
for(Edge edge: edgesList){
if((edge.getStartVertex() == start && edge.getEndVertex() == end) ||
(edge.getStartVertex() == end && edge.getEndVertex() == start))
return true;
}
return false;
}
If there are E edges then the worst case time complexity of this method will also be O(E).
The entire code for this undirected unweighted graph is available here.
Weighted Undirected Graph
If the edges have a weight associated with them then we add another instance variable of integer type to the edge class to store the weight of that edge. And rest operations like adding the edge, finding adjacent vertices of given vertex, etc remain same. The code for a weighted undirected graph is available here.
Fig 3 Weighted Undirected Graph
/**
* Edge --- class to store an edge with a weight between Start vertex and End vertex
*/
class Edge{
private int startVertex;
private int endVertex;
private int weight;
public Edge(int startVertex, int endVertex, int weight){
this.startVertex = startVertex;
this.endVertex = endVertex;
this.weight = weight;
}
//Getter method for start vertex
public int getStartVertex(){
return startVertex;
}
//Getter method for end vertex
public int getEndVertex(){
return endVertex;
}
}
Weighted Directed Graph
Fig 4: Weighted Directed Graph
The entire representation of graph will be same as the undirected graph. Only the way to access adjacent list and find whether two nodes are connected or not will change. Because now we only have an edge (u,v). The code for the weighted directed graph is available here.
Why this implementation is not effective
For this implementation, we store the graph in an Edges List and a Vertices List. First, consider the space used in this representation. The first Vertices List is a simple integer array of size V (V is a total number of vertices in the graph). If we assume the integer takes constant space ie, O(1), then space to store V vertices will be O(V * 1) ie O(V). The second Edges List is an array of edge objects, and each edge object stores two or three integer variables. Therefore, each edge takes constant space, as we assume both integers takes constant space, ie O(1). If there are E edges then the space for Edges List is O(E). The total spacecomplexity of this representation is O(V + E).
We already know the time complexity of some operations from above, ie O(E). We traverse linearly through all edges to get our desired result. And the number of edges in a graph can be as high as V*V in the worst case. Which makes the time complexity of operations very high.
So, we need an implementation which has operations run in order of vertices instead of edges. In the next post, we study another way to store graph, ie Adjacency Matrix.
