Java

/* BFS.java   Template for Breadth First Search      This template includes some testing code to help verify the implementation.   To interactively provide test inputs, run the program with           To conveniently test the algorithm with a large input, create a text file   containing one or more test graphs (in the format described below) and run   the program with        java BFS file.txt   where file.txt is replaced by the name of the text file which contains the    graph.      The input consists of a series of graphs in the following format:                       ...                   An input file can contain an unlimited number of graphs; each will be    processed separately.*/import java.util.Scanner;import java.util.LinkedList; import java.util.Queue;import java.io.File;public class BFS {        /* BFS(G)           Given an adjacency matrix describing a undirected graph, print the           listing of vertices encountered by a Queue based breadth-first            search starting at vertex 0.        */        public static void QueueBasedBFS(int[][] G) {                int n = G.length;                /* ... Your code here ... */                        }                                /* main()           Contains code to test the BFS method.        */        public static void main(String[] args) {                Scanner s;                if (args.length > 0) {                        try{                                s = new Scanner(new File(args[0]));                        } catch (java.io.FileNotFoundException e){                                System.out.printf("Unable to open %s",args[0]);                                return;                        }                        System.out.printf("Reading input values from %s.",args[0]);                }else {                        s = new Scanner(System.in);                        System.out.printf("Reading input values from stdin.");                }                                int graphNum = 0;                double totalTimeSeconds = 0;                                //Read graphs until EOF is encountered (or an error occurs)                while(true) {                        graphNum++;                        if(graphNum != 1 && !s.hasNextInt())                                break;                        System.out.printf("Reading graph %d",graphNum);                        int n = s.nextInt();                        int[][] G = new int[n][n];                        int valuesRead = 0;                        for (int i = 0; i 0)?totalTimeSeconds/graphNum:0);        }}

graph1.txt

6
0 0 0 1 1 0
0 0 1 0 1 1
0 1 0 0 0 1
1 0 0 0 1 0
1 1 0 1 0 0
0 1 1 0 0 0

Transcribed Image Text:

Question 2 (BFS): Breadth-first search (BFS) is an algorithm for traversing or searching a tree or graph data structures. Same as DFS, it starts at the tree root (or some arbitrary node as the root node in the case of a graph) and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. In this lab, you will be implementing a queue based BFS on undirected graphs giving in adjacency matrix (in 2d array). Use the pseudocode provided below as a general guideline. Algorithm BFS(G): Initialize a new empty LinkedList based queue Q Initialize a new Boolean array visited Enqueue v in Q Set v as explored in visited While Q is not empty do v = dequeue from Q For each w in incident edges of v in adjacency matrix G do If w is unexplored do Set w as explored in visited Enqueue w in Q Question 2 (BFS): Breadth-first search (BFS) is an algorithm for traversing or searching a tree or graph data structures. Same as DFS, it starts at the tree root (or some arbitrary node as the root node in the case of a graph) and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. In this lab, you will be implementing a queue based BFS on undirected graphs giving in adjacency matrix (in 2d array). Use the pseudocode provided below as a general guideline. Algorithm BFS(G): Initialize a new empty LinkedList based queue Q Initialize a new Boolean array visited Enqueue v in Q Set v as explored in visited While Q is not empty do v = dequeue from Q For each w in incident edges of v in adjacency matrix G do If w is unexplored do Set w as explored in visited Enqueue w in Q

Answer rating: 100% (QA)

Heres a possible implementation of the BFS algorithm in Java java import javautilLinkedList import j... View the full answer