omplete the method to perform breadth first traversal (search) here is the method: private static void breadthFirst() { //Todo System.out.println("test"); }
Complete the method to perform breadth first traversal (search)
here is the method:
private static void breadthFirst() {
//Todo
System.out.println("test");
}
here is the complete source code:
Graph.java
---------------------------------
package finlab;
import java.util.*;
public class Graph {
List<Edge>[] list;
public Graph(int n){
list = new LinkedList[n];
for(int i=0; i<list.length;i++){
list[i] = new LinkedList<>();
}
}
void addEdge(int u, int v, int w){
list[u].add(0,new Edge(v,w));
}
boolean isConnected(int u, int v){
for(Edge e: list[u]) {
if (e.v == v)
return true;
}
return false;
}
@Override
public String toString(){
String result= "";
for(int i=0; i<list.length; i++){
result+= i+": "+list[i]+"\n";
}
return result;
}
}
Edge.java
--------------------------------------------------------
package finlab;
class Edge{
int v;
int w;
public Edge(int v,int w){
this.v = v;
this.w = w;
}
public int getVertex(){
return v;
}
public int getWeight(){
return w;
}
@Override
public String toString(){
return "("+v+", "+w+")";
}
}
Main.java
----------------------------------
package finlab;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("1. Load file containing the graph's data");
System.out.println("2. Perform Depth First Traversal of the graph");
System.out.println("3. Perform Breadth First Traversal of the graph");
System.out.println("4. Show to shortest path from one vertex to another");
System.out.println("5. Exit");
System.out.print("Enter your choice: ");
int c = scan.nextInt();
try {
while (c != 5) {
performChoice(c);
System.out.println("\n----------");
System.out.println("1. Load file containing the graph's data");
System.out.println("2. Perform Depth First Traversal of the graph");
System.out.println("3. Perform Breadth First Traversal of the graph");
System.out.println("4. Show to shortest path from one vertex to another");
System.out.println("5. Exit");
System.out.print("Enter your choice: ");
c = scan.nextInt();
}
}catch (Exception e){
System.out.println(e.getMessage());
}
}
static void performChoice(int c) throws Exception {
switch (c){
case 1 -> loadFile();
case 2 -> depthFirst();
case 3 -> breadthFirst();
case 4 -> dijkstra();
case 5 -> System.exit(0);
default -> System.out.println("Invalid choice, try again.");
}
}
private static void loadFile() throws Exception {
File file = new File("src/finlab/data.txt");
Scanner scan = new Scanner(file);
System.out.println("==========");
if(file.canRead()){
System.out.println("File is readable");
System.out.println("File contents: \n");
}else{
System.out.println("File is not readable");
}
while (scan.hasNextLine()){
System.out.println(scan.nextLine());
}
}
private static void depthFirst() {
///Todo
System.out.println("test");
}
private static void breadthFirst() {
//Todo
System.out.println("test");
}
private static void dijkstra() {
//Todo
System.out.println("test");
}
}
Test.java
------------------------------
package finlab;
public class Test {
public static void main(String[] args) {
Graph g = new Graph(4);
g.addEdge(0,1,2);
g.addEdge(0,2,3);
System.out.println(g.toString());
}
}
data.txt
--------------------------
destination, vertex, weight
0,1,2
0,2,1
0,3,6
1,0,2
1,4,4
1,5,8
2,0,1
2,6,2
3,0,6
3,7,7
4,1,4
4,7,5
5,1,8
5,7,3
6,2,2
6,7,4
7,3,7
7,6,4
7,4,5
7,5,3
Step by step
Solved in 2 steps
