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.
Learn Java in-depth with real-world projects through our Java certification course. Enroll and become a certified expert to boost your career.
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
Graph