My Blog. : Graph representation using adjacency matrix and adjacency list in Java.

In computer science graphs are data structures that can be used to model many types of physical problems. Graph is a collection of vertices and edges, edge represent connection between two vertices. For example, in a graph representing a city various vertices can represent important landmarks of city and edges can represent roads connecting various landmarks.

Below are few graph terms-
Adjacent - A vertex is said to be adjacent to another vertex if it connected by single edge.


Fig 3.0

For example in above graph vertices adjacent to A are B and C.
Similarly A and C are adjacent to vertex A.

Paths - It is sequence of various connected edges. For example in above figure ACD, ABCD are various paths.

Connected Graph - A graph is said to be connected if there exist a path from any vertex to any other vertex of graph. Graph represented by Fig. 3.0 is connected graph.

Disconnected Graph - A graph is said to be disconnected if it is not connected i.e. if we start from one vertex of graph and we can not reach some vertices thats means there is no connection with those vertices. Below figure is example of disconnected graph, if we start from A we can not reach B and D. Similarly if we start from B or D we can not reach A and C.

Fig. 3.1

Directed Graph - A Graph is said to be directed if edges have direction.

Fig. 3.2

Fig. 3.2 is an example of directed graph. Edge AB has direction i.e. you can go from A to B but not from B to A. Fig. 3.0 and Fig. 3.1 are example of undirected graph, you can go either way in edge of undirected graph. In fig. 3.0 for edge AB we can go A to B or B to A.

Weighted Graph - In weighted graph every edge has some weight.

Fig. 3.3

If vertices in above graphs represent places in a city then edges weight can represent distance in Km. between those places or may be it can represent cost of ticket between those places.

Java code to represent a Graph.
There are two different ways to represent edges of a graph in programming - adjacency matrix and adjacency lists. I will be discussing both these methods in this post.

Representation using Adjacency matrix.

public class GraphAdjacencyMatrix {
 protected int maxVertsNum;
 protected int numVerts;
 protected Vertex [] vertexList;
 protected int [][] adjMatrix;
 
 public GraphAdjacencyMatrix(int maxVerts){
  maxVertsNum = maxVerts;
  numVerts = 0;
  vertexList = new Vertex[maxVertsNum];
  adjMatrix = new int[maxVertsNum][maxVertsNum];
  //Initializing all entries to zero.
  for (int i = 0; i < maxVertsNum; i++) {
   for (int j = 0; j < maxVertsNum; j++) {
    adjMatrix[i][j] = 0;
   }
  }
 }
 
 public void addVertex(char label){
  if(numVerts < maxVertsNum){
   vertexList[numVerts++] = new Vertex(label);
  }
 }
 
 public void addEdge(int start, int end){
  if(start < numVerts && end < numVerts){
   adjMatrix[start][end] = 1;
   adjMatrix[end][start] = 1;
  }
 }
 
 public boolean hasEdge(int src, int dest){
  return adjMatrix[src][dest]==1;
 }
 
 public boolean isVertexVisited(int vertex){
  return vertexList[vertex].isVisited;
 }
 
 public void display(int idx){
  System.out.print(vertexList[idx].label);
 }
 
 public void displayAllEdges(){
  System.out.println("All edges are:");
  for (int i = 0; i < numVerts; i++) {
   for (int j = 0; j < numVerts; j++) {
    if(adjMatrix[i][j]==1){
     System.out.print(vertexList[i].label+""+vertexList[j].label);
     System.out.print(" ");
    }
   }
  }
  System.out.println();
 }

 public static void main(String[] args) {
  GraphAdjacencyMatrix graph = new GraphAdjacencyMatrix(5);
  graph.addVertex('A'); //0
  graph.addVertex('B'); //1
  graph.addVertex('C'); //2
  graph.addVertex('D'); //3
  
  graph.addEdge(0, 1);
  graph.addEdge(0, 2);
  graph.addEdge(1, 2);
  graph.addEdge(2, 3);
  
  graph.displayAllEdges();
  
  System.out.println("Is there an edge between "+graph.vertexList[0].label+" and "+graph.vertexList[2].label+" = "+graph.hasEdge(0, 2));
  System.out.println("Is there an edge between "+graph.vertexList[1].label+" and "+graph.vertexList[3].label+" = "+graph.hasEdge(1, 3));
 }
}

class Vertex{
 public char label;
 public boolean isVisited = false;
 
