Java Depth First Search

Chapter: Interview Programs Last Updated: 04-12-2016 16:33:31 UTC

Program:

            /* ............... START ............... */
                

import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Stack;

public class JavaDepthFirstSearch {

	private Stack<Integer> stack;

	public JavaDepthFirstSearch() {
		stack = new Stack<Integer>();
	}

	public void dfs(int adjacency_matrix[][], int source) {
		int number_of_nodes = adjacency_matrix[source].length - 1;

		int visited[] = new int[number_of_nodes + 1];
		int element = source;
		int i = source;
		System.out.print(element + "\t");
		visited[source] = 1;
		stack.push(source);

		while (!stack.isEmpty()) {
			element = stack.peek();
			i = element;
			while (i <= number_of_nodes) {
				if (adjacency_matrix[element][i] == 1 && visited[i] == 0) {
					stack.push(i);
					visited[i] = 1;
					element = i;
					i = 1;
					System.out.print(element + "\t");
					continue;
				}
				i++;
			}
			stack.pop();
		}
	}

	public static void main(String... arg) {
		int number_of_nodes, source;
		Scanner scanner = null;
		try {
			System.out.println("Enter the number of nodes in the graph");
			scanner = new Scanner(System.in);
			number_of_nodes = scanner.nextInt();

			int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
			System.out.println("Enter the adjacency matrix");
			for (int i = 1; i <= number_of_nodes; i++)
				for (int j = 1; j <= number_of_nodes; j++)
					adjacency_matrix[i][j] = scanner.nextInt();

			System.out.println("Enter the source for the graph");
			source = scanner.nextInt();

			System.out.println("The DFS Traversal for the graph is given by ");
			JavaDepthFirstSearch dfs = new JavaDepthFirstSearch();
			dfs.dfs(adjacency_matrix, source);
		} catch (InputMismatchException inputMismatch) {
			System.out.println("Wrong Input format");
		}
		scanner.close();
	}
}
                /* ............... END ............... */
        

Output

Enter the number of nodes in the graph
4
Enter the adjacency matrix
0 1 0 1
0 0 1 0
0 1 0 1
0 0 0 1
Enter the source for the graph
1
The DFS Traversal for the graph is given by 
1	2	3	4

Tags

Depth First Search, Java, Interview Programs

Similar Programs Chapter Last Updated
Java Program To Find Frequency Of Character In String Interview Programs 28-09-2017
Java Program To Find Power Of Number Using While Loop Interview Programs 30-08-2017
Java Program To Count Divisors Of Integer Number Interview Programs 24-06-2017
Java Program To Sort N Names In Ascending Order Interview Programs 24-06-2017
Java Program To Count Total Number Of Words In String Interview Programs 24-06-2017
Java Program To Print All Prime Numbers From 1 to N Interview Programs 24-06-2017
Java Program To Extract Digits / Numbers From String Interview Programs 22-09-2018
Java First Repeated Character In String Interview Programs 16-05-2017
Java String Character Repetition Count Interview Programs 15-05-2017
Java Program To Check Vowel Or Not Interview Programs 25-09-2018
Java Program To Check Alphabet Or Not Interview Programs 06-04-2017
Java Program To Find First Repeated And Non Repeated Character In String Interview Programs 25-03-2017
Java Spiral Matrix Interview Programs 22-09-2018
Java Program To Reverse A Number Using Strings Interview Programs 13-02-2017
Java Program To Print Diamond Star Pattern Interview Programs 16-12-2016
Java Program To Print Pyramid Pattern Of Star Interview Programs 16-12-2016
Java Program To Find Second Largest Number In Array Interview Programs 04-12-2016
Java Breadth First Search Interview Programs 04-12-2016
Java Linked List Length Recursive Solution Interview Programs 17-11-2016
Java Linked List Length Iterative Solution Interview Programs 17-11-2016
Java Linked List Node Deletion At Given Position Interview Programs 17-11-2016
Java Linked List Node Delete Interview Programs 17-11-2016
Java Sum Of Digits Using Recursion Interview Programs 06-11-2016
Java Program To Reverse Vowels Of String Interview Programs 05-11-2016
Java Program To Remove Vowels From String Interview Programs 05-11-2016
Java Find Top Two Maximum Numbers In Array Interview Programs 05-11-2016
Java QuickSort Example Interview Programs 05-11-2016
Java Binary Tree Spiral Level Traversal Interview Programs 04-11-2016
Java Binary Tree Preorder Traversal Interview Programs 04-11-2016
Java Binary Tree InOrder Traversal Interview Programs 31-10-2016

1 2 3 4 5