Advertisement
Guest User

Jana help

a guest
Feb 22nd, 2020
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.25 KB | None | 0 0
  1. /******************************************************************************
  2.  
  3. Online Java Compiler.
  4. Code, Compile, Run and Debug java program online.
  5. Write your code in this editor and press "Run" button to execute it.
  6.  
  7. *******************************************************************************/
  8. import java.util.*;
  9. import java.io.*;
  10.  
  11. class SLLNode<E> {
  12. protected E element;
  13. protected SLLNode<E> succ;
  14.  
  15. public SLLNode(E elem, SLLNode<E> succ) {
  16. this.element = elem;
  17. this.succ = succ;
  18. }
  19.  
  20. @Override
  21. public String toString() {
  22. return element.toString();
  23. }
  24. }
  25.  
  26. class GraphNode<E> {
  27. private int index;//index (reden broj) na temeto vo grafot
  28. private E info;
  29. private LinkedList<GraphNode<E>> neighbors;
  30.  
  31. public GraphNode(int index, E info) {
  32. this.index = index;
  33. this.info = info;
  34. neighbors = new LinkedList<GraphNode<E>>();
  35. }
  36.  
  37. boolean containsNeighbor(GraphNode<E> o){
  38. return neighbors.contains(o);
  39. }
  40.  
  41. void addNeighbor(GraphNode<E> o){
  42. neighbors.add(o);
  43. }
  44.  
  45. void removeNeighbor(GraphNode<E> o){
  46. if(neighbors.contains(o))
  47. neighbors.remove(o);
  48. }
  49.  
  50. @Override
  51. public String toString() {
  52. String ret= "INFO:"+info+" SOSEDI:";
  53. for(int i=0;i<neighbors.size();i++)
  54. ret+=neighbors.get(i).info+" ";
  55. return ret;
  56.  
  57. }
  58.  
  59. @Override
  60. public boolean equals(Object obj) {
  61. @SuppressWarnings("unchecked")
  62. GraphNode<E> pom = (GraphNode<E>)obj;
  63. return (pom.info.equals(this.info));
  64. }
  65.  
  66. public int getIndex() {
  67. return index;
  68. }
  69.  
  70. public void setIndex(int index) {
  71. this.index = index;
  72. }
  73.  
  74. public E getInfo() {
  75. return info;
  76. }
  77.  
  78. public void setInfo(E info) {
  79. this.info = info;
  80. }
  81.  
  82. public LinkedList<GraphNode<E>> getNeighbors() {
  83. return neighbors;
  84. }
  85.  
  86. public void setNeighbors(LinkedList<GraphNode<E>> neighbors) {
  87. this.neighbors = neighbors;
  88. }
  89.  
  90.  
  91.  
  92. }
  93.  
  94. class Graph<E> {
  95.  
  96. int num_nodes;
  97. GraphNode<E> adjList[];
  98.  
  99. @SuppressWarnings("unchecked")
  100. public Graph(int num_nodes, E[] list) {
  101. this.num_nodes = num_nodes;
  102. adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
  103. for (int i = 0; i < num_nodes; i++)
  104. adjList[i] = new GraphNode<E>(i, list[i]);
  105. }
  106.  
  107. @SuppressWarnings("unchecked")
  108. public Graph(int num_nodes) {
  109. this.num_nodes = num_nodes;
  110. adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
  111. }
  112.  
  113. int adjacent(int x, int y) {
  114. // proveruva dali ima vrska od jazelot so
  115. // indeks x do jazelot so indeks y
  116. return (adjList[x].containsNeighbor(adjList[y])) ? 1 : 0;
  117. }
  118.  
  119. void addEdge(int x, int y) {
  120. // dodava vrska od jazelot so indeks x do jazelot so indeks y
  121. if (!adjList[x].containsNeighbor(adjList[y])) {
  122. adjList[x].addNeighbor(adjList[y]);
  123. }
  124. }
  125.  
  126. void deleteEdge(int x, int y) {
  127. adjList[x].removeNeighbor(adjList[y]);
  128. }
  129.  
  130. void dfsSearch(int node) {
  131. boolean visited[] = new boolean[num_nodes];
  132. for (int i = 0; i < num_nodes; i++)
  133. visited[i] = false;
  134. dfsRecursive(node, visited);
  135. }
  136.  
  137. void dfsRecursive(int node, boolean visited[]) {
  138. visited[node] = true;
  139. System.out.println(node + ": " + adjList[node].getInfo());
  140.  
  141. for (int i = 0; i < adjList[node].getNeighbors().size(); i++) {
  142. GraphNode<E> pom = adjList[node].getNeighbors().get(i);
  143. if (!visited[pom.getIndex()])
  144. dfsRecursive(pom.getIndex(), visited);
  145. }
  146. }
  147.  
  148. void dfsNonrecursive(int node) {
  149. boolean visited[] = new boolean[num_nodes];
  150. for (int i = 0; i < num_nodes; i++)
  151. visited[i] = false;
  152. visited[node] = true;
  153. System.out.println(node+": " + adjList[node].getInfo());
  154. Stack<Integer> s = new Stack<Integer>();
  155. s.push(node);
  156.  
  157. GraphNode<E> pom;
  158.  
  159. while (!s.isEmpty()) {
  160. pom = adjList[s.peek()];
  161. GraphNode<E> tmp=null;
  162. for (int i = 0; i < pom.getNeighbors().size(); i++) {
  163. tmp = pom.getNeighbors().get(i);
  164. if (!visited[tmp.getIndex()])
  165. break;
  166. }
  167. if(tmp!=null && !visited[tmp.getIndex()]){
  168. visited[tmp.getIndex()] = true;
  169. System.out.println(tmp.getIndex() + ": " + tmp.getInfo());
  170. s.push(tmp.getIndex());
  171. }
  172. else
  173. s.pop();
  174. }
  175.  
  176. }
  177.  
  178. void bfs(int node){
  179. boolean visited[] = new boolean[num_nodes];
  180. for (int i = 0; i < num_nodes; i++)
  181. visited[i] = false;
  182. visited[node] = true;
  183. System.out.println(node+": " + adjList[node].getInfo());
  184. Queue<Integer> q = new LinkedQueue<Integer>();
  185. q.enqueue(node);
  186.  
  187. GraphNode<E> pom;
  188.  
  189. while(!q.isEmpty()){
  190. pom = adjList[q.dequeue()];
  191. GraphNode<E> tmp=null;
  192. for (int i = 0; i < pom.getNeighbors().size(); i++) {
  193. tmp = pom.getNeighbors().get(i);
  194. if (!visited[tmp.getIndex()]){
  195. visited[tmp.getIndex()] = true;
  196. System.out.println(tmp.getIndex()+": " + tmp.getInfo());
  197. q.enqueue(tmp.getIndex());
  198. }
  199. }
  200.  
  201.  
  202. }
  203.  
  204. }
  205.  
  206.  
  207. @Override
  208. public String toString() {
  209. String ret = new String();
  210. for (int i = 0; i < this.num_nodes; i++)
  211. ret += i + ": " + adjList[i] + "\n";
  212. return ret;
  213. }
  214.  
  215. }
  216.  
  217.  
  218. public class Main
  219. {
  220. public static void main(String[] args) {
  221. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  222.  
  223. int N = Integer.parseInt(br.readLine());
  224. String[] infos = br.readLine().split(" ");
  225.  
  226. Graph<String> g = new Graph(N, infos);
  227. }
  228. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement