Depth-First Search
The two well-known approaches for graph search are depth-first search and breadth-first search. Both approaches can get the job done, but each provides unique advantages in particular situations. We’re going to start with depth-first search, also referred to as DFS, because it’s actually quite similar to the algorithm for binary tree traversal that we discussed back in Binary Search Tree Traversal. In fact, it’s also the same essential algorithm that we saw in Filesystem Traversal.
As mentioned earlier, graph search can be used to either find a particular vertex, or it can be used to simply traverse the graph. We’re going to begin by using depth-first search to traverse the graph since that algorithm is slightly simpler. ...
Get A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1 now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
