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:

1. Edges and Vertices List.
2. Adjacency Matrix
3. 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.

 

Consider above graph, the vertices can be stored in a vertices array and the edges can be stored in a separate array. 

 

 

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.

 

public ArrayList<Integer> findAdjacent(int vertex){
	ArrayList<Integer> adjacent = new ArrayList<Integer>();
	for(Edge edge: edgesList){
	    if(edge.getStartVertex() == vertex)
		adjacent.add(edge.getEndVertex());
	    else if(edge.getEndVertex() == vertex)
		adjacent.add(edge.getStartVertex());
	}
	return adjacent;
}

 

 

The findAdjacent method takes a vertex as input and returns an ArrayList of vertices adjacent 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.

 

 

/**
* 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

 

 

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 space complexity 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.