Breadth first search with BackTracking. - gists · GitHub

public class BFS{. public static Node[] prev;. public static Graph G;. public static void BFSWithBackTracking( ). {. if(G==null). return;. Skiptocontent Allgists BacktoGitHub Signin Signup Sign in Sign up {{message}} Instantlysharecode,notes,andsnippets. KodeSeeker/BFSWithBackTracking.java LastactiveAug29,2015 Star 0 Fork 0 Star Code Revisions 2 Embed Whatwouldyouliketodo? Embed Embedthisgistinyourwebsite. Share Copysharablelinkforthisgist. Clonevia HTTPS ClonewithGitorcheckoutwithSVNusingtherepository’swebaddress. LearnmoreaboutcloneURLs DownloadZIP BreadthfirstsearchwithBackTracking. Raw BFSWithBackTracking.java ThisfilecontainsbidirectionalUnicodetextthatmaybeinterpretedorcompileddifferentlythanwhatappearsbelow.Toreview,openthefileinaneditorthatrevealshiddenUnicodecharacters. LearnmoreaboutbidirectionalUnicodecharacters Showhiddencharacters publicclassBFS{ publicstaticNode[]prev; publicstaticGraphG; publicstaticvoidBFSWithBackTracking() { if(G==null) return; //classicBFSwithanarraytostorethepredecessorofeachnode Node[]prev=newNode[G.size()]; //QueueforBFS Queueq=newLinkedList(); Noderoot=G.root; if(root!=null) { q.push(root); prev[root]=-1; root.visited=true; } while(!q.isEmpty()) { Nodechild=q.poll(); for(Noden:child.getNeighbors()) { if(!n.isVisited()) { n.visited=true; prev[n]=child; q.push(n); } } } } //Methodtofindshortestpath //Assumepred[]ispopulatedwiththerightnodeinformation. publicintshortestPath(Nodev)//visthedestinationvertex { if(pred.length==0) return-1;//predhasntbeenpopulatedcorrectly. intdist=0; if(G.root==v) return0; while(pred[v]!=-1) { dist++; v=pred[v]; } returndist; } } Signupforfree tojointhisconversationonGitHub. Alreadyhaveanaccount? Signintocomment Youcan’tperformthatactionatthistime. Yousignedinwithanothertaborwindow.Reloadtorefreshyoursession. Yousignedoutinanothertaborwindow.Reloadtorefreshyoursession.