We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Here is my Adjacency list based standard BFS solution (in Java 7) for your reference though I recommend reading only when you've spent a good amount of time on this problem.
publicstaticclassGraph{List<List<Integer>>adjLst;intsize;publicGraph(intsize){adjLst=newArrayList<>();this.size=size;while(size-->0)//Initialize the adjancency list.adjLst.add(newArrayList<Integer>());}publicvoidaddEdge(intfirst,intsecond){adjLst.get(first).add(second);adjLst.get(second).add(first);// For undirected graph, you gotta add edges from both sides.}publicint[]shortestReach(intstartId){// 0 indexedint[]distances=newint[size];Arrays.fill(distances,-1);// O(n) space.Queue<Integer>que=newLinkedList<>();que.add(startId);// Initialize queue.distances[startId]=0;HashSet<Integer>seen=newHashSet<>();//O(n) space. Could be further optimized. I leave it to you to optimize it.seen.add(startId);while(!que.isEmpty()){// Standard BFS loop.Integercurr=que.poll();for(intnode:adjLst.get(curr)){if(!seen.contains(node)){que.offer(node);// Right place to add the visited set.seen.add(node);// keep on increasing distance level by level.distances[node]=distances[curr]+6;}}}returndistances;}}
BFS: Shortest Reach in a Graph
You are viewing a single comment's thread. Return to all comments →
Here is my Adjacency list based standard BFS solution (in Java 7) for your reference though I recommend reading only when you've spent a good amount of time on this problem.