Graph And LinkList Operation

/** * This class contains the operations related to Graph * @Date 9th Oct 2018 */ public class Graph { int numberOfVertex; LinkList[] edges; boolean[] visited; public Graph(int numberOfVertex){ this.numberOfVertex = numberOfVertex; //Declaration Adjacency List to save graph edges = new LinkList[this.numberOfVertex]; //Items in Adjacency List for(int i = 0; i < numberOfVertex; i++){ edges[i] = new LinkList(); } //This array helps in traversing the graph via marking vertex visited or not-visited visited = new boolean[this.numberOfVertex]; } //Add the node in Adjacency List public void addAnEdge(int endPoint1, int endPoint2){ edges[endPoint1].addNode(endPoint2); } public void print(){ for(int i = 0; i < this.numberOfVertex; i++){ System.out.print(i + " --- "); if(edges[i] != null) edges[i].printLinkList(); System.out.print("\n"); } } public void trimTheAdjanceyList(){ for(int i = 0; i < numberOfVertex; i++){ edges[i] = this.edges[i].deleteNode(0); } } public void DFSTraversal(int startingVertex){ //Checking whether the vertex has been visited or not if(visited[startingVertex]) return; //Marking the visiting vertex visited[startingVertex] = true; //Printing the marked vertex System.out.print(startingVertex+"->"); LinkList tempHead = edges[startingVertex]; //Traversing the Adjacency List while(tempHead != null) { DFSTraversal(tempHead.getData()); tempHead = tempHead.getNext(); if(tempHead == null) return; } } public void resetVisited(){ for(int i = 0; i < numberOfVertex; i++){ visited[i] = false; } } public void BFSTraversal(int startingVertex){ //Checking whether the vertex has been visited or not if(visited[startingVertex]) return; //Marking the visiting vertex visited[startingVertex] = true; //Printing the marked vertex System.out.print(startingVertex+"->"); LinkList tempHead = edges[startingVertex]; //Printing adjacency list of current vertex as adjacency list contains the traversal element in BFS format while(tempHead != null){ if(!visited[tempHead.getData()]) visited[tempHead.getData()] = true; System.out.print(tempHead.getData()+"->"); tempHead = tempHead.getNext(); } tempHead = edges[startingVertex]; //Traversing the Adjacency List while(tempHead != null) { BFSTraversal(tempHead.getData()); tempHead = tempHead.getNext(); if(tempHead == null) return; } } } public class LinkList { /** * This class contains the operations related to LinkList * @Date 9th Oct 2018 */ int data; LinkList next; // Default Constructor, it initialize the link list node with value 0 LinkList(){ } //It initialize the the link list with the data passed to it LinkList(int data){ this.data = data; next = null; } public int getData() { return data; } public void setData(int data) { this.data = data; } public LinkList getNext() { return next; } public void setNext(LinkList next) { this.next = next; } //add the node in link list public void addNode(LinkList node){ LinkList tempHead = this; //Traversing to last node while(tempHead.getNext() != null){ tempHead = tempHead.getNext(); } //add the passed node as a last node tempHead.setNext(node); } // Create a node with the passed data and add that node into link list public void addNode(int data){ addNode(new LinkList(data)); } //Print the link list public void printLinkList(){ LinkList tempHead = this; //Traversing to last node while(tempHead!= null){ System.out.print(tempHead.getData() + "-"); tempHead = tempHead.getNext(); } } //Delete the node which contains the same data as passed by the calling function public LinkList deleteNode(int data){ LinkList tempHead = this; LinkList previousNode = tempHead; //Traversing to the link list to find data while(tempHead.getNext() != null && tempHead.getData() != data){ previousNode = tempHead; tempHead = tempHead.getNext(); } //Adding the previous node of target node to next node of the target node if(tempHead.getData() == data){ if(tempHead.getData() == this.getData()) { previousNode = previousNode.getNext(); return previousNode; } else { previousNode.setNext(tempHead.getNext()); return this; } } else { return this; } } } public class EntryPoint { /** * This class contains the entry point to all class implemented in this package * @Date 9th Oct 2018 */ public static void main(String[] args) { LinkList headNode = new LinkList(1); //adding nodes to link list with the head node of 1 headNode.addNode(2); headNode.addNode(3); //print the entire link list headNode.printLinkList(); System.out.print(" (After adding 2 and 3 to link list)\n"); //Delete node which contains passing data from link list headNode = headNode.deleteNode(3); if(headNode != null) { headNode.printLinkList(); System.out.print("(After deleting 3 from link list)\n"); }else{ System.out.print("Link List is empty \n"); } if(headNode != null) { //Delete node which contains passing data from link list headNode = headNode.deleteNode(2); }else{ print("Link List is empty \n"); } if(headNode != null) { headNode.printLinkList(); print("(After deleting 2 from link list)\n"); }else{ print("Link List is empty \n"); } if(headNode != null) { //Delete node which contains passing data from link list headNode = headNode.deleteNode(1); }else{ print("Link List is empty \n"); } if(headNode != null) { //print the entire link list headNode.printLinkList(); print("(After deleting 1 from link list)\n"); } else{ print("Link List is empty after deleting 1 from link list \n"); } Graph obj = new Graph(4); obj.addAnEdge(0, 1); obj.addAnEdge(0, 2); obj.addAnEdge(0, 3); //Undirected Graph Addition obj.addAnEdge(1, 0); //Undirected Graph Addition obj.addAnEdge(1, 2); obj.addAnEdge(2, 0); obj.addAnEdge(2, 1); //Undirected Graph Addition obj.addAnEdge(2, 3); obj.addAnEdge(3, 0); //Undirected Graph Addition obj.addAnEdge(3, 3); //Deleted the first node of every list because it stores the irrelevant data obj.trimTheAdjanceyList(); obj.print(); // This function prints the graph in DFS print("DFS: "); obj.DFSTraversal(2); // Resetting all visited vertex, those are marked visited during DFS obj.resetVisited(); // This function prints the graph in BFS print("\nBFS: "); obj.BFSTraversal(2); } public static void print(String stringToPrint){ System.out.print(stringToPrint); } }