You are viewing a single comment's thread. Return to all comments →
public static List<Integer> bfs(int n, int m, List<List<Integer>> edges, int s) { Map<Integer,Integer> edgeMap = new HashMap<>(); List<Integer> res = new ArrayList<>(); int[] distance = new int[n]; for(int i = 0 ; i<n && i!=s-1;i++){ distance[i] = Integer.MAX_VALUE; } boolean[] visited = new boolean[n]; visited[s-1]=true; int[][] edgesMatrix = new int[n][n]; for(int i = 0;i<edges.size();i++){ edgesMatrix[edges.get(i).get(0)-1][edges.get(i).get(1)-1]=1; edgesMatrix[edges.get(i).get(1)-1][edges.get(i).get(0)-1]=1; } Queue<Integer> q = new ArrayDeque<Integer>(); q.add(s-1); while(!(q.isEmpty())){ int current= q.poll(); for(int i = 0 ;i<edgesMatrix.length;i++){ if(edgesMatrix[current][i]==1&& !visited[i]){ visited[i] = true; q.add(i); distance[i]=distance[current]+6; } } } System.out.println(Arrays.toString(distance)); for(int i = 0 ;i<distance.length;i++){ if(i!=s-1&&distance[i]!=0){ res.add(distance[i]= distance[i]==Integer.MAX_VALUE ?-1 : distance[i]); } if(i!=s-1&&distance[i]==0){ distance[i]=-1; res.add(distance[i]); } } return res; }
Breadth First Search: Shortest Reach
You are viewing a single comment's thread. Return to all comments →