/* package whatever; // don't place package name! */
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
{
int[][] b = new int[5][5];
// b[0][0] = 0;
// b[2][3] = 1;
// b[3][1] = 1;
//
// b[1][4] = 1;
//b[2][1] = 1;
b[0][1] = 1;
b[1][2] = 1;
b[2][3] = 1;
b[3][4] = 1;
Graph g = new Graph(b);
//g.breadthFirstSearch(g.vertices[2], g.vertices[3]);
g.breadthFirstSearch(g.vertices[0], g.vertices[4]);
}
// your code goes here
// public int[][] makeMatrix(String )
static class Node{
int visited;
int value;
Node(int visited, int value){
this.visited = visited;
this.value = value;
}
public void assignData
(String data
){ this.data = data;
}
}
static class Graph{
int[][] adjacencyMatrix;
Node[] vertices;
int visitTruthVal;
Graph(int[][] adjacencyMatrix){
this.adjacencyMatrix = adjacencyMatrix;
visitTruthVal = 0;
createGraphVertices(adjacencyMatrix);
}
public void createGraphVertices(int[][] list){
vertices = new Node[list.length];
for(int i = 0; i < list.length; i++){
Node unit = new Node(0, i);
vertices[i] = unit;
}
}
public void depthFirstSearch(Node from, Node to){
from.visited = 1;
int n = from.value;
int key = to.value;
// System.out.println(from.value);
connection = DFS(from, to, connection);
if(connection.equals("-1")){
System.
out.
println(from.
value + ", -1, " + key
); }else{
connection = from.value + ", " + connection;
System.
out.
println(connection
); }
// System.out.println("-1");
int i = 0;
while(i < vertices.length){
vertices[i].visited = 0;
i++;
}
//+ SUBSSTRING RETURN( connection = connection + "," + i)
}
// bool t;
int i = 0;
//boolean connection;
from.visited = 1;
int n = from.value;
int key = to.value;
//String path = "";// = Integer.toString(key);
while(i < adjacencyMatrix.length){
// System.out.println(n + "+" + i);
// System.out.println(vertices[i].visited);//adjacencyMatrix[n][i]);
//vertices[]
if(vertices[i].visited == 0){
if(adjacencyMatrix[n][i] == 1){
//System.out.println("10");
path = DFS(vertices[i], to, "-1");
if(i == key){
// connection = true;
// visitTruthVal =
//if(vertices[i] == to){
// String path;
// int temp = i;
// for(int j = 0; j < vertices.length; j++){
// if(vertices[j].visited == 1 && adjacencyMatrix[temp][j] == 1){
// path = path + ", " + vertices[j].value;// + ", " //+ path;// System.out.println(", " + vertices[i].value);
// }
// if(vertices[j].visited == 1){
// temp = j;
// }
//temp = j;
//System.out.println()
// }
// System.out.println(path);
//System.out.println(j);////////////////
// return true;
// System.out.println(j);
//}
// System.out.println(", ");
// System.out.println(i);
return path;
}
if(path.equals("-1") != true){
// if(adjacencyMatrix[n][i] == 0){
// System.out.println("-1");
// }
// System.out.println(i);
path = i + ", " + path;
return path;
}
//connection = DFS(vertices[i], to, false);
// adjacencyMatrix[i][]
}
}
i++;
// if(n = key)
}
//System.out.println(", -1");
//System.out.println(", " + key);
return "-1";
}
public void breadthFirstSearch(Node from, Node to){//) throws IOException{ //visits each node in the tree, going from level to level and from left to right.
//FileWriter output = new FileWriter(outFile);
// BufferedWriter writer = new BufferedWriter(output);//creates writer to write the data values of visited nodes to the second command line specified output file
// node temp = root;
// node[] q = new node[128];
// Queue queue = new Queue(q);//creates queue to store visited nodes
// node child;
// writer.write("Num Name Dep/Prog.Year"); //reads headings to second output file
// writer.newLine();
// writer.write(temp.data);
// writer.newLine()
int n = from.value;
int key = to.value;
int size = vertices.length * vertices.length;
Node arr[] = new Node[size];
Queue q = new Queue(arr);
//int i = 0;
Node check = from;
q.enqueue(from);
//while(i < vertices.length){
//if()
// q.enqueue(vertices[i]);
while(q.isEmpty() == false){
//System.out.println("g");
check = q.dequeue();
check.visited = 1;
// int j = 0;
for(int j = 0; j < vertices.length; j++){
// System.out.println("dSS");
if(adjacencyMatrix[check.value][j] != 0){
if(vertices[j].visited != 1){
// vertices[j].visited = 1;
if(vertices[j] == to){
// String path;
// for(int i = 0; i < vertices.length; i++){
// if(vertices[i].visited == 1 && adjacencyMatrix[i][j] == 1){
// path = vertices[i].value + ", " + path;// System.out.println(", " + vertices[i].value);
// }
// //System.out.println()
// }
int temp = j;
for(int i = 0; i < vertices.length; i++){
if(vertices[i].visited == 1 && adjacencyMatrix[temp][i] == 1){
path = path + ", " + vertices[i].value;//vertices[i].value + ", " + path;// System.out.println(", " + vertices[i].value);
}
if(vertices[i].visited == 1){
temp = i;
}
//temp = j;
//System.out.println()
}
// path = from.value + ", " + path;
//System.out.println(j);
return;
// System.out.println(j);
}
q.enqueue(vertices[j]);
//check = q.dequeue;
//if()
}
}
}
}
int k = 0;
while(k < vertices.length){
vertices[k].visited = 0;
k++;
}
System.
out.
println(n
+ ", -1, " + path
);
}
/* do{ //nodes are visited until queue is empty
child = temp.leftPointer;
if(child != null){
queue.enqueue(child);
writer.write(child.data);
writer.newLine();
}
child = temp.rightPointer;
if(child != null){
queue.enqueue(child);
writer.write(child.data);
writer.newLine();
}
if(queue.isEmpty()){
break;
}
temp = queue.dequeue();
}while(true);
writer.close();
} */
class Queue{//queue(FIFO data structure) that holds array of nodes. Utilized to store references to nodes in breadthFirstTraversal()
Node[] arr;
int head = -1;
int tail = -1;
Queue(Node arr[]){
this.arr = arr;
}
public void enqueue(Node last){ //adds new node to back of queue
if (tail == -1 && head == -1){
arr[0] = last;
head = head + 1;
tail = tail + 1;
}else{
tail = tail + 1;
if(isFull() != true){
arr[tail] = last;
}
}
}
public Node dequeue(){ //removes and returns node at head of queue
Node temp = arr[head];
arr[head] = null;
head = head + 1;
return temp;
}
public boolean isEmpty(){
if(head == tail + 1){
return true;
}
return false;
}
public boolean isFull(){
if(tail == arr.length - 1){
return true;
}
return false;
}
}
}
}