Implementing Graph Traversing Algorithms in Java

Graph traversal is the problem of visiting all the nodes in a graph in a particular manner, updating and/or checking their values along the way. There are two methods for graph traversal, they are as follows.

  1. Depth-first search: DFS visits the child nodes before visiting the sibling nodes; that is, it traverses the depth of any particular path before exploring its breadth.
  2. Breadth-first search: FS visits the parent nodes before visiting the child nodes.
package graphtraversal;
import java.io.*;
class Quec {
    public int front, rear, n, que[];
    public Quec() {
        n = 20;
        que = new int[20];
        front = 0;
        rear = -1;
    }
    public boolean isFull() {
        if (rear == n - 1)
            return true;
        else
            return false;
    }
    public void enque(int x) {
        if (isFull() == true)
            System.out.println("No Space");
        else {
            rear++;
            que[rear] = x;
        }
    }
    public void display() {
        if (isEmpty() == true)
            System.out.println("Queue is empty");
        else {
            for (int i = front; i <= rear; i++) {
                System.out.print(que[i] + " ");
            }
        }
    }
    public boolean isEmpty() {
        if (rear < front)
            return true;
        else
            return false;
    }
    public int deque() {
        if (isEmpty() == true) {
            System.out.println("Queue is empty");
            return -1;
        } else {
            int x = que[front];
            front++;
            return x;
        }
    }
}
class grapht {
    Quec que = new Quec();
    int matrix[][];
    int vseq[], vo[], ne, vseqc, voc;
    public grapht(int m[][], int s) {
        matrix = m;
        ne = s;
        vseq = new int[ne];
        vo = new int[ne];
        vseqc = 0;
        voc = 0;

    }
    public void bfs(int ele) {
        que.enque(ele);
        vseq[vseqc] = ele;
        vseqc++;
        while (que.isEmpty() != true) {
            int x = que.deque();
            for (int i = 0; i < ne; i++) {
                if (matrix[x][i] == 1 && vseqsearch(i) != true) {
                    que.enque(i);
                    vseq[vseqc] = i;
                    vseqc++;
                }
            }
        }
        System.out.println("BFS:");
        for (int t = 0; t < ne; t++) {
            System.out.print(vseq[t] + " ");
        }
    }
    public boolean vseqsearch(int x) {
        for (int i = 0; i < ne; i++) {
            if (vseq[i] == x)
                return true;
        }
        return false;
    }
    public void dfs(int x) {
        vo[voc] = x;
        voc++;
        for (int i = 0; i < ne; i++) {
            if (matrix[x][i] == 1 && vosearch(i) == false) {
                dfs(i);
            }
        }
    }
    public void printdfs() {
        System.out.println();
        System.out.println("DFS:");
        for (int i = 0; i < ne; i++) {
            System.out.print(vo[i] + " ");
        }
    }
    public boolean vosearch(int x) {
        for (int i = 0; i < ne; i++) {
            if (vo[i] == x)
                return true;
        }
        return false;
    }
}
public class GraphTraversal {
    public static void main(String[] args) throws IOException {
        BufferedReader obj = new BufferedReader(new InputStreamReader(System.in));
        int matrix[][];
        int size;
        System.out.println("enter no of vertices");
        size = Integer.parseInt(obj.readLine());
        matrix = new int[size][size];
        System.out.println("Enter Matrix");
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                matrix[i][j] = Integer.parseInt(obj.readLine());
            }
        }
        grapht gt = new grapht(matrix, size);
        System.out.println("Enter stating element");
        int x1 = Integer.parseInt(obj.readLine());
        gt.bfs(x1);
        gt.dfs(x1);
        gt.printdfs();
    }
}
/* Output

enter no of vertices
7
Enter Matrix
0
1
1
1
1
0
0
1
0
0
1
1
0
0
1
0
0
0
0
1
1
1
1
0
0
1
0
0
1
1
0
1
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
1
0 
Enter stating element
0
BFS:
0 1 2 3 4 5 6 
DFS:
0 1 3 4 2 5 6
 */

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.