Tag Archives: DFS

Java Data Structure Implementation : Undirected Simple Graph (BFS/DFS)

This program demonstrates the Undirected Simple Graph implementation using link list, Queue & Stack in Java.
The Operation implemented :
1. Insert Vertex/Edge,
2. Delete Vertex/Edge,
3. Breadth First Traversal (Used my Stack Program)
4. Depth First Traversal (Used my Queue Program)
5. Print Adjancy List (Used my List Program)
6. Print Vertices Data

The implementation logic and memory representation is shown in the below picture.

Undirected Simple Graph Impl

Undirected Simple Graph Implementations

Two Major Implementations Breadth First Traversal and Depth First Traversal are implemented using Queue and Stack respectively. This shows the best use/application of the Stack and Queue.

This implementation is implemented using the Link List, Stack and Queue so you need to download my Doubly link list, Stack and Queue code into your package before running this code. You can download the Doubly link list, Stack and Queue code from my previous blogs

Find the Java Code below :


import hclinfosys.ds.linklist.DoublyLinkList;
import hclinfosys.ds.queue.Queue;
import hclinfosys.ds.stack.StackUsingArray;

import java.util.Scanner;

/*
* This class represent the Graph Vertex.
* @author : Madan Gopal Singh
* @version : 1.0
* @date : 09th April, 2014
*/
class GraphVertex{
int id;
DoublyLinkList connectedEdges = null;
boolean isVisited = false;

public GraphVertex() {}

public GraphVertex(int id){
this.id=id;
}
}

/*
* This class demonstrates Graph Implementation in java with Insert/Delete/Traversal/Find Operations.
* @author : Madan Gopal Singh
* @version : 2.0
* @date : 11th April, 2014
*/
public class Graph {

public static int NO_OF_VERTICES = 7;
public static int TOP = -1;

public static GraphVertex[] vertices;

public Graph() {}

/**
* This method add new vertex in graph.
* @param vertexToBeInserted.
* @return void.
*/
public static void addNewVertex(GraphVertex vertexToBeInserted){
if(TOP==NO_OF_VERTICES-1){
System.out.println("Graph Size Exceeded");
}else{
TOP=TOP+1;
vertices[TOP] = vertexToBeInserted;
System.out.println("Vertex Inserted at "+TOP+" with value : "+vertices[TOP].id);
}
}

/**
* This method remove vertex from graph.
* @param vertexToBeRemoved.
* @return void.
*/
public static void removeVertex(GraphVertex vertexToBeRemoved){
if(TOP==-1){
System.out.println("No Vertex in Graph");
}else{
//Removing Edges connected to vertex
DoublyLinkList startNode = vertexToBeRemoved.connectedEdges;
while(startNode!=null){
System.out.println("Node Info : "+startNode.id+" Index of Vertex : "+Graph.getVertexIndex(startNode.id));
GraphVertex destinationVertex = vertices[Graph.getVertexIndex(startNode.id)];
Graph.removeEdge(vertexToBeRemoved, destinationVertex);
startNode = startNode.next;
}
//Removing Vertex
int indexOfVertex = Graph.getVertexIndex(vertexToBeRemoved.id);
for(int i = indexOfVertex;i=0){
if(String.valueOf(vertices[i].id).equalsIgnoreCase((String)obj.toString())){
return i;
}
i = i-1;
}
return -1;
}
}

/**
* This method print all vertices of the Graph.
* @param void.
* @return void.
*/
public static void printAllVertices(){
if(TOP == -1){
System.out.println("Graph has no vertices");
}else{
int i = TOP;
while(i>=0){
System.out.println("Element at position "+ i + " is :- "+vertices[i].id);
i = i-1;
}
}
}

/**
* This method print the Adjancy list of the Graph
* @return void
*/
public static void printAdjancyList(){
for(int i = 0; i=0){
vertices[i].isVisited = false;
System.out.println("Vertex "+ vertices[i].id + " is marked un visited.");
i = i-1;
}
}
}

/**
* This method prints the depth first traversal of the Graph from starting vertex.
* @param void.
* @return void.
*/
public static void depthFirstTraversal(GraphVertex startingVertex){
markAllVerticesNotVisted();//Marking all vertices not visited
int removedVertexId,removedVertexIndex;
String depthFirstTraversalSequence = "";
StackUsingArray.STACK_SIZE = NO_OF_VERTICES;
StackUsingArray.stackElements = new Object[StackUsingArray.STACK_SIZE];
StackUsingArray.push(vertices[0].id);
while(!StackUsingArray.isEmpty()){
Object removed = StackUsingArray.pop();
if(removed!=null){
removedVertexId = Integer.parseInt(removed.toString());
depthFirstTraversalSequence += removedVertexId+" ";
removedVertexIndex = Graph.getVertexIndex(removedVertexId);
vertices[removedVertexIndex].isVisited = true;
DoublyLinkList edges = vertices[removedVertexIndex].connectedEdges;
while(edges!=null){
if(vertices[Graph.getVertexIndex(edges.id)].isVisited==false && StackUsingArray.isElementExists(edges.id)==false){
StackUsingArray.push(edges.id);
}
edges = edges.next;
}
}
}
System.out.println("Depth First Traversal Sequence : "+depthFirstTraversalSequence);
}

