This project has two parts. In the first part, you need to implement DFS in JAVA

Question

This project has two parts. In the first part, you need to implement DFS in JAVA. Your program should take as input a graph adjacency matrix, and generate the following: •

Order in which vertices are first encountered. Assume that the vertices are visited in numerical order when no other order is specified by the search. • Order in which vertices become dead-ends. •

The number of connected components in the graph. •

Tree edges. •

Back edges. Figure 1:

Example graph In the example graph shown in Figure 1, the input graph adjacency matrix is specified in a text file with the following content: 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0

Note that the vertex identifiers correspond to the row indices (and column indices) of the adjacency matrix. For the above example, DFS should generate the following vertex orderings (count value for vertices):

First encountered : 1 2 6 7 4 3 5 8 First dead ends : 8 7 5 4 1 2 6 3

The number of connected components is 1. The tree edges and back edges are given by two adjacency matrices:

2 Tree edges 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0

Back edges 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

In the second part of the project, you need to implement BFS in JAVA.

Your program should take as input a graph adjacency matrix as in DFS, and generate the following: •

Order in which vertices are first encountered. Assume that the vertices are visited in numerical order when no other order is specified by the search. • The number of connected components in the graph. •

Tree edges. •

Cross edges. For the graph in Figure 1, the program should generate the following vertex ordering (count value for vertices): 1 2 6 8 3 4 5 7 The number of connected components is 1. The tree edges and cross edges are given by two adjacency matrices:

Tree edges 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0

Cross edges 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0

Back ed 4 6 Figue 1: Exanlegh In the ecanple graph sws in Fgare , the paph wljery matrix ci in a test Sle with the 000o11 The of coted compont i 1. The tve dg and hack nd are given boy two adjacency matric 0000 1000 0010 0000 In the cond part of the pojnct, you awd to impn BES inJAVA. Your pong a gaph adjacency atri w in DES, dgsrrabe the folowing houkd taon w inpat no other oni ified by the wanc Foe the gph in Figure 1, the pgrm sold gemerate th llowing vertes cedering(count vaue for vertice 1268345

Explanation / Answer

Java Program to Traverse Graph using DFS

This Java program,performs the DFS traversal on the given graph represented by a adjacency matrix.the DFS traversal makes use of an stack.Here is the source code of the Java program to perform the dfs traversal. The Java program is successfully compiled and run on a Linux system

The code is as followes:

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

public class DFS
{
    private Stack<Integer> stack;

    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())
        {
            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();       
    }  
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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