For my BFS in JAVA in How can I get the output of this to be correct when I put in this adjacency matrix.
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
The output should be:
The BFS traversal of the graph is
1 2 6 8 3 4 5 7
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
The number of connected components is : 1
My code is as follows
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class BFS
{
private Queue queue;
public BFS()
{
queue = new LinkedList();
}
public void bfs(int adjacency_matrix[][], int source)
{
int number_of_nodes = adjacency_matrix[source].length - 1;
int[] visited = new int[number_of_nodes + 1];
int i, element;
visited[source] = 1;
queue.add(source);
while (!queue.isEmpty())
{
element = queue.remove();
i = element;
System.out.print(i + "\t");
while (i <= number_of_nodes)
{
if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
{
queue.add(i);
visited[i] = 1;
}
i++;
}
}
}
public static void main(String... arg)
{
int number_no_nodes, source;
Scanner scanner = null;
try
{
System.out.println("Enter the number of nodes in the graph");
scanner = new Scanner(System.in);
number_no_nodes = scanner.nextInt();
int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1];
System.out.println("Enter the adjacency matrix");
for (int i = 1; i <= number_no_nodes; i++)
for (int j = 1; j <= number_no_nodes; j++)
adjacency_matrix[i][j] = scanner.nextInt();
System.out.println("Enter the source for the graph");
source = scanner.nextInt();
System.out.println("The BFS traversal of the graph is ");
BFS bfs = new BFS();
bfs.bfs(adjacency_matrix, source);
} catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input Format");
}
scanner.close();
}
}
I guess the correct output should be 1 2 5 6 7 3 8 4
I have modified the method bfs()
public void bfs(int adjacency_matrix[][], int source)
{
int number_of_nodes = adjacency_matrix[source].length - 1;
int[] visited = new int[number_of_nodes + 1];
int i, element;
visited[source] = 1;
queue.add(source);
while (!queue.isEmpty())
{
element = queue.remove();
i = 1;
System.out.print(element+ "\t");
while (i <= number_of_nodes)
{
if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
{
queue.add(i);
visited[i] = 1;
}
i++;
}
}
}
I have a Graph.java which I need to complete four methods in the java file: completeGraph(), valence(int vid), DFS(int start), and findPathBFS(int start, int end). I also have a JUnit test file GraphTest.java for you to check your code. Here is Graph.java: import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; /* Generic vertex class */ class Vertex<T> { public T data; public boolean visited; public Vertex() { data = null; visited = false; } public Vertex(T _data) { data =...
JAVA HELP: Directions Write a program that will create an array of random numbers and output the values. Then output the values in the array backwards. Here is my code, I am having a problem with the second method. import java.util.Scanner; import java.util.Random; public class ArrayBackwards { public static void main(String[] args) { genrate(); print(); } public static void generate() { Scanner scanner = new Scanner(System.in); System.out.println("Seed:"); int seed = scanner.nextInt(); System.out.println("Length"); int length = scanner.nextInt(); Random random...
/* Graph read from file, and represnted as adjacency list.
To implement DFS and BFS on the graph
*/
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <utility>
#include <unordered_map>
#include <set>
#include <queue>
using namespace std;
// Each vertex has an integer id.
typedef vector<vector<pair<int,int>>> adjlist; //
Pair: (head vertex, edge weight)
adjlist makeGraph(ifstream& ifs);
void printGraph(const adjlist& alist);
vector<int> BFS(const adjlist& alist, int source); //
Return vertices in BFS order
vector<int> DFS(const adjlist& alist, int source); //...
My Question is: I have to modify this program, even a small modification is fine. Can anyone give any suggestion and solution? Thanks in Advanced. import java.util.*; class arrayQueue { protected int Queue[]; protected int front, rear, size, len; public arrayQueue(int n) { size = n; len = 0; Queue = new int[size]; front = -1; rear = -1; } public boolean isEmpty() { return front == -1; } public boolean isFull() { return front == 0 && rear ==size...
draw a flew chart for this code // written by Alfuzan Mohammed package matreix; import java.util.Scanner; public class Matrix { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.print("Enter number of rows: first matrix "); int rows = scanner.nextInt(); System.out.print("Enter number of columns first matrix: "); int columns = scanner.nextInt(); System.out.print("Enter number of rows: seconed matrix "); int rowss = scanner.nextInt(); System.out.print("Enter number of columns seconed matrix:...
JAVA: How do I output all the data included for each employee? I can only get it to output the name, monthly salary and annual salary, but only from the Employee.java file, not Salesman.java or Executive.java. Employee.java package project1; public class Employee { private String name; private int monthlySalary; public Employee(String name, int monthlySalary) { this.name = name; this.monthlySalary = monthlySalary; } public int getAnnualSalary() { int totalPay = 0; totalPay = 12 * monthlySalary; return totalPay; } public String...
You will be implementing a Breadth-First Search (BFS) and a
Depth-First Search (DFS) algorithm on a graph stored as an
adjacency list. The AdjacencyList class inherits from the Graph
class shown below. class Graph { private: vector _distances; vector
_previous; public: Graph() { } virtual int vertices() const = 0;
virtual int edges() const = 0; virtual int distance(int) const = 0;
virtual void bfs(int) const = 0; virtual void dfs(int) const = 0;
virtual void display() const = 0;...
#include <iostream>
#include <queue>
using namespace std;
class Graph {
public:
Graph(int n);
~Graph();
void addEdge(int src, int tar);
void BFTraversal();
void DFTraversal();
void printVertices();
void printEdges();
private:
int vertexCount;
int edgeCount;
bool** adjMat;
void BFS(int n, bool marked[]);
void DFS(int n, bool marked[]);
};
Graph::Graph(int n=0) {
vertexCount = n;
edgeCount = 0;
if(n == 0)
adjMat = 0;
else {
adjMat = new bool* [n];
for(int i=0; i < n; i++)
adjMat[i] = new bool [n];
for(int i=0;...
(How do I remove the STATIC ArrayList from the public class Accounts, and move it to the MAIN?) import java.util.ArrayList; import java.util.Scanner; public class Accounts { static ArrayList<String> accounts = new ArrayList<>(); static Scanner scanner = new Scanner(System.in); public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int option = 0; do { System.out.println("0->quit\n1->add\n2->overwirte\n3->remove\n4->display"); System.out.println("Enter your option"); option = scanner.nextInt(); if (option == 0) { break; } else if (option == 1) { add(); } else...
I have a below codes with all details and need to answer this below question ONLY! How to explain below codes with the two properties of a Greedy algorithm - Optimal Substructure and the Greedy Property line by line? ====================== public class TeamFormation { private static ArrayList buildTeam(ArrayList team, int skill) { ArrayList newTeam = new ArrayList(); newTeam.add(skill); for (int player : team) { if (skill == (player + 1)) { newTeam.add(player); } } return newTeam; } private static boolean...