/**
* This method prints the breadth first traversal of the Graph from starting vertex.
* @param void.
* @return void.
*/
public static void breadthFirstTraversal(GraphVertex startingVertex){
markAllVerticesNotVisted();//Marking all vertices not visited
int removedVertexId,removedVertexIndex;
String breadthFirstTraversalSequence = "";
Queue.QUEUE_SIZE = NO_OF_VERTICES;
Queue.queueList = new Object[Queue.QUEUE_SIZE];
Queue.insertIntoQueue(vertices[0].id);
while(!Queue.isEmpty()){
Object removed = Queue.removeFromQueue();
if(removed!=null){
removedVertexId = Integer.parseInt(removed.toString());
breadthFirstTraversalSequence += removedVertexId+" ";
removedVertexIndex = Graph.getVertexIndex(removedVertexId);
vertices[removedVertexIndex].isVisited = true;
DoublyLinkList edges = vertices[removedVertexIndex].connectedEdges;
while(edges!=null){
if(vertices[Graph.getVertexIndex(edges.id)].isVisited==false && Queue.isElementExists(edges.id)==false){
Queue.insertIntoQueue(edges.id);
}
edges = edges.next;
}
}
}
System.out.println("Breadth First Traversal Sequence : "+breadthFirstTraversalSequence);
}

/**
* This method main method to perform the Doubly Link List Operations.
* @param args command line argument list
* @return void.
*/
public static void main(String[] args) {
int userOperation = 0, vertexId=-1,fromVertexId=-1,toVertexId=-1,fromVertexIndex=-1,toVertexIndex=-1;

vertices = new GraphVertex[NO_OF_VERTICES];
GraphVertex vertexToBeInserted = null,sourceVertex = null,destinationVertex = null;
Scanner sc = new Scanner(System.in);
do{
String menuString = "\tSimple Undirected Graph \nWhat operation you want to perform?"+
"\n 1. Insert New Vertex"+
"\n 2. Insert New Edge"+
"\n 3. Remove Vertex"+
"\n 4. Remove Edge"+
"\n 5. Breadth First Traversal"+
"\n 6. Depth First Traversal"+
"\n 7. Print All Vertices"+
"\n 8. Print Adjancy List Representation"+
"\n -1. Exit from Menu"+
"\n Please enter Operation Number : ";
System.out.println(menuString);
userOperation = sc.nextInt();

switch(userOperation){
case 1:
System.out.println("Plese enter vertex Id to Insert: ");
vertexId = sc.nextInt();
vertexToBeInserted = new GraphVertex(vertexId);
System.out.println("Adding New Vertex");
Graph.addNewVertex(vertexToBeInserted);
break;
case 2:
System.out.println("Plese enter FROM vertex Id : ");
fromVertexId = sc.nextInt();
fromVertexIndex = Graph.getVertexIndex(fromVertexId);
System.out.println("Plese enter TO vertex Id : ");
toVertexId = sc.nextInt();
toVertexIndex = Graph.getVertexIndex(toVertexId);
System.out.println("From Vertext Index : "+fromVertexIndex);
System.out.println("To Vertext Index : "+toVertexIndex);
if(fromVertexIndex!=-1&&toVertexIndex!=-1){
sourceVertex = vertices[fromVertexIndex];
destinationVertex = vertices[toVertexIndex];
System.out.println("Destination Vertex Id : "+destinationVertex.id);
System.out.println("Adding Edge");
if(!Graph.isEdgeExists(sourceVertex, destinationVertex)){
Graph.addNewEdge(sourceVertex, destinationVertex);
}else{
System.out.println("Simple Graph doesn't allow multiple Edges. Please try new pair");
}
}
break;
case 3:
System.out.println("Plese enter vertex Id to Remove: ");
vertexId = sc.nextInt();
fromVertexIndex = Graph.getVertexIndex(vertexId);
if(fromVertexIndex!=-1){
vertexToBeInserted = vertices[fromVertexIndex];
System.out.println("Removing Vertex");
Graph.removeVertex(vertexToBeInserted);
}
break;
case 4:
System.out.println("Plese enter FROM vertex Id for Remove: ");
fromVertexId = sc.nextInt();
fromVertexIndex = Graph.getVertexIndex(fromVertexId);
System.out.println("Plese enter TO vertex Id for Remove: ");
toVertexId = sc.nextInt();
toVertexIndex = Graph.getVertexIndex(toVertexId);
if(fromVertexIndex!=-1&&toVertexIndex!=-1){
sourceVertex = vertices[fromVertexIndex];
destinationVertex = vertices[toVertexIndex];
System.out.println("Removing Edge");
if(Graph.isEdgeExists(sourceVertex, destinationVertex)){
Graph.removeEdge(sourceVertex, destinationVertex);
}else{
System.out.println("Edge doesnit exists between these pair of vertices. Please try new pair");
}
}
break;
case 5:
System.out.println("Breadth First Traversal from Starting Node");
Graph.breadthFirstTraversal(vertexToBeInserted);
break;
case 6:
System.out.println("Depth First Traversal from Starting Node");
Graph.depthFirstTraversal(vertexToBeInserted);
break;
case 7:
System.out.println("Printing All Elements");
Graph.printAllVertices();
break;
case 8:
System.out.println("Printing Adjancy List");
Graph.printAdjancyList();
break;
case -1:
System.out.println("Exit Application");
System.exit(0);
default : System.out.println("Exit from System");
}
}while(userOperation!=-1);
}
}

Any suggestion is invited if any.