Depth-First Search
There are two well-known approaches for graph search: depth-first search and breadth-first search. Both approaches can get the job done, but each provide 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, Second Edition, 2nd Edition 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.
