In Java for my DFS, How to I get the output : \"First deadends : 8 7 5 4 1 2 6 3

Question

In Java for my DFS, How to I get the output :   "First deadends : 8 7 5 4 1 2 6 3"    To show where my program hits dead ends

Here is my code

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 + " ");      

            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 + " ");

                    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 ");

                DFS dfs = new DFS();

                dfs.dfs(adjacency_matrix, source);                  

            }catch(InputMismatchException inputMismatch)

            {

                System.out.println("Wrong Input format");

            }  

            scanner.close();  

        }  

    }

Explanation / Answer

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

public class DFS
{
private Stack<Integer> stack;
boolean flag; // whenever dead end will be encountered, this flag will be set
int count=0; // use to count no of dead end

public DFS()
{
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 + " ");      
visited[source] = 1;      
stack.push(source);

while (!stack.isEmpty())
{
flag=false;
element = stack.peek();
i = element;  
   while (i <= number_of_nodes)
   {
    if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
   {
       flag=true;// true means the node has other elements to traverse
stack.push(i);
visited[i] = 1;
element = i;
i = 1;
System.out.print(element + " ");
   continue;
}
i++;
   }
   if(flag==false){
       count++; //increment the no of dead ends
System.out.println(count+" Dead End ");
   }
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 ");
DFS dfs = new DFS();
dfs.dfs(adjacency_matrix, source);                  
}catch(InputMismatchException inputMismatch)
{
System.out.println("Wrong Input format");
}  
scanner.close();  
}  
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.