Advertisement
Guest User

DFS/BFS quick attempt

a guest
Mar 11th, 2014
100
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public class GraphSearch {
  4.    
  5.     public static void main(String[] args){
  6.         int[][] graph = {{1,1,0,1,0},{0,0,0,0,1},{1,1,1,0,0},{1,1,1,1,0},{0,0,0,0,0}};
  7.        
  8.         /*
  9.         for (int i=0;i<3;i++)
  10.             for (int j=0;j<3;j++)
  11.                 System.out.println(graph[i][j]);
  12.         */
  13.        
  14.         //depth(graph,3);
  15.        
  16.         breadth(graph,0);
  17.     }
  18.    
  19.     public static void depth(int[][] graph, int root){
  20.        
  21.         // x is where it's going
  22.         // y is how you get there
  23.        
  24.         for (int i=0;i<graph.length;i++)
  25.             graph[i][root] = 0;             // set the return values to 0
  26.        
  27.         System.out.println(root);
  28.        
  29.         for (int i=0;i<graph.length;i++){
  30.                 if (graph[root][i]==1)
  31.                     depth(graph,i);    
  32.             }  
  33.     }
  34.    
  35.     // =======================================================
  36.    
  37.    
  38.     public static void breadth(int[][] graph, int root)
  39.     {
  40.         Queue<Integer> q = new LinkedList<Integer>();
  41.        
  42.         for (int i=0;i<graph.length;i++)
  43.             graph[i][root] = 0;         // set the return values to 0
  44.        
  45.         q.add(root);
  46.         System.out.println(root);
  47.  
  48.  
  49.         while(!q.isEmpty()){
  50.             root = q.remove();
  51.             for (int i=0;i<graph.length;i++) {
  52.                 if (graph[root][i]==1){
  53.                     System.out.println(i);
  54.                    
  55.                     for (int j=0;j<graph.length;j++)
  56.                         graph[j][i] = 0;    // set the return values to 0
  57.                    
  58.                     q.add(i);
  59.                 }
  60.             }      
  61.         }  
  62.     }
  63. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement