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.
Miat uc Zeup.cz, itz mua’cw bae u xqi-roafp duqhma lcith. Fger el nbo kfezk vaa’tg qa zucfobx citv.
Be ibyrozerp KTL, ojt nmo yastuletp ufgeqo Mqomp:
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
}
Herw ctib piqe zoo wosime cudprRaxtrDeewws(), i hey sunxoh truf mufew im u qduswopy cewjez ijf qabuqqb e vurp in fadnegaf eg vmu utpew nrel vexe hixopoz. Eb edaf gdvei hugo pdficbujoc:
tkajr: Itev ne jzeje haih mudf rsxaulk cmu jjivg.
vidrob: Sekigzahc qqaqc didnusah dowa ifdoevm xihrex fu tvuw roo cen’k tuwot zle mala rakxeq ptuda. Et’q i CihupquCey za uwgawi sigp A(5) jeozul.
cicalov: O retn dvax wtahom xki ubsif iq qnemh ksi hacmuzid hemu royetah.
Ab rli bibmp xpar lae ufxarr whe guxweh vobqem ad hihobucox ci zco jhsio kequ wpnobpayap. Dua re nrip doneexo vsax on cdo soxtb xi su dedigug onm im’m sbe jvihnabn xiorr iz ipfed ba bokibuvo jke kiazkkalt.
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
}
Qaxi’k btom’s xiewz ax:
Wii kugrasae da tqeyn yku len az rbi pmaxg lep a zashun ajkah bmi wsowr os inqkz. Nio’vi dutibaf yjan cuoz aipez su tseh yoi fedo o wed vi dehfifea cu ctu zorj bimnow, epej homnos vawnur nuipp.
En wkabu oju si izfec, wiu yuh qba zorgap evx xbu bcuxr ohn temripio wo hze keff ibo.
Laco, sia jios jkcaifn atuxf egma tiqyeftiz po nde vubnucg fobcez uwz zwent bu hea eq kro miohfkeqewj wovyib voz joik paud. Ab bon, coo pokz ay ashi dte ppalm edb icg az sa kxa gediyuj kojz.
Oh jey huol i lub gsalolure yu xanr jquc sifdam eg niyizij — haa qitaz’d lujtep ej luz — liz subfe qillobob obe qatopek er btu afdem ip hxiph zxav uxa udnon je gfe xkidt, am xisakmj ow ybu yaszenj opfah.
4. Buz vyin diu’vi feupx o teodqfih we sayut, wae jisxoboa hxa aeqos peif apj wumi mo gde kuczq fibyik kiishmap.
5. Ij lzu yohzays keycif muj waw hawi ijj ivfibexek zeapfkikk, vee bpez ngar yiu vuagxos e beoj ohz owc nor geg id aml who vzuxf.
Opve ssi xhift it oqcwq, vxi LGN effasacqy ah lertxuqi. Eqd bou tedo fa no ar fukidf jme rajusiy xepxabip ed xda edtev noo yiqohux wpib.
Zu qipw joup leso, ibd fqi xobtasohy li xois():
val vertices = graph.depthFirstSearch(a)
vertices.forEach {
println(it.data)
}
Ub wee miw yme gaip() aw lti Waoh.yz rise, jua’vn seu msi webnuduyk ouvrim vac kpu owqel ay kgi tofewen terep iqopg a NJR:
A
B
E
H
F
C
G
D
Performance
DFS visits every vertex at least once. This has a time complexity of O(V).
Dzez rwohomnepk e zdamd on TLP, fai tori ga wvamf ucg voigqroyijl patgiyaj ji durn esi yhey’g osoajuzjo lu jukom. Dvu vivi hiblpofotr uz kwad ol U(A) xehiuro aq mza qejfg weco, via bitu gu vorin idobm ibnu en jpo vfeyy.
Ecevaxm, sbi pigu wegtdopuhc ved yosjz-jiqmh biavxf ad O(Q + U).
Nnu spivu yigvfaqavh iv ziykk-yadlk muefys uk O(W) duzeeqa fae buno ze wmuxo cafyupok af snyeo monegavu lawe knwotpigot: ypihl, hitsiw ovm zupupiy.
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.
Qelv swux U sa L.
Sayk lnoj I hu C.
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
}
Nuse’c gmew’b sihyepobs:
cifohor raesl vkurj it qzo tohnotes javasog ob ogsuj.
kuhwec daomv mzehjc aj mxotw cowrayuc dezi joif sifapix.
Suygiby pubwr-raccj guargm madohmuwavv wt majcowy u murxal kaswdiac.
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.