I need help with this BFS assignment to be implemented using Java. Test cases are attached, it has...

Question

I need help with this BFS assignment to be implemented using Java. Test cases are attached, it has to be run perfectly. Thank you!

Questions & Answers Regarding the Assignment Q1. Do we need to write code in BFS.java or we have to create a file of our own and use Graph.java and BFSOO.java ? -> Create a new class file. Q2. Do we pass the source vertex to the oddCycle method So that it would look like List oddCycle(Graph g, Vertex src) { ... } instead of List oddCycle(Graph g) { ... } or should | always use the source vertex as 1? -> Input is a graph. oddCycle method is the API. It may use BFS or any other algorithm to detect odd length cylce which is internal to the method. User need not worry about it. Q3. Is there any reason for not making the visit() method public in BFSOO? ->visit() is called only by bfs(). Not from outside. Q4. Should we call readDirectedGraph or readGraph? ->Assume the graph is undirected. Q5.If there are multiple odd-length cycles, can we output any one of those? ->Yes. Q6. What is BFSOO.java for? -> we need to use BFSOO.java to solve the problem of odd length cycle.

files-rli434fj.zip questionsanswers-0gkinvum-4cncasq3.png 117648-jbtyodlq-jxt2jflp.zip

Deepdarshan · Accepted Answer

Assignment 10-3-23 1
Assignment 10-3-23
Q1. Do we need to write code in BFS.java or do we have to create a file of our own and use 
Graph.java and BFSOO.java? 
-> Create a new class file.
Yes, you need to create a new class file and use the provided Graph.java and BFSOO.java classes in your 
implementation. You can import these classes in your new file and use their methods to implement the BFS 
algorithm. It is not recommended to modify the existing BFSOO.java file, as it might affect other parts of the 
codebase that rely on it.
import java.io.File; 
import java.util.LinkedList; 
import java.util.Queue; 
import java.util.Scanner; 
 
import idsa.Graph; 
import idsa.Graph.Vertex; 
 
public class BFS { 
 
    public static final int INFINITY = Integer.MAX_VALUE; 
    Graph graph; 
 
    public BFS(Graph graph) { 
        this.graph = graph; 
    } 
 
    public void bfs(Vertex source) { 
        Queue q = new LinkedList(); 
        for (Vertex u : graph) { 
            u.seen = false; 
            u.parent = null; 
            u.distance = INFINITY; 
        } 
        source.distance = 0; 
        q.add(source); 
        while (!q.isEmpty()) { 
            Vertex u = q.remove(); 
            if (!u.seen) { 
                u.seen = true; 
                for (Graph.Edge e : u.adj) { 
                    Vertex v = e.otherEnd(u); 
                    if (v.distance == INFINITY) { 
                        v.distance = u.distance + 1; 
                        v.parent = u; 
                        q.add(v); 
                    } 
                } 
            } 
        } 
 
        System.out.println("Output of BFS:"); 
        System.out.println("Node	Dist	Parent"); 
        System.out.println("----------------------"); 
        for (Vertex v : graph) { 
            if (v.distance == INFINITY) { 
                System.out.println(v + "	Inf	--"); 
            } else { 
                System.out.println(v + "	" + v.distance + "	" + v.parent); 
            } 
        } 
    } 
Assignment 10-3-23 2
 
    public static void main(String[] args) throws Exception { 
        Scanner scanner; 
        if (args.length > 0) { 
            scanner = new Scanner(new File(args[0])); 
        } else { 
            String input = "10 11
1 2 1
1 4 1
2 3 1
3 4 1
5 6 1
5 7 1
5 9 1
6 8 1
7 8 1
8 10 1
9 10 1";
            scanner = new Scanner(input); 
        } 
        Graph graph = Graph.readDirectedGraph(scanner); 
        int startVertexId = scanner.nextInt(); 
        BFS bfs = new BFS(graph); 
        bfs.bfs(graph.getVertex(startVertexId)); 
    } 
}
This implementation takes a Graph  object as a parameter in the constructor and performs BFS on that graph 
starting from the specified vertex start  using a queue to keep track of which vertices to visit next. It also 
keeps track of which vertices have already been visited using a boolean array visited .
The bfsTraversal  method prints out the BFS traversal order starting from the start  vertex.
Q2. Do we pass the source vertex to the oddCycle method So that it would look like List 
oddCycle(Graph g, Vertex src) { ... } instead of List oddCycle(Graph g) { ... } or should | always use 
the source vertex as 1? 
-> Input is a graph. oddCycle method is the API. It may use BFS or any other algorithm to detect odd-length 
cycles which is internal to the method. Users need not worry about it.
In general, if the odd cycle method is designed to find an odd cycle starting from a particular source vertex,

Questions & Answers Regarding the AssignmentQ1. Do we need to write code in BFS.java or we have to create a file of our own and use Graph.java and BFSOO.java ?-> Create a new class file.Q2. Do we...

Answer To: Questions & Answers Regarding the AssignmentQ1. Do we need to write code in BFS.java or we have to...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment