Question

1. Implement the graph ADT using the adjacency list structure.

2. Implement the graph ADT using the adjacency matrix structure.

LANGUAGE IS IN JAVA

Comment for any questions

Data structures and algorithms

Answer 1

Save this file as Adjacency.java since class Adjacency is public

CODE FOR ADJACENCY LIST IN JAVA:

//implementation of Adjacency list
import java.util.LinkedList;

public class Adjacency
{
   // class to represent a graph.
   // A graph is an array of adjacency lists.
   static class Graph
   {
       int nVertices;
       LinkedList<Integer> adjListArray[];
      
       // constructor
       //Size of array and = number of vertices in graph
       Graph(int nVertices)
       {
           this.nVertices = nVertices;
           adjListArray = new LinkedList[nVertices];
          
           // Creating a new list for each vertex tp store adjacent nodes
           for(int i = 0; i < nVertices ; i++){
               adjListArray[i] = new LinkedList<>();
           }
       }
   }
  
   // To add edge
   static void addEdge(Graph graph, int src, int dest)
   {
       // To add edge from source to destination
       graph.adjListArray[src].add(dest);
      
   // To add an edge from destination to source since the graph is undirected
       graph.adjListArray[dest].add(src);
   }
  
   //function to print the adjacency list for a given graph
   static void print(Graph graph)
   {     
       for(int v = 0; v < graph.nVertices; v++)
       {
           System.out.println("Adjacency list of vertex "+ v);
           System.out.print("head");
           for(Integer pCrawl: graph.adjListArray[v]){
               System.out.print(" -> "+pCrawl);
           }
           System.out.println("\n");
       }
   }
  
   // Driver function
   public static void main(String args[])
   {
       // creating a graph
       int V = 5;
       Graph graph = new Graph(V);
       addEdge(graph, 0, 1);
       addEdge(graph, 0, 4);
       addEdge(graph, 1, 2);
       addEdge(graph, 1, 3);
       addEdge(graph, 1, 4);
       addEdge(graph, 2, 3);
       addEdge(graph, 3, 4);
  
       // printing the adjacency list
       print(graph);
   }
}
SCREENSHOT AND OUTPUT OF THE PROGRAM:

OUTPUT:

CODE FOR ADJACENCY MATRIX IN JAVA:

Save this class in a file named Graph.java

//Adjacency Matrix in Java
public class Graph {
// Two-dimensional matrix that will store only boolean values
private boolean adjMatrix[][];
  
//store the value of the number of vertices in a graph
private int nVertices;

public Graph(int nVertices) {
this.nVertices = nVertices;
adjMatrix = new boolean[nVertices][nVertices];
}
//To add Edge
public void addEdge(int i, int j) {
adjMatrix[i][j] = true;
adjMatrix[j][i] = true;
}
//To remove Edge
public void removeEdge(int i, int j) {
adjMatrix[i][j] = false;
adjMatrix[j][i] = false;
}
//To return edge
public boolean isEdge(int i, int j) {
return adjMatrix[i][j];
}
public String toString() {
StringBuilder s = new StringBuilder();
for (int i = 0; i < nVertices; i++) {
s.append(i + ": ");
for (boolean j : adjMatrix[i]) {
s.append((j?1:0) + " ");
}
s.append("\n");
}
return s.toString();
}
//Driver function
public static void main(String args[])
{
Graph graph = new Graph(4);

graph.addEdge(1, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);

//Printing the adjacency matrix
System.out.print(graph.toString());
}
}

SCREENSHOTS OF CODE AND SAMPLE OUTPUT:

OUTPUT:

HAPPY LEARNING