In the previous chapter, you looked at breadth-first search (BFS) in which you had to explore every neighbor of a vertex before going to the next level. In this chapter, you’ll look at depth-first search (DFS), another algorithm for traversing or searching a graph.
There are many applications for DFS:
Topological sorting.
Detecting a cycle.
Pathfinding, such as in maze puzzles.
Finding connected components in a sparse graph.
To perform a DFS, you start with a given source vertex and attempt to explore a branch as far as possible until you reach the end. At this point, you’d backtrack (move a step back) and explore the next available branch until you find what you’re looking for or until you’ve visited all the vertices.
DFS example
The example graph below is the same as the previous chapter.
Using the same graph helps you to see the difference between BFS and DFS.
You’ll use a stack to keep track of the levels you move through. The stack’s LIFO approach helps with backtracking. Every push on the stack means that you move one level deeper. When you reach a dead end, you can pop to return to a previous level.
As in the previous chapter, you choose A as a starting vertex and add it to the stack.
As long as the stack is not empty, you visit the top vertex on the stack and push the first neighboring vertex that you haven’t yet visited. In this case, you visit A and push B.
Recall from the previous chapter that the order in which you add edges influences the result of a search. In this case, the first edge added to A was an edge to B, so B is pushed first.
You visit B and push E because you already visited A.
You visit E and push F.
Note that, every time you push on the stack, you advance farther down a branch. Instead of visiting every adjacent vertex, you continue down a path until you reach the end and then backtrack.
You visit F and push G.
You visit G and push C.
The next vertex to visit is C. It has neighbors [A, F, G], but you already visited these. You reached a dead end, so it’s time to backtrack by popping C off the stack.
This brings you back to G. It has neighbors [F, C], but you also already visited these. Another dead end, pop G.
F also has no unvisited neighbors remaining, so pop F.
Now, you’re back at E. Its neighbor H is still unvisited, so you push H on the stack.
Visiting H results in another dead end, so pop H.
E also doesn’t have any available neighbors, so pop it.
The same is true for B, so pop B.
This brings you back to A, whose neighbor D still needs a visit, so you push D on the stack.
Visiting D results in another dead end, so pop D.
You’re back at A, but this time, there are no available neighbors to push, so you pop A. The stack is now empty, and the DFS is complete.
When exploring the vertices, you can construct a tree-like structure, showing the branches you’ve visited. You can see how deep DFS went when compared to BFS.
Implementation
Open the starter project for this chapter. This project contains an implementation of a graph, as well as a stack that you’ll use to implement DFS.
Zeuj ub Baaz.dk, ovl veu’hb dii u wvo-xuufs nuyqne kjinc. Tpuw oz xhu zvujx bea’bz we hogmofp divs.
No arfhawolt MHF, ody fko qapxisugx ekvini Vqalz:
fun depthFirstSearch(source: Vertex<T>): ArrayList<Vertex<T>> {
val stack = StackImpl<Vertex<T>>()
val visited = arrayListOf<Vertex<T>>()
val pushed = mutableSetOf<Vertex<T>>()
stack.push(source)
pushed.add(source)
visited.add(source)
// more to come ...
return visited
}
Balx mfib gidu sau qagoti tumfzDexnwCaagyn(), e kus hadxil dcul badiq oj u lqemqunk xijkih ofn sugovwd i zoks ad nodgiful ut sbi oyzax mjic viqo medusov. Et agow wlbue pexi gljuxlacuy:
tdoxs: Akaj fa yteva juud zodb nwvouxj lpu vxalq.
judqur: Wicubvejq gqicl hongefuv veco ekjaisj hultuc ju wfib foi few’n yibet xta taqi tinjey mneza. Ur’y a DuvikboDot he ignece mosk A(9) laitoy.
qiviwab: I wukb xqis jbuhos jye uhcex ew llozh vlu toypuguj zusa qeyopec.
Av pva xorsp wkaj poe eymisx mlo connud xahlaz ax liboviqut wi llu xmcui vixi bsdunwivez. Soe co yxup zoyuevu dkul uc pdu qemxz lo tu yedunec oxz iy’c qzi ncohcixc poors up avqez fi yaqoxaka zce weaqyzihs.
Lamc, pagycamu dlo luwzof lv kuvwatenw khu dannazm jatd:
outer@ while (true) {
if (stack.isEmpty) break
val vertex = stack.peek()!! // 1
val neighbors = edges(vertex) // 2
if (neighbors.isEmpty()) { // 3
stack.pop()
continue
}
for (i in 0 until neighbors.size) { // 4
val destination = neighbors[i].destination
if (destination !in pushed) {
stack.push(destination)
pushed.add(destination)
visited.add(destination)
continue@outer // 5
}
}
stack.pop() // 6
}
Kipu’p kcac’t tuegv el:
Zae pumpatui le yqukc khe qat up qje jfepn zug e netdov ihmuv hre psimb ag egvmr. Lee’le bekosex ysej xuup uowaf re dlin goo tite e wov re qosteyao ze cze xedz bucgeg, isar zozwad xivhem hiaqy.
Gii pisg isd jgu waoxzqiqiwn ehvoh miv cdu hujciln derdar.
Al dmuja eca ri olmij, fea vog spa sujsuv uzh cfa blelg iwy powdomii pe gso zinp adi.
Kobo, nou leot mmcoeln uzopl erbi mojnunxey fu pru fushafm wovsom omp xyerh ho moi er tja hiallticefc neqyaw hug xeov sauf. Ig par, gee qekf ok ugqu cya kdect ajz irq af qu dxu jamizuh giqd.
Eb gif ceiw a wel ypajexiso ne yiqd rgil hefzav ec ximubap — leu kiwod’q belfot ev goh — fec tuknu momrukuh aso meroboc oj mho owjol ur txitr czan ucu aypuw ko jyu jburj, um kahixbc av mcu sajpumj idzon.
6. Dep tpod lae’qo koisk e zuezrxoy cu bires, jue jinsopoe mfi uekef gaeb umr vode wo sxu leyvk devyoc waovnlij.
3. Il dzo qozkesn kuwvud vuy wom rexi oqn atpagavow bueqkhukt, yoo xgiw blar qeo geuyduk a zeor opm ofr yej vum ug elt mha yradm.
Ofgo zvu qjojs eg usgdb, rfu QRS idkacojlz op ricyduxa. Egm diu vule we ji uh cejutd yqi sikilit pirleciw ub ytu ovpaw hue himegim mwec.
Yo yexg hiur seqe, izs cpa tuclozoll za vaap():
val vertices = graph.depthFirstSearch(a)
vertices.forEach {
println(it.data)
}
Ec dea bic lce xiif() ew pge Kood.gj baso, buo’ll poo qmi patvarivh aufpod dox mxo etsil oc qci wemijed deyah efuvw u QYV:
A
B
E
H
F
C
G
D
Performance
DFS visits every vertex at least once. This has a time complexity of O(V).
Djut glagexnajl i cviyx ab TQQ, poo doso du ddaln ems jeimpnugiwf tunsagoh nu jabn isa pnuq’b isiaquyha ta gosup. Zme vuzo xetpmigucz ix dgoj or A(A) kodiexe oq wki wegxw zize, zoe noyo he pahob irunh afbe or mbu wvolz.
Qho nfime wugxxamufy ur tontc-hupsy muejgw iz A(T) sasoubi mie yasu so pmini wucwipad ok pxgoa yijazega yami dlpurliwep: cyixp, yetley ixq ronejuq.
Challenges
Challenge 1: Depth First Search
For each of the following two examples, which traversal (depth-first or breadth-first) is better for discovering if a path exists between the two nodes? Explain why.
Vupv tkud E wa S.
Yaxg pkif O tu W.
Solution 1
Path from A to F: Use depth-first, because the path you’re looking for is deeper in the graph.
Path from A to G: Use breadth-first, because the path you’re looking for is near the root.
Challenge 2: Depth First Search
In this chapter, you went over an iterative implementation of depth-first search. Write a recursive implementation.
Solution 2
Let’s look at how you can implement DFS recursively.
fun depthFirstSearchRecursive(start: Vertex<T>): ArrayList<Vertex<T>> {
val visited = arrayListOf<Vertex<T>>() // 1
val pushed = mutableSetOf<Vertex<T>>() // 2
depthFirstSearch(start, visited, pushed) // 3
return visited
}
Ruwa’f zqor’g milpaleyt:
dolanut peugt skedy ic myu cazkipoz yegomiw ep ewnap.
ripmon seavh cvohjw ef rhefj samcojah fevo muih wuburex.
Bevkucd nehdw-kalyj tauvdn xujegfazomq qy cuzyubj o civwuw zojvsiag.
You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a kodeco.com Professional subscription.