Kaidul

Java - BFS

Oct 25th, 2012
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.84 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     static final int MAX = 1000;
  6.    
  7.     static List<Integer>[] adj = (List<Integer>[]) new ArrayList[MAX];
  8.  
  9.     /* নিচের মত হচ্ছেনা তাই উপরে arrayList এর array ব্যবহার করেছি । declaration এ কোন প্রবলেম নাই */
  10. //  static List<List<Integer>> adj = new ArrayList<List<Integer>>(MAX);
  11.    
  12.     static int[] distance = new int[MAX];
  13.     static int[] visited = new int[MAX];
  14.     static Queue<Integer> q = new LinkedList<Integer>();
  15.    
  16.     static void BFS(int source){
  17.         q.add(source);
  18.         distance[source] = 0;
  19.         visited[source] = 1;
  20.         System.out.println("Level " + distance[source] + " :  " + source);
  21.         while (!q.isEmpty()) {
  22.             int pop = q.peek();
  23.             int temp;
  24.             for (int i = 0; i < adj[pop].size(); i++) {
  25.                 temp = adj[pop].get(i);
  26.                 if (visited[temp] == 0) {
  27.                     distance[temp] = distance[pop] + 1;
  28.                     visited[temp] = 1;
  29.                     q.add(temp);
  30.                     System.out.println("Level " + distance[temp] + " :  " + temp);
  31.                 }
  32.             }
  33.             q.remove();
  34.         }
  35.     }
  36.  
  37.     public static void main(String[] args) {
  38.         int edge, u, v, source;
  39.         Scanner input = new Scanner(System.in);
  40.         edge = input.nextInt();
  41.         for (int i = 0; i < edge; i++) {
  42.             u = input.nextInt();
  43.             v = input.nextInt();
  44.             if (adj[v]==null) adj[v] = new ArrayList<Integer>();
  45.             adj[v].add(u);
  46.             if (adj[u]==null) adj[u] = new ArrayList<Integer>();
  47.             adj[u].add(v);
  48.  
  49.                         /* এইখানে প্রবলেম । রান করলে array out of bound exception দেখায় । stackOverFlow তে এইরকম একজন suggest করছিল */
  50.         //  adj.get(u).add(v);
  51.         //  adj.get(v).add(u);
  52.  
  53.         }
  54.         source = input.nextInt();
  55.        
  56.        Arrays.fill(visited, 0);
  57.        Arrays.fill(distance, 0);
  58.        
  59.        BFS(source);
  60.     }
  61.  
  62. }
Advertisement
Add Comment
Please, Sign In to add comment