Graph Traversal (Depth/Breadth First Search) - VisuAlgo

Given a graph, we can use the O(V+E) DFS (Depth-First Search) or BFS (Breadth-First Search) algorithm to traverse the graph and explore the features/properties ... 7 VisuAlgo.net / en zh id /dfsbfs GraphTraversal(DFS/BFS) ExplorationMode▿ e-LectureMode Login Profile Training LogOut slowfast 1.DFS&BFS 2.Visualization 3.SpecifyinganInputGraph 4.Recap    4-1.BinaryTreeTraversal-Source=Root    4-2.BinaryTreeTraversal-Pre-/In-/Post-order    4-3.TheAnswer    4-4.BinaryTreeTraversal-Acyclic    4-5.IssuesinGeneralGraph 5.DFS    5-1.Analogy    5-2.TryingAllOptions    5-3.AvoidingCycle    5-4.MemorizingthePath    5-5.Hands-onExample    5-6.O(V+E)TimeComplexity    5-7.O(V+E)atalltimes?    5-8.TheAnswer 6.BFS    6-1.Analogy    6-2.TryAll,AvoidCycle,MemorizePath    6-3.Hands-onExample    6-4.O(V+E)TimeComplexity 7.SimpleDFS/BFSApplications    7-1.ReachabilityTest    7-2.PrinttheTraversalPath    7-3.IdentifyingaConnectedComponent(CC)    7-4.CountingtheNumberof/LabelingtheCCs    7-5.Wait,WhatistheTimeComplexity?    7-6.TheAnswer    7-7.DetectingCycle-Part1    7-8.DetectingCycle-Part2    7-9.Hands-onExample(Detailed)    7-10.TopologicalSort-Definition    7-11.TopologicalSort 8.MoreAdvancedDFS/BFSApplications 9.BipartiteGraphChecker 10.FindCutVertices&Bridges 11.FindStronglyConnectedComponents 12.2-SATCheckerAlgorithm 13.WhichOneisBetter?    13-1.TheAnswer 14.Extras    14-1.OnlineQuiz    14-2.OnlineJudgeExercises    14-3.Discussion ✍ ✘ Givenagraph,wecanusetheO(V+E)DFS(Depth-FirstSearch)orBFS(Breadth-FirstSearch)algorithmtotraversethegraphandexplorethefeatures/propertiesofthegraph.Eachalgorithmhasitsowncharacteristics,features,andside-effectsthatwewillexploreinthisvisualization.ThisvisualizationisrichwithalotofDFSandBFSvariants(allruninO(V+E))suchas:TopologicalSortalgorithm(bothDFSandBFS/Kahn'salgorithmversion),BipartiteGraphCheckeralgorithm(bothDFSandBFSversion),CutVertex&Bridgefindingalgorithm,StronglyConnectedComponents(SCC)findingalgorithms(bothKosaraju'sandTarjan'sversion),and2-SATCheckeralgorithm. Remarks:Bydefault,weshowe-LectureModeforfirsttime(ornonlogged-in)visitor. IfyouareanNUSstudentandarepeatvisitor,pleaselogin. → 🕑 Whenthechosengraphtraversalalgorithmisrunning,theanimationwillbeshownhere.Weusevertex+edgecolor(thecolorschemewillbeelaboratedsoon)andoccasionallytheextratextunderthevertex(inredfont)tohighlightthechanges.Allgraphtraversalalgorithmsworkondirectedgraphs(thisisthedefaultsetting,whereeachedgehasanarrowtiptoindicateitsdirection)buttheBipartiteGraphCheckalgorithmandtheCutVertex&Bridgefindingalgorithmrequirestheundirectedgraphs(theconversionisdoneautomaticallybythisvisualization). Pro-tip1:Sinceyouarenotlogged-in,youmaybeafirsttimevisitor(ornotanNUSstudent)whoarenotawareofthefollowingkeyboardshortcutstonavigatethise-Lecturemode:[PageDown]/[PageUp]togotothenext/previousslide,respectively,(andifthedrop-downboxishighlighted,youcanalsouse[→or↓/←or↑]todothesame),and[Esc]totogglebetweenthise-Lecturemodeandexplorationmode. ← → 🕑 Therearetwodifferentsourcesforspecifyinganinputgraph:DrawGraph:Youcandrawanyunweighteddirectedgraphastheinputgraph(todrawbidirectionaledge(u,v),youcandrawtwodirectededgesu→vandv→u).ExampleGraphs:Youcanselectfromthelistofourselectedexamplegraphstogetyoustarted. Pro-tip2:Wedesignedthisvisualizationandthise-Lecturemodetolookgoodon1366x768resolutionorlarger(typicalmodernlaptopresolutionin2021).WerecommendusingGoogleChrometoaccessVisuAlgo.Gotofullscreenmode(F11)toenjoythissetup.However,youcanusezoom-in(Ctrl+)orzoom-out(Ctrl-)tocalibratethis. ← → 🕑 Ifyouarriveatthise-Lecturewithouthavingfirstexplore/mastertheconceptofBinaryHeapandespeciallyBinarySearchTree,wesuggestthatyouexplorethemfirst,astraversinga(Binary)Treestructureismuchsimplerthantraversingageneralgraph.Quiz:Minipre-requisitecheck.WhatarethePre-/In-/Post-ordertraversalofthebinarytreeshown(root=vertex0),leftandrightchildareasdrawn?Post=1,3,4,2,0Pre=0,2,4,3,1Pre=0,1,2,3,4In=4,2,3,0,1Post=4,3,2,1,0In=1,0,3,2,4Submit Pro-tip3:OtherthanusingthetypicalmediaUIatthebottomofthepage,youcanalsocontroltheanimationplaybackusingkeyboardshortcuts(inExplorationMode):Spacebartoplay/pause/replaytheanimation,←/→tosteptheanimationbackwards/forwards,respectively,and-/+todecrease/increasetheanimationspeed,respectively. ← → 🕑 Wenormallystartfromthemostimportantvertexofa(binary)tree:Therootvertex.Ifthegiventreeisnot'rooted'(seetheexamplepicture),wecanpickanyonevertex(forexample,vertex0intheexamplepicture)anddesignateitastheroot.Ifweimaginethatalledgesarestringsofsimilarlength,thenafter"virtuallypullingthedesignatedrootupwards"andletgravitypullstherestdownwards,wehavearooteddirected(downwards)tree—seethenextslide.PS:Technically,thistransformationisdonebyrunningDFS(0)thatwewillexploresoon. ← → 🕑 Inabinarytree,weonlyhaveuptotwoneighboringchoices:Fromthecurrentvertex,wecangototheleftsubtreefirstorgototherightsubtreefirst.Wealsohaveoptiontovisitthecurrentvertexbeforeoraftervisitingoneofthe(orboth)subtree(s).Thisgivesrisetotheclassics:pre-order(visitcurrentvertex,visititsleftsubtree,visititsrightsubtree),in-order(left,current,right),andpost-order(left,right,current)traversals.Discussion:Doyounoticethattherearethreeotherpossiblebinarytreetraversalcombinations?Whatarethey? ← → 🕑 Thecontentofthisinterestingslide(theansweroftheusuallyintriguingdiscussionpointfromtheearlierslide)ishiddenandonlyavailableforlegitimateCSlecturerworldwide.ThismechanismisusedinthevariousflippedclassroomsinNUS. IfyouarereallyaCSlecturer(oranITteacher)(outsideofNUS)andareinterestedtoknowtheanswers,pleasedropanemailtostevenhalimatgmaildotcom(showyourUniversitystaffprofile/relevantprooftoSteven)forSteventomanuallyactivatethisCSlecturer-onlyfeatureforyou. FAQ:ThisfeaturewillNOTbegiventoanyoneelsewhoisnotaCSlecturer. ← → 🕑 Inabinarytree,orinatreestructureingeneral,thereisno(non-trivial)cycleinvolving3ormoredistinctverticestoworryabout(wedonotconsiderthetrivialcycleinvolvingbi-directionaledgeswhichcanbetakencareofeasily—seethreeslidesearlier). ← → 🕑 Ingeneralgraph,wedonothavethenotionofrootvertex.Instead,weneedtopickonedistinguishedvertextobethestartingpointofthetraversal,i.e.thesourcevertexs.Wealsohave0,1,...,kneighborsofavertexinsteadofjust≤2.Wemay(oractuallyverylikely)havecycle(s)inourgeneralgraphinsteadofacyclictree,beitthetrivialonelikeu→v→uorthenon-trivialonelikea→b→c→a.Butfretnot,graphtraversalisaneasyproblemwithtwoclassicalgorithms:DFSandBFS. ← → 🕑 OneofthemostbasicgraphtraversalalgorithmistheO(V+E)Depth-FirstSearch(DFS).DFStakesoneinputparameter:Thesourcevertexs.DFSisoneofthemostfundamentalgraphalgorithm,sopleasespendtimetounderstandthekeystepsofthisalgorithm. ← → 🕑 TheclosestanalogyofthebehaviorofDFSistoimagineamazewithonlyoneentranceandoneexit.Youareattheentranceandwanttoexplorethemazetoreachtheexit.Obviouslyyoucannotsplityourselfintomorethanone.Askthesereflectivequestionsbeforecontinuing:Whatwillyoudoiftherearebranchingoptionsinfrontofyou?Howtoavoidgoingincycle?Howtomarkyourownpath?Hint:Youneedachalk,stones(oranyothermarker)anda(long)string. ← → 🕑 Asitnameimplies,DFSstartsfromadistinguishedsourcevertexsandusesrecursion(animplicitstack)toorderthevisitationsequenceasdeepaspossiblebeforebacktracking.IfDFSisatavertexuandithasXneighbors,itwillpickthefirstneighborV1(usuallythevertexwiththelowestvertexnumber),recursivelyexploreallreachableverticesfromvertexV1,andeventuallybacktracktovertexu.DFSwillthendothesamefortheotherneighborsuntilitfinishesexploringthelastneighborVXanditsreachablevertices.ThiswordyexplanationwillbeclearerwithDFSanimationlater. ← → 🕑 Ifthegraphiscyclic,theprevious'try-all'strategymayleadDFStorunincycle.SothebasicformofDFSusesanarraystatus[u]ofsizeVverticestodecidebetweenbinaryconditions:Whethervertexuhasbeenvisitedorunvisited.Onlyifvertexuisstillunvisited,thenDFScanvisitvertexu.WhenDFSrunsoutofoption,itbacktracktopreviousvertex(p[u],seethenextslide)astherecursionunwinds. ← → 🕑 DFSusesanotherarrayp[u]ofsizeVverticestoremembertheparent/predecessor/previousofeachvertexualongtheDFStraversalpath.Thepredecessorofthesourcevertex,i.e.,p[s]issetto-1tosaythatthesourcevertexhasnopredecessor(asthelowestvertexnumberisvertex0).ThesequenceofverticesfromavertexuthatisreachablefromthesourcevertexsbacktosformstheDFSspanningtree.Wecolorthesetreeedgeswithredcolor. ← → 🕑 Fornow,ignoretheextrastatus[u]=exploredinthedisplayedpseudocodeandthepresenceofblueandgreyedgesinthevisualization(tobeexplainedsoon).Withoutfurtherado,let'sexecuteDFS(0)onthedefaultexamplegraphforthise-Lecture(CP3Figure4.1).RecapDFSExampleThebasicversionofDFSpresentedsofarisalreadyenoughformostsimplecases. ← → 🕑 ThetimecomplexityofDFSisO(V+E)because:EachvertexisonlyvisitedonceduetothefactthatDFSwillonlyrecursivelyexploreavertexuifstatus[u]=unvisited—O(V)Everytimeavertexisvisited,allitskneighborsareexploredandthereforeafterallverticesarevisited,wehaveexaminedallEedges—(O(E)asthetotalnumberofneighborsofeachvertexequalstoE). ← → 🕑 TheO(V+E)timecomplexityofDFSonlyachievableifwecanvisitallkneighboringverticesofavertexinO(k)time.Quiz:Whichunderlyinggraphdatastructuresupportthatoperation?AdjacencyMatrixAdjacencyListEdgeListSubmitDiscussion:Why? ← → 🕑 Thecontentofthisinterestingslide(theansweroftheusuallyintriguingdiscussionpointfromtheearlierslide)ishiddenandonlyavailableforlegitimateCSlecturerworldwide.ThismechanismisusedinthevariousflippedclassroomsinNUS. IfyouarereallyaCSlecturer(oranITteacher)(outsideofNUS)andareinterestedtoknowtheanswers,pleasedropanemailtostevenhalimatgmaildotcom(showyourUniversitystaffprofile/relevantprooftoSteven)forSteventomanuallyactivatethisCSlecturer-onlyfeatureforyou. FAQ:ThisfeaturewillNOTbegiventoanyoneelsewhoisnotaCSlecturer. ← → 🕑 AnotherbasicgraphtraversalalgorithmistheO(V+E)Breadth-FirstSearch(BFS).AswithDFS,BFSalsotakesoneinputparameter:Thesourcevertexs.BothDFSandBFShavetheirownstrengthsandweaknesses.Itisimportanttolearnbothandapplythecorrectgraphtraversalalgorithmforthecorrectsituation. ← → 🕑 Imagineastillbodyofwaterandthenyouthrowastoneintoit.ThefirstlocationwherethestonehitsthewatersurfaceisthepositionofthesourcevertexandthesubsequentrippleeffectacrossthewatersurfaceisliketheBFStraversalpattern. ← → 🕑 BFSisverysimilarwithDFSthathavebeendiscussedearlier,butwithsomedifferences.BFSstartsfromasourcevertexsbutitusesaqueuetoorderthevisitationsequenceasbreadthaspossiblebeforegoingdeeper.BFSalsousesaBooleanarrayofsizeVverticestodistinguishbetweentwostates:visitedandunvisitedvertices(wewillnotuseBFStodetectbackedge(s)aswithDFS).Inthisvisualization,wealsoshowthatstartingfromthesamesourcevertexsinanunweightedgraph,BFSspanningtreeofthegraphequalstoitsSSSPspanningtree. ← → 🕑 Withoutfurtherado,let'sexecuteBFS(5)onthedefaultexamplegraphforthise-Lecture(CP3Figure4.3).RecapBFSExample.NoticetheBreadth-first explorationduetotheusageofFIFOdatastructure:Queue? ← → 🕑 ThetimecomplexityofBFSisO(V+E)because:Eachvertexisonlyvisitedonceasitcanonlyenterthequeueonce—O(V)Everytimeavertexisdequeuedfromthequeue,allitskneighborsareexploredandthereforeafterallverticesarevisited,wehaveexaminedallEedges—(O(E)asthetotalnumberofneighborsofeachvertexequalstoE).AswithDFS,thisO(V+E)timecomplexityisonlypossibleifweuseAdjacencyListgraphdatastructure—samereasonaswithDFSanalysis. ← → 🕑 Sofar,wecanuseDFS/BFStosolveafewgraphtraversalproblemvariants:Reachabilitytest,Actuallyprintingthetraversalpath,Identifying/Counting/LabelingConnectedComponents(CCs)ofundirectedgraphs,Detectingifagraphiscyclic,TopologicalSort(onlyonDAGs),Formostdatastructuresandalgorithmscourses,theapplicationsofDFS/BFSareuptothesefewbasiconesonly,althoughDFS/BFScandomuchmore... ← → 🕑 Ifyouareaskedtotestwhetheravertexsanda(different)vertextinagrapharereachable,i.e.,connecteddirectly(viaadirectedge)orindirectly(viaasimple,noncyclic,path),youcancalltheO(V+E)DFS(s)(orBFS(s))andcheckifstatus[t]=visited.Example1:s=0andt=4,runDFS(0)andnoticethatstatus[4]=visited.Example2:s=0andt=7,runDFS(0)andnoticethatstatus[7]=unvisited. ← → 🕑 Rememberthatwesetp[v]=ueverytimewemanagetoextendDFS/BFStraversalfromvertexutovertexv—atreeedgeintheDFS/BFSspanningtree.Thus,wecanusefollowingsimplerecursivefunctiontoprintoutthepathstoredinarrayp.Possiblefollow-updiscussion:Canyouwritethisiniterativeform?(trivial)methodbacktrack(u)if(u==-1)stopbacktrack(p[u]);outputvertexuToprintoutthepathfromasourcevertexstoatargetvertextinagraph,youcancallO(V+E)DFS(s)(orBFS(s))andthenO(V)backtrack(t).Example:s=0andt=4,youcancallDFS(0)andthenbacktrack(4).Elaborate ← → 🕑 Wecanenumerateallverticesthatarereachablefromavertexsinanundirectedgraph(astheexamplegraphshownabove)bysimplycallingO(V+E)DFS(s)(orBFS(s))andenumerateallvertexvthathasstatus[v]=visited.Example:s=0,runDFS(0)andnoticethatstatus[{0,1,2,3,4}]=visitedsotheyareallreachableverticesfromvertex0,i.e.,theyformoneConnectedComponent(CC). ← → 🕑 Wecanusethefollowingpseudo-codetocountthenumberofCCs:CC=0foralluinV,setstatus[u]=unvisitedforalluinVif(status[u]==unvisited)++CC//wecanuseCCcounternumberastheCClabelDFS(u)//orBFS(u),thatwillflagitsmembersasvisitedoutputCC//theansweris3fortheexamplegraphabove,i.e.//CC0={0,1,2,3,4},CC1={5},CC2={6,7,8}YoucanmodifytheDFS(u)/BFS(u)codeabitifyouwanttouseittolabeleachCCwiththeidentifierofthatCC. ← → 🕑 Quiz:WhatisthetimecomplexityofCountingtheNumberofCCsalgorithm?Trickquestion,theanswerisnoneoftheabove,itisO(_____)ItisstillO(V+E)CallingO(V+E)DFS/BFSVtimes,soO(V*(V+E))=O(V^2+VE)SubmitDiscussion:Why? ← → 🕑 Thecontentofthisinterestingslide(theansweroftheusuallyintriguingdiscussionpointfromtheearlierslide)ishiddenandonlyavailableforlegitimateCSlecturerworldwide.ThismechanismisusedinthevariousflippedclassroomsinNUS. IfyouarereallyaCSlecturer(oranITteacher)(outsideofNUS)andareinterestedtoknowtheanswers,pleasedropanemailtostevenhalimatgmaildotcom(showyourUniversitystaffprofile/relevantprooftoSteven)forSteventomanuallyactivatethisCSlecturer-onlyfeatureforyou. FAQ:ThisfeaturewillNOTbegiventoanyoneelsewhoisnotaCSlecturer. ← → 🕑 WecanactuallyaugmentthebasicDFSfurthertogivemoreinsightsabouttheunderlyinggraph.Inthisvisualization,weusebluecolortohighlightbackedge(s)oftheDFSspanningtree.Thepresenceofatleastonebackedgeshowsthatthetraversedgraph(component)iscyclicwhileitsabsenceshowsthatatleastthecomponentconnectedtothesourcevertexofthetraversedgraphisacyclic. ← → 🕑 Backedgecanbedetectedbymodifyingarraystatus[u]torecordthreedifferentstates:unvisited:sameasearlier,DFShasnotreachvertexubefore,explored:DFShasvisitedvertexu,butatleastoneneighborofvertexuhasnotbeenvisitedyet(DFSwillgodepth-firsttothatneighborfirst),visited:nowstrongerdefinition:allneighborsofvertexuhavealsobeenvisitedandDFSisabouttobacktrackfromvertexutovertexp[u].IfDFSisnowatvertexxandexploreedgex→yandencounterstatus[y]=explored,wecandeclarex→yisabackedge(acycleisfoundaswewerepreviouslyatvertexy(hencestatus[y]=explored),godeeptoneighborofyandsoon,butwearenowatvertexxthatisreachablefromybutvertexxleadsbacktovertexy). ← → 🕑 Theedgesinthegraphthatarenottreeedge(s)norbackedge(s)arecoloredgrey.Theyarecalledforwardorcrossedge(s)andcurrentlyhavelimiteduse(notelaborated).NowtryDFS(0)ontheexamplegraphabovewiththisnewunderstanding,especiallyaboutthe3possiblestatusofavertex(unvisited/normalblackcircle,explored/bluecircle,visited/orangecircle)andbackedge.Edge2→1willbediscoveredasabackedgeasitispartofcycle1→3→2→1(asvertex2is`explored'tovertex1whichiscurrently`explored')(similarlywithEdge6→4aspartofcycle4→5→7→6→4).Notethatifedges2→1and6→4arereversedto1→2and4→6,thenthegraphiscorrectlyclassifiedasacyclicasedge3→2and4→6gofrom`explored'to`fullyvisited'.Ifweonlyusebinarystates:`unvisited'vs`visited',wecannotdistinguishthesetwocases. ← → 🕑 ThereisanotherDFS(andalsoBFS)applicationthatcanbetreatedas'simple':PerformingTopologicalSort(ing)ofaDirectedAcyclicGraph(DAG)—seeexampleabove.TopologicalsortofaDAGisalinearorderingoftheDAG'sverticesinwhicheachvertexcomesbeforeallverticestowhichithasoutboundedges.EveryDAG(canbecheckedwithDFSearlier)hasatleastonebutpossiblymoretopologicalsorts/ordering.Oneofthemainpurposeof(atleastone)topologicalsortofaDAGisforDynamicProgramming(DP)technique.Forexample,thistopologicalsortingprocessisusedinternallyinDPsolutionforSSSPonDAG. ← → 🕑 WecanuseeithertheO(V+E)DFSorBFStoperformTopologicalSortofaDirectedAcyclicGraph(DAG).TheDFSversionrequiresjustoneadditionallinecomparedtothenormalDFSandisbasicallythepost-ordertraversalofthegraph.TryToposort(DFS)ontheexampleDAG.TheBFSversionisbasedontheideaofverticeswithoutincomingedgeandisalsocalledasKahn'salgorithm.TryToposort(BFS/Kahn's)ontheexampleDAG. ← → 🕑 Asofnow,youhaveseenDFS/BFSandwhatitcansolve(withjustminortweaks).Thereareafewmoreadvancedapplicationsthatrequiremoretweaksandwewillletadvancedstudentstoexplorethemontheirown:BipartiteGraphChecker(DFSandBFSvariants),FindingArticulationPoints(CutVertices)andBridgesofanUndirectedGraph(DFSonly),FindingStronglyConnectedComponents(SCCs)ofaDirectedGraph(Tarjan'sandKosaraju'salgorithms),and2-SAT(isfiability)Checkeralgorithms.Advertisement:ThedetailsarewritteninCompetitiveProgrammingbook. ← → 🕑 WecanusetheO(V+E)DFSorBFS(theyworksimilarly)tocheckifagivengraphisaBipartiteGraphbygivingalternatingcolor(orangeversusblueinthisvisualization)betweenneighboringverticesandreport'nonbipartite'ifweendsupassigningsamecolortotwoadjacentverticesor'bipartite'ifitispossibletodosuch'2-coloring'process.TryDFS_CheckerorBFS_CheckerontheexampleBipartiteGraph.BipartiteGraphshaveusefulapplicationsin(Bipartite)GraphMatchingproblem.NotethatBipartiteGraphsareusuallyonlydefinedforundirectedgraphssothisvisualizationwillconvertdirectedinputgraphsintoitsundirectedversionautomaticallybeforecontinuing.Thisactionisirreversibleandyoumayhavetoredrawthedirectedinputgraphagainforotherpurposes. ← → 🕑 Wecanmodify(butunfortunately,nottrivially)theO(V+E)DFSalgorithmintoanalgorithmtofindCutVertices&BridgesofanUndirectedGraph.ACutVertex,oranArticulationPoint,isavertexofanundirectedgraphwhichremovaldisconnectsthegraph.Similarly,abridgeisanedgeofanundirectedgraphwhichremovaldisconnectsthegraph.NotethatthisalgorithmforfindingCutVertices&Bridgesonlyworksforundirectedgraphssothisvisualizationwillconvertdirectedinputgraphsintoitsundirectedversionautomaticallybeforecontinuing.Thisactionisirreversibleandyoumayhavetoredrawthedirectedinputgraphagainforotherpurposes.YoucantrytoFindCutVertices&Bridgesontheexamplegraphabove. ← → 🕑 Wecanmodify(butunfortunately,nottrivially)theO(V+E)DFSalgorithmintoanalgorithmtofindStronglyConnectedComponents(SCCs)ofaDirectedGraphG.AnSCCofadirectedgraphGaisdefinedasasubgraphSofGsuchthatforanytwoverticesuandvinS,vertexucanreachvertexvdirectlyorviaapath,andvertexvcanalsoreachvertexubackdirectlyorviaapath.TherearetwoknownalgorithmsforfindingSCCsofaDirectedGraph:Kosaraju'sandTarjan's.Bothofthemareavailableinthisvisualization.TryKosaraju'sAlgorithmand/orTarjan'sAlgorithmontheexampledirectedgraphabove. ← → 🕑 Wealsohavethe2-SATCheckeralgorithm.Givena2-Satisfiability(2-SAT)instanceintheformofconjuctionofclauses:(clause1)^(clause2)^...^(clausen)andeachclauseisinformofdisjunctionofuptotwovariables(varavvarb),determineifwecanassignTrue/Falsevaluestothesevariablessothattheentire2-SATinstanceisevaluatedtobetrue,i.e.satisfiable.Itturnsoutthateachclause(avb)canbeturnedintofourverticesa,nota,b,andnotbwithtwoedges:(nota→b)and(notb→a).ThuswehaveaDirectedGraph.IfthereisatleastonevariableanditsnegationinsideanSCCofsuchgraph,weknowthatitisimpossibletosatisfythe2-SATinstance.Aftersuchdirectedgraphmodeling,wecanrunanSCCfindingalgorithm(Kosaraju'sorTarjan'salgorithm)todeterminethesatisfiabilityofthe2-SATinstance. ← → 🕑 Quiz:WhichGraphTraversalAlgorithmisBetter?AlwaysDFSItDependsontheSituationBothareEquallyGoodAlwaysBFSSubmitDiscussion:Why? ← → 🕑 Thecontentofthisinterestingslide(theansweroftheusuallyintriguingdiscussionpointfromtheearlierslide)ishiddenandonlyavailableforlegitimateCSlecturerworldwide.ThismechanismisusedinthevariousflippedclassroomsinNUS. IfyouarereallyaCSlecturer(oranITteacher)(outsideofNUS)andareinterestedtoknowtheanswers,pleasedropanemailtostevenhalimatgmaildotcom(showyourUniversitystaffprofile/relevantprooftoSteven)forSteventomanuallyactivatethisCSlecturer-onlyfeatureforyou. FAQ:ThisfeaturewillNOTbegiventoanyoneelsewhoisnotaCSlecturer. ← → 🕑 TherearelotsofthingsthatwecanstilldowithjustDFSand/orBFS... ← → 🕑 Thereareinterestingquestionsaboutthesetwographtraversalalgorithms:DFS+BFSandvariantsofgraphtraversalproblems,pleasepracticeonGraphTraversaltrainingmodule(nologinisrequired,butshortandofmediumdifficultysettingonly).However,forregisteredusers,youshouldloginandthengototheMainTrainingPagetoofficiallyclearthismoduleandsuchachievementwillberecordedinyouruseraccount. ← → 🕑 WealsohaveafewprogrammingproblemsthatsomewhatrequirestheusageofDFSand/orBFS:Kattis-reachableroadsandKattis-breakingbad.Trytosolvethemandthentrythemanymoreinterestingtwists/variantsofthissimplegraphtraversalproblemand/oralgorithm.Youareallowedtouse/modifyourimplementationcodeforDFS/BFSAlgorithms:dfs_cc.cpp/bfs.cppdfs_cc.java/bfs.javadfs_cc.py/bfs.pydfs_cc.ml/bfs.ml ← → 🕑 Thecontentofthisinterestingslide(theansweroftheusuallyintriguingdiscussionpointfromtheearlierslide)ishiddenandonlyavailableforlegitimateCSlecturerworldwide.ThismechanismisusedinthevariousflippedclassroomsinNUS. IfyouarereallyaCSlecturer(oranITteacher)(outsideofNUS)andareinterestedtoknowtheanswers,pleasedropanemailtostevenhalimatgmaildotcom(showyourUniversitystaffprofile/relevantprooftoSteven)forSteventomanuallyactivatethisCSlecturer-onlyfeatureforyou. FAQ:ThisfeaturewillNOTbegiventoanyoneelsewhoisnotaCSlecturer. Youhavereachedthelastslide.Returnto'ExplorationMode'tostartexploring! Notethatifyounoticeanybuginthisvisualizationorifyouwanttorequestforanewvisualizationfeature,donothesitatetodropanemailtotheprojectleader:DrStevenHalimviahisemailaddress:stevenhalimatgmaildotcom. ← 🕑 XClose DrawGraph ExampleGraphs Depth-FirstSearch Breadth-FirstSearch TopologicalSort BipartiteGraphCheck CutVertex&Bridge SCCAlgorithms 2-SATChecker > CP34.1 CP34.3 CP34.4DAG CP34.9 CP34.17DAG CP34.18DAG,Bipartite CP34.19Bipartite s= Go s= Go DFSversion BFSversion(Kahn'salgorithm) DFSversion BFSversion Kosaraju'sAlgorithm Tarjan'sAlgorithm Numberofclauses= Numberofvariables= GO About Team Termsofuse PrivacyPolicy About✕ VisuAlgowasconceptualisedin2011byDrStevenHalimasatooltohelphisstudentsbetterunderstanddatastructuresandalgorithms,byallowingthemtolearnthebasicsontheirownandattheirownpace.VisuAlgocontainsmanyadvancedalgorithmsthatarediscussedinDrStevenHalim'sbook('CompetitiveProgramming',co-authoredwithhisbrotherDrFelixHalim)andbeyond.Today,afewoftheseadvancedalgorithmsvisualization/animationcanonlybefoundinVisuAlgo.ThoughspecificallydesignedforNationalUniversityofSingapore(NUS)studentstakingvariousdatastructureandalgorithmclasses(e.g.,CS1010/equivalent,CS2040/equivalent,CS3230,CS3233,andCS4234),asadvocatorsofonlinelearning,wehopethatcuriousmindsaroundtheworldwillfindthesevisualizationsusefultoo.VisuAlgoisnotdesignedtoworkwellonsmalltouchscreens(e.g.,smartphones)fromtheoutsetduetotheneedtocaterformanycomplexalgorithmvisualizationsthatrequirelotsofpixelsandclick-and-draggesturesforinteraction.Theminimumscreenresolutionforarespectableuserexperienceis1024x768andonlythelandingpageisrelativelymobile-friendly.However,wearecurrentlyexperimentingwithamobile(lite)versionofVisuAlgotobereadybyApril2022.VisuAlgoisanongoingprojectandmorecomplexvisualizationsarestillbeingdeveloped.Themostexcitingdevelopmentistheautomatedquestiongeneratorandverifier(theonlinequizsystem)thatallowsstudentstotesttheirknowledgeofbasicdatastructuresandalgorithms.Thequestionsarerandomlygeneratedviasomerulesandstudents'answersareinstantlyandautomaticallygradeduponsubmissiontoourgradingserver.Thisonlinequizsystem,whenitisadoptedbymoreCSinstructorsworldwide,shouldtechnicallyeliminatemanualbasicdatastructureandalgorithmquestionsfromtypicalComputerScienceexaminationsinmanyUniversities.Bysettingasmall(butnon-zero)weightageonpassingtheonlinequiz,aCSinstructorcan(significantly)increasehis/herstudentsmasteryonthesebasicquestionsasthestudentshavevirtuallyinfinitenumberoftrainingquestionsthatcanbeverifiedinstantlybeforetheytaketheonlinequiz.Thetrainingmodecurrentlycontainsquestionsfor12visualizationmodules.Wewillsoonaddtheremaining12visualizationmodulessothateveryvisualizationmoduleinVisuAlgohaveonlinequizcomponent.WehavetranslatedVisuAlgopagesintothreemainlanguages:English,Chinese,andIndonesian.Currently,wehavealsowrittenpublicnotesaboutVisuAlgoinvariouslanguages: id, kr, vn, th. Team✕ ProjectLeader&Advisor(Jul2011-present) DrStevenHalim,SeniorLecturer,SchoolofComputing(SoC),NationalUniversityofSingapore(NUS) DrFelixHalim,SeniorSoftwareEngineer,Google(MountainView) UndergraduateStudentResearchers1(Jul2011-Apr2012) KohZiChun,VictorLohBoHuai FinalYearProject/UROPstudents1(Jul2012-Dec2013) PhanThiQuynhTrang,PeterPhandi,AlbertMillardoTjindradinata,NguyenHoangDuy FinalYearProject/UROPstudents2(Jun2013-Apr2014) RoseMarieTanZhaoYun,IvanReinaldo UndergraduateStudentResearchers2(May2014-Jul2014) JonathanIrvinGunawan,NathanAzaria,IanLeowTzeWei,NguyenVietDung,NguyenKhacTung,StevenKesterYuwono,CaoShengze,MohanJishnu FinalYearProject/UROPstudents3(Jun2014-Apr2015) ErinTeoYiLing,WangZi FinalYearProject/UROPstudents4(Jun2016-Dec2017) TruongNgocKhanh,JohnKevinTjahjadi,GabriellaMichelle,MuhammadRaisFathinMudzakir FinalYearProject/UROPstudents5(Aug2021-Apr2022) LiuGuangyuan,ManasVegi,ShaLong Listoftranslatorswhohavecontributed≥100translationscanbefoundatstatisticspage. Acknowledgements ThisprojectismadepossiblebythegenerousTeachingEnhancementGrantfromNUSCentreforDevelopmentofTeachingandLearning(CDTL). Termsofuse✕ VisuAlgoisfreeofchargeforComputerSciencecommunityonearth.IfyoulikeVisuAlgo,theonly"payment"thatweaskofyouisforyoutotelltheexistenceofVisuAlgotootherComputerSciencestudents/instructorsthatyouknow=)viaFacebook/Twitter/Instagram/TikTokposts,coursewebpages,blogreviews,emails,etc.Ifyouareadatastructureandalgorithmstudent/instructor,youareallowedtousethiswebsitedirectlyforyourclasses.Ifyoutakescreenshots(videos)fromthiswebsite,youcanusethescreenshots(videos)elsewhereaslongasyoucitetheURLofthiswebsite(https://visualgo.net)and/orlistofpublicationsbelowasreference.However,youareNOTallowedtodownloadVisuAlgo(client-side)filesandhostitonyourownwebsiteasitisplagiarism.Asofnow,wedoNOTallowotherpeopletoforkthisprojectandcreatevariantsofVisuAlgo.Usingtheofflinecopyof(client-side)VisuAlgoforyourpersonalusageisfine.NotethatVisuAlgo'sonlinequizcomponentisbynaturehasheavyserver-sidecomponentandthereisnoeasywaytosavetheserver-sidescriptsanddatabaseslocally.Currently,thegeneralpubliccanonlyusethe'trainingmode'toaccesstheseonlinequizsystem.Currentlythe'testmode'isamorecontrolledenvironmentforusingtheserandomlygeneratedquestionsandautomaticverificationfor realexaminationsinNUS.ListofPublicationsThisworkhasbeenpresentedbrieflyattheCLIWorkshopattheACMICPCWorldFinals2012(Poland,Warsaw)andattheIOIConferenceatIOI2012(Sirmione-Montichiari,Italy).Youcanclickthislinktoreadour2012paperaboutthissystem(itwasnotyetcalledVisuAlgobackin2012).Thisworkisdonemostlybymypaststudents. BugReportsorRequestforNewFeaturesVisuAlgoisnotafinishedproject.DrStevenHalimisstillactivelyimprovingVisuAlgo.IfyouareusingVisuAlgoandspotabuginanyofourvisualizationpage/onlinequiztoolorifyouwanttorequestfornewfeatures,pleasecontactDrStevenHalim.Hiscontactistheconcatenationofhisnameandaddgmaildotcom. PrivacyPolicy✕ Version1.0(Wed,22Dec2021).Disclosuretoallvisitors:WecurrentlyuseGoogleAnalyticstogetanoverviewunderstandingofoursitevisitors.Weplantochangethistoamoreprivacy-friendlyalternativetrackersoon(e.g.,CloudflareWebTrafficAnalytics).SinceWed,22Dec2021,onlyNationalUniversityofSingapore(NUS)staffs/studentsandapprovedCSlecturersoutsideofNUSwhohavewrittenarequesttoStevencanlogintoVisuAlgo,anyoneelseintheworldwillhavetouseVisuAlgoasananonymoususerthatisnotreallytrackableotherthanwhataretrackedbyGoogleAnalytics.ForNUSstudentsenrolledinmodulesthatusesVisuAlgo:ByusingaVisuAlgoaccount(atupleofNUSofficialemailaddress,NUSofficialstudentnameasintheclassroster,andapasswordthatisencryptedontheserverside—nootherpersonaldataisstored),youaregivingaconsentforyourmodulelecturertokeeptrackofyoure-lectureslidesreadingandonlinequiztrainingprogressesthatisneededtorunthemodulesmoothly.YourVisuAlgoaccountwillalsobeneededfortakingNUSofficialVisuAlgoOnlineQuizzesandthuspassingyouraccountcredentialstoanotherpersontodotheOnlineQuizonyourbehalfconstitutesanacademicoffense.Youruseraccountwillbepurgedaftertheconclusionofthemoduleunlessyouchoosetokeepyouraccount(OPT-IN).AccesstothefullVisuAlgodatabase(withencryptedpasswords)islimitedtoStevenhimself.ForotherNUSstudents,youcanself-registeraVisuAlgoaccountbyyourself(OPT-IN).ForotherCSlecturersworldwidewhohavewrittentoSteven,aVisuAlgoaccount(your(non-NUS)emailaddress,youcanuseanydisplayname,andencryptedpassword)isneededtodistinguishyouronlinecredentialversustherestoftheworld.YouraccountwillbetrackedsimilarlyasanormalNUSstudentaccountabovebutitwillhaveCSlecturerspecificfeatures,namelytheabilitytoseethehiddenslidesthatcontain(interesting)answerstothequestionspresentedintheprecedingslidesbeforethehiddenslides.Youcanfreelyusethematerialtoenhanceyourdatastructuresandalgorithmclasses.NotethattherecanbeotherCSlecturerspecificfeaturesinthefuture.ForanyonewithVisuAlgoaccount,youcanremoveyourownaccountbyyourselfshouldyouwishtonolongerbeassociatedwithVisuAlgotool.