”;
Overview
Graph is a datastructure to model the mathematical graphs. It consists of a set of connected pairs called edges of vertices. We can represent a graph using an array of vertices and a two dimentional array of edges.
Important terms
-
Vertex − Each node of the graph is represented as a vertex. In example given below, labeled circle represents vertices. So A to G are vertices. We can represent them using an array as shown in image below. Here A can be identified by index 0. B can be identified using index 1 and so on.
-
Edge − Edge represents a path between two vertices or a line between two vertices. In example given below, lines from A to B, B to C and so on represents edges. We can use a two dimentional array to represent array as shown in image below. Here AB can be represented as 1 at row 0, column 1, BC as 1 at row 1, column 2 and so on, keeping other combinations as 0.
-
Adjacency − Two node or vertices are adjacent if they are connected to each other through an edge. In example given below, B is adjacent to A, C is adjacent to B and so on.
-
Path − Path represents a sequence of edges betweeen two vertices. In example given below, ABCD represents a path from A to D.
Basic Operations
Following are basic primary operations of a Graph which are following.
-
Add Vertex − add a vertex to a graph.
-
Add Edge − add an edge between two vertices of a graph.
-
Display Vertex − display a vertex of a graph.
Add Vertex Operation
//add vertex to the array of vertex public void addVertex(char label){ lstVertices[vertexCount++] = new Vertex(label); }
Add Edge Operation
//add edge to edge array public void addEdge(int start,int end){ adjMatrix[start][end] = 1; adjMatrix[end][start] = 1; }
Display Edge Operation
//display the vertex public void displayVertex(int vertexIndex){ System.out.print(lstVertices[vertexIndex].label+" "); }
Traversal Algorithms
Following are important traversal algorithms on a Graph.
-
Depth First Search − traverses a graph in depthwards motion.
-
Breadth First Search − traverses a graph in breadthwards motion.
Depth First Search Algorithm
Depth First Search algorithm(DFS) traverses a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search when a dead end occurs in any iteration.
As in example given above, DFS algorithm traverses from A to B to C to D first then to E, then to F and lastly to G. It employs following rules.
-
Rule 1 − Visit adjacent unvisited vertex. Mark it visited. Display it. Push it in a stack.
-
Rule 2 − If no adjacent vertex found, pop up a vertex from stack. (It will pop up all the vertices from the stack which do not have adjacent vertices.)
-
Rule 3 − Repeat Rule 1 and Rule 2 until stack is empty.
public void depthFirstSearch(){ //mark first node as visited lstVertices[0].visited = true; //display the vertex displayVertex(0); //push vertex index in stack stack.push(0); while(!stack.isEmpty()){ //get the unvisited vertex of vertex which is at top of the stack int unvisitedVertex = getAdjUnvisitedVertex(stack.peek()); //no adjacent vertex found if(unvisitedVertex == -1){ stack.pop(); }else{ lstVertices[unvisitedVertex].visited = true; displayVertex(unvisitedVertex); stack.push(unvisitedVertex); } } //stack is empty, search is complete, reset the visited flag for(int i=0;i<vertexCount;i++){ lstVertices[i].visited = false; } }
Breadth First Search Algorithm
Breadth First Search algorithm(BFS) traverses a graph in a breadthwards motion and uses a queue to remember to get the next vertex to start a search when a dead end occurs in any iteration.
As in example given above, BFS algorithm traverses from A to B to E to F first then to C and G lastly to D. It employs following rules.
-
Rule 1 − Visit adjacent unvisited vertex. Mark it visited. Display it. Insert it in a queue.
-
Rule 2 − If no adjacent vertex found, remove the first vertex from queue.
-
Rule 3 − Repeat Rule 1 and Rule 2 until queue is empty.
public void breadthFirstSearch(){ //mark first node as visited lstVertices[0].visited = true; //display the vertex displayVertex(0); //insert vertex index in queue queue.insert(0); int unvisitedVertex; while(!queue.isEmpty()){ //get the unvisited vertex of vertex which is at front of the queue int tempVertex = queue.remove(); //no adjacent vertex found while((unvisitedVertex=getAdjUnvisitedVertex(tempVertex)) != -1){ lstVertices[unvisitedVertex].visited = true; displayVertex(unvisitedVertex); queue.insert(unvisitedVertex); } } //queue is empty, search is complete, reset the visited flag for(int i=0;i<vertexCount;i++){ lstVertices[i].visited = false; } }
Graph Implementation
Stack.java
package com.tutorialspoint.datastructure; public class Stack { private int size; // size of the stack private int[] intArray; // stack storage private int top; // top of the stack // Constructor public Stack(int size){ this.size = size; intArray = new int[size]; //initialize array top = -1; //stack is initially empty } // Operation : Push // push item on the top of the stack public void push(int data) { if(!isFull()){ // increment top by 1 and insert data intArray[++top] = data; }else{ System.out.println("Cannot add data. Stack is full."); } } // Operation : Pop // pop item from the top of the stack public int pop() { //retrieve data and decrement the top by 1 return intArray[top--]; } // Operation : Peek // view the data at top of the stack public int peek() { //retrieve data from the top return intArray[top]; } // Operation : isFull // return true if stack is full public boolean isFull(){ return (top == size-1); } // Operation : isEmpty // return true if stack is empty public boolean isEmpty(){ return (top == -1); } }
Queue.java
package com.tutorialspoint.datastructure; public class Queue { private final int MAX; private int[] intArray; private int front; private int rear; private int itemCount; public Queue(int size){ MAX = size; intArray = new int[MAX]; front = 0; rear = -1; itemCount = 0; } public void insert(int data){ if(!isFull()){ if(rear == MAX-1){ rear = -1; } intArray[++rear] = data; itemCount++; } } public int remove(){ int data = intArray[front++]; if(front == MAX){ front = 0; } itemCount--; return data; } public int peek(){ return intArray[front]; } public boolean isEmpty(){ return itemCount == 0; } public boolean isFull(){ return itemCount == MAX; } public int size(){ return itemCount; } }
Vertex.java
package com.tutorialspoint.datastructure; public class Vertex { public char label; public boolean visited; public Vertex(char label){ this.label = label; visited = false; } }
Graph.java
package com.tutorialspoint.datastructure; public class Graph { private final int MAX = 20; //array of vertices private Vertex lstVertices[]; //adjacency matrix private int adjMatrix[][]; //vertex count private int vertexCount; private Stack stack; private Queue queue; public Graph(){ lstVertices = new Vertex[MAX]; adjMatrix = new int[MAX][MAX]; vertexCount = 0; stack = new Stack(MAX); queue = new Queue(MAX); for(int j=0; j<MAX; j++) // set adjacency for(int k=0; k<MAX; k++) // matrix to 0 adjMatrix[j][k] = 0; } //add vertex to the vertex list public void addVertex(char label){ lstVertices[vertexCount++] = new Vertex(label); } //add edge to edge array public void addEdge(int start,int end){ adjMatrix[start][end] = 1; adjMatrix[end][start] = 1; } //display the vertex public void displayVertex(int vertexIndex){ System.out.print(lstVertices[vertexIndex].label+" "); } //get the adjacent unvisited vertex public int getAdjUnvisitedVertex(int vertexIndex){ for(int i=0; i<vertexCount; i++) if(adjMatrix[vertexIndex][i]==1 && lstVertices[i].visited==false) return i; return -1; } public void depthFirstSearch(){ //mark first node as visited lstVertices[0].visited = true; //display the vertex displayVertex(0); //push vertex index in stack stack.push(0); while(!stack.isEmpty()){ //get the unvisited vertex of vertex which is at top of the stack int unvisitedVertex = getAdjUnvisitedVertex(stack.peek()); //no adjacent vertex found if(unvisitedVertex == -1){ stack.pop(); }else{ lstVertices[unvisitedVertex].visited = true; displayVertex(unvisitedVertex); stack.push(unvisitedVertex); } } //stack is empty, search is complete, reset the visited flag for(int i=0;i<vertexCount;i++){ lstVertices[i].visited = false; } } public void breadthFirstSearch(){ //mark first node as visited lstVertices[0].visited = true; //display the vertex displayVertex(0); //insert vertex index in queue queue.insert(0); int unvisitedVertex; while(!queue.isEmpty()){ //get the unvisited vertex of vertex which is at front of the queue int tempVertex = queue.remove(); //no adjacent vertex found while((unvisitedVertex=getAdjUnvisitedVertex(tempVertex)) != -1){ lstVertices[unvisitedVertex].visited = true; displayVertex(unvisitedVertex); queue.insert(unvisitedVertex); } } //queue is empty, search is complete, reset the visited flag for(int i=0;i<vertexCount;i++){ lstVertices[i].visited = false; } } }
Demo Program
GraphDemo.java
package com.tutorialspoint.datastructure; public class GraphDemo { public static void main(String args[]){ Graph graph = new Graph(); graph.addVertex(''A''); //0 graph.addVertex(''B''); //1 graph.addVertex(''C''); //2 graph.addVertex(''D''); //3 graph.addVertex(''E''); //4 graph.addVertex(''F''); //5 graph.addVertex(''G''); //6 /* 1 2 3 * 0 |--B--C--D * A--| * | * | 4 * |-----E * | 5 6 * | |--F--G * |--| */ graph.addEdge(0, 1); //AB graph.addEdge(1, 2); //BC graph.addEdge(2, 3); //CD graph.addEdge(0, 4); //AC graph.addEdge(0, 5); //AF graph.addEdge(5, 6); //FG System.out.print("Depth First Search: "); //A B C D E F G graph.depthFirstSearch(); System.out.println(""); System.out.print("Breadth First Search: "); //A B E F C G D graph.breadthFirstSearch(); } }
If we compile and run the above program then it would produce following result −
Depth First Search: A B C D E F G Breadth First Search: A B E F C G D
”;