 public Vertex(char label){
  this.label = label;
 }
}

Output:
All edges are:
AB AC BA BC CA CB CD DC
Is there an edge between A and C = true
Is there an edge between B and D = false

Explanation:
Below table represent adjacency matrix of graph that is made in above program and fig 3.0 represent same graph. 2-D array adjMatrix is used to hold connection between various vertices. For example there is connection between AB and BA so 1 is present in row A column B and row B column A. Since this adjacency matrix is for undirected graph so both AB and BA is 1. There is no connection between A and D so row A and column D has 0. Whenever we add an edge between 2 vertices in graph the corresponding value in adjacency matrix is set to 1 in addEdge method.

Representation of Graph using Adjacency List:
In adjacency list approach for each vertex we have a list that contains all of its adjacent vertices.

Java Code:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class GraphAdjacencyList {
 private List<List<Integer>> adjList;
 private int maxVerts;
 private int numVerts;
 private Vertex[] vertList;
 
 public GraphAdjacencyList(int maxVerts){
  this.maxVerts = maxVerts;
  numVerts = 0;
  adjList = new ArrayList<List<Integer>>();
  vertList = new Vertex[maxVerts];
  for (int i = 0; i < maxVerts; i++) {
   adjList.add(new LinkedList<Integer>());
  }
 }

 public void addVertex(char label){
  if(numVerts < maxVerts){
   vertList[numVerts++] = new Vertex(label);
  }
 }
 
 public void addEdge(int src, int dest){
  if(src < numVerts && dest < numVerts){
   adjList.get(src).add(dest);
   adjList.get(dest).add(src);
  }
 }
 
 public boolean hasEdge(int src, int dest){
  return adjList.get(src).contains(dest);
 }
 
 public void display(int idx){
  System.out.print(vertList[idx].label);
 }
 
 public void displayAllEdges(){
  for (int i = 0; i < adjList.size(); i++) {
   List<Integer> adjVertex = adjList.get(i);
   for (int j = 0; j < adjVertex.size(); j++) {
    System.out.print(""+vertList[i].label+""+vertList[adjVertex.get(j)].label+" ");
   }
  }
  System.out.println();
 }
 
 public static void main(String[] args) {
  GraphAdjacencyList graph = new GraphAdjacencyList(5);
  graph.addVertex('A'); //0
  graph.addVertex('B'); //1
  graph.addVertex('C'); //2
  graph.addVertex('D'); //3
  
  graph.addEdge(0, 1);
  graph.addEdge(0, 2);
  graph.addEdge(1, 2);
  graph.addEdge(2, 3);
  
  graph.displayAllEdges();
  
  System.out.println("Vertices adjacent to "+graph.vertList[0].label+" are ");
  List<Integer> list = graph.adjList.get(0);
  for (int i = 0; i < list.size(); i++) {
   System.out.print(graph.vertList[list.get(i)].label);
  }
 }
}

Output:
AB AC BA BC CA CB CD DC
Vertices adjacent to A are
BC

Explanation:
For every vertex we have list that contains adjacent vertices to that vertex. Whenever an edge is added between 2 vertices the destination vertex is added to adjacency list of source vertex. The vertices adjacent to various vertex are:
Vertex            Adjacent vertices in adjacency list
A         -         B, C
B         -         A, C
C         -         A, B D
D         -         C

When to use Adjacency matrix and Adjacency list:
1. In adjacency matrix approach space usage is proportional to V^2 where V is number of vertices in graph. So if graph is sparse i.e. it has less number of edges between various vertices then adjacency matrix approach will result in waste of space because in adjacency matrix of sparse graph lot of entries will be 0 indicating no connection. So if in sparse graph we use adjacency list approach we will be storing only vertcies that are connected to given vertex in a list for that vertex. In adjacency list approach space is proportional to both total edges and vertices. So if we have sparse array it will be better to use adjacency list to save space.

2. In adjacency matrix approach operation to check whether there is an edge between 2 vertices is fast and it take O(1) time because for that we have to check entry in array, where is in adjacency list approach we have to iterate over list to find if there is an edge between 2 vertices so it is slow and takes O(V) time. So if we need fast time to check if there is edge between 2 particular vertices then adjacency matrix approach is better.

My Blog.

Monday, November 24, 2014

Graph representation using adjacency matrix and adjacency list in Java.

1 comment:

Total Pageviews