fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. /* package whatever; // don't place package name! */
  4.  
  5. import java.util.*;
  6. import java.lang.*;
  7. import java.io.*;
  8.  
  9. /* Name of the class has to be "Main" only if the class is public. */
  10. class Ideone
  11. {
  12. 	public static void main (String[] args) throws java.lang.Exception
  13. 	{
  14. 		int[][] b = new int[5][5];
  15. 	//	b[0][0] = 0;
  16. 	//	b[2][3] = 1;
  17. 	//	b[3][1] = 1;
  18. 	//	
  19. 	//	b[1][4] = 1;
  20. 		//b[2][1] = 1;
  21. 		b[0][1] = 1;
  22. 		b[1][2] = 1;
  23. 		b[2][3] = 1;
  24. 		b[3][4] = 1;
  25.  
  26.  
  27. 		Graph g = new Graph(b);
  28.  
  29.  
  30. 		//g.breadthFirstSearch(g.vertices[2], g.vertices[3]);
  31. 		g.breadthFirstSearch(g.vertices[0], g.vertices[4]);
  32.  
  33.  
  34.  
  35.  
  36.  
  37. 	}
  38. 		// your code goes here
  39. //	public int[][] makeMatrix(String )
  40. 	static class Node{
  41. 		int visited;
  42. 		int value;
  43. 		String data;
  44. 		Node(int visited, int value){
  45. 			this.visited = visited;
  46. 			this.value = value;
  47. 		}
  48. 		public void assignData(String data){
  49. 			this.data = data;
  50. 		}
  51.  
  52. 	}
  53. 	static class Graph{
  54. 		int[][] adjacencyMatrix;
  55. 		Node[] vertices;
  56. 		int visitTruthVal;
  57. 		Graph(int[][] adjacencyMatrix){
  58. 			this.adjacencyMatrix = adjacencyMatrix;
  59. 			visitTruthVal = 0;
  60. 			createGraphVertices(adjacencyMatrix);
  61. 		}
  62. 		public void createGraphVertices(int[][] list){
  63. 			vertices = new Node[list.length];
  64. 			for(int i = 0; i < list.length; i++){
  65. 				Node unit = new Node(0, i);
  66. 				vertices[i] = unit;
  67. 			}
  68. 		}
  69. 		public void depthFirstSearch(Node from, Node to){
  70. 			from.visited = 1;
  71. 			int n = from.value;
  72. 			int key = to.value;
  73. 			String connection = "-1";
  74. 		//	System.out.println(from.value);
  75. 			connection = DFS(from, to, connection);
  76. 			if(connection.equals("-1")){
  77. 				System.out.println(from.value + ", -1, " + key);
  78. 			}else{
  79. 				connection = from.value + ", " + connection;
  80. 				System.out.println(connection);
  81. 			}
  82.  
  83. 		//	System.out.println("-1");
  84. 			int i = 0;
  85.  
  86. 			while(i < vertices.length){
  87. 				vertices[i].visited = 0;
  88. 				i++;
  89. 			}
  90. 			//+ SUBSSTRING RETURN( connection = connection + "," + i)
  91.  
  92.  
  93.  
  94.  
  95. 		}
  96. 	//		bool t;
  97.  
  98.  
  99. 		public String DFS(Node from, Node to, String path){
  100. 			int i = 0;
  101. 			//boolean connection;
  102. 			from.visited = 1;
  103. 			int n = from.value;
  104. 			int key = to.value;
  105. 			//String path = "";// = Integer.toString(key);
  106.  
  107. 			while(i < adjacencyMatrix.length){
  108. 			//	System.out.println(n + "+" + i);
  109. 			//	System.out.println(vertices[i].visited);//adjacencyMatrix[n][i]);
  110. 				//vertices[]
  111. 				if(vertices[i].visited == 0){
  112. 					if(adjacencyMatrix[n][i] == 1){
  113. 						//System.out.println("10");
  114. 						path  = DFS(vertices[i], to, "-1");
  115. 						if(i == key){
  116. 						//	connection = true;
  117. 						//	visitTruthVal = 
  118.  
  119.  
  120. 							//if(vertices[i] == to){
  121. 									//	String path;
  122. 									//	int temp = i;
  123. 									//	for(int j = 0; j < vertices.length; j++){
  124. 									//		if(vertices[j].visited == 1 && adjacencyMatrix[temp][j] == 1){
  125. 									//			path = path + ", " + vertices[j].value;// + ", " //+ path;//  System.out.println(", " + vertices[i].value);
  126. 									//		}
  127. 									//		if(vertices[j].visited == 1){
  128. 									//			temp = j;
  129. 									//		}
  130. 											//temp = j;
  131. 											//System.out.println()	
  132. 									//	}
  133.  
  134. 									//	System.out.println(path);
  135. 										//System.out.println(j);////////////////
  136. 									//	return true;
  137. 									//	System.out.println(j);
  138.  
  139. 							//}
  140.  
  141. 						//	System.out.println(", ");
  142. 						//	System.out.println(i);
  143. 							path = Integer.toString(i);
  144. 							return path;
  145. 						}
  146. 						if(path.equals("-1") != true){
  147.  
  148.  
  149. 					//	if(adjacencyMatrix[n][i] == 0){ 
  150. 					//		System.out.println("-1");
  151. 					//	}
  152. 						//	System.out.println(i);
  153. 							path = i + ", " + path;
  154. 							return path;
  155. 						}
  156. 						//connection = DFS(vertices[i], to, false);
  157. 					//	adjacencyMatrix[i][]
  158. 				}
  159.  
  160. 				}
  161. 				i++;
  162.  
  163. 			//	if(n = key)
  164.  
  165. 			}
  166. 			//System.out.println(", -1");
  167. 			//System.out.println(", " + key);
  168.  
  169. 			return "-1";
  170.  
  171. 		}
  172.  
  173.  
  174.  
  175.  
  176.  
  177.  
  178.  
  179. 		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.  
  180. //FileWriter output = new FileWriter(outFile); 
  181. //				BufferedWriter writer = new BufferedWriter(output);//creates writer to write the data values of visited nodes to the second command line specified output file 
  182. //				node temp = root;
  183. //				node[] q = new node[128];
  184. //				Queue queue = new Queue(q);//creates queue to store visited nodes
  185. //				node child;
  186.  
  187. //				writer.write("Num    Name                    Dep/Prog.Year"); //reads headings to second output file
  188. //				writer.newLine();				
  189. //				writer.write(temp.data);
  190. //				writer.newLine()
  191. 				int n = from.value;
  192. 				int key = to.value;
  193. 				String path = Integer.toString(key);
  194. 				int size = vertices.length * vertices.length;
  195. 				Node arr[] = new Node[size];
  196. 				Queue q = new Queue(arr);
  197. 				//int i = 0;
  198. 				Node check = from;
  199. 				q.enqueue(from);
  200. 				//while(i < vertices.length){
  201.  
  202. 					//if()
  203. 				//	q.enqueue(vertices[i]);
  204.  
  205.  
  206. 				while(q.isEmpty() == false){
  207. 						//System.out.println("g");
  208. 						check = q.dequeue();
  209. 						check.visited = 1;
  210. 					//	int j = 0;
  211. 						for(int j = 0; j < vertices.length; j++){
  212. 						//	System.out.println("dSS");
  213. 							if(adjacencyMatrix[check.value][j] != 0){
  214. 								if(vertices[j].visited != 1){
  215. 								//	vertices[j].visited = 1;
  216. 									if(vertices[j] == to){
  217. 									//	String path;
  218. 			//							for(int i = 0; i < vertices.length; i++){
  219. 			//								if(vertices[i].visited == 1 && adjacencyMatrix[i][j] == 1){
  220. 			//									path = vertices[i].value + ", " + path;//  System.out.println(", " + vertices[i].value);
  221. 			//								}
  222. 			//								//System.out.println()	
  223. 			//							}
  224. 										int temp = j;
  225. 										for(int i = 0; i < vertices.length; i++){
  226. 											if(vertices[i].visited == 1 && adjacencyMatrix[temp][i] == 1){
  227. 												path = path + ", " + vertices[i].value;//vertices[i].value + ", " + path;//  System.out.println(", " + vertices[i].value);
  228. 											}
  229. 											if(vertices[i].visited == 1){
  230. 												temp = i;
  231. 											}
  232. 											//temp = j;
  233. 											//System.out.println()	
  234. 										}
  235. 									//	path = from.value + ", " + path;
  236. 										System.out.println(path);
  237. 										//System.out.println(j);
  238. 										return;
  239. 									//	System.out.println(j);
  240.  
  241. 									}
  242. 									q.enqueue(vertices[j]);
  243. 									//check = q.dequeue;
  244. 									//if()
  245. 								}
  246. 							}
  247. 						}
  248. 					}
  249. 					int k = 0;
  250. 					while(k < vertices.length){
  251.  
  252. 						vertices[k].visited = 0;
  253. 						k++;
  254. 					}
  255. 					System.out.println(n + ", -1, " + path);
  256.  
  257.  
  258.  
  259. 					}
  260. 			/*	do{							//nodes are visited until queue is empty
  261.  
  262. 					child = temp.leftPointer;
  263.   					if(child != null){
  264. 						queue.enqueue(child);
  265. 						writer.write(child.data);
  266. 						writer.newLine();
  267. 					}
  268.  
  269. 					child = temp.rightPointer;
  270. 					if(child != null){
  271. 						queue.enqueue(child);
  272. 						writer.write(child.data);
  273. 						writer.newLine();
  274. 					}
  275.  
  276. 					if(queue.isEmpty()){
  277. 						break;
  278. 					}
  279. 					temp = queue.dequeue();
  280.   
  281. 				}while(true);
  282. 				writer.close(); 
  283. 		} */
  284.  
  285.  	class Queue{//queue(FIFO data structure) that holds array of nodes. Utilized to store references to nodes in breadthFirstTraversal()
  286. 		Node[] arr;
  287. 		int head = -1;
  288. 		int tail = -1;
  289.  
  290. 		Queue(Node arr[]){
  291. 			this.arr = arr;
  292.  
  293. 		}
  294. 		public void enqueue(Node last){ //adds new node to back of queue
  295. 			if (tail == -1 && head == -1){
  296. 				arr[0] = last;
  297. 				head = head + 1;
  298. 				tail = tail + 1;
  299. 			}else{
  300. 				tail = tail + 1;
  301. 				if(isFull() != true){
  302. 					arr[tail] = last;
  303. 				}
  304. 			}
  305. 		}
  306.  
  307. 		public Node dequeue(){ //removes and returns node at head of queue
  308. 			Node temp = arr[head];
  309. 			arr[head] = null;
  310. 			head = head + 1;
  311. 			return temp;
  312. 		}
  313.  
  314. 		public boolean isEmpty(){
  315. 			if(head == tail + 1){
  316. 				return true;
  317. 			}
  318. 			return false;
  319. 		}
  320.  
  321. 		public boolean isFull(){
  322. 			if(tail == arr.length - 1){
  323. 				return true;
  324. 			}
  325. 			return false;
  326. 		}
  327.  
  328. 	}
  329. 	}
  330.  
  331. } 
  332.  
Success #stdin #stdout 0.04s 4386816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4, 1, 2, 3
https://ideone.com/mVEgPt
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!