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.
- 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.
- 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
*/