Learn
You’ve learned a bunch about graph searches and how to use them effectively:
- You can use a graph search algorithm to traverse the entirety of a graph data structure to locate a specific value
- Vertices in a graph search include a “visited” list to keep track of whether or not each vertex has been checked
- Depth-first search (DFS) and breadth-first search (BFS) are two common approaches to graph search
- The runtime for graph search algorithms is O(vertices + edges)
- DFS, which employs either recursion or a stack data structure, is useful for determining whether a path exists between two points
- BFS, which generally relies on a queue data structure, is helpful in finding the shortest path between two points
- There are three common traversal orders which you can apply with DFS to generate a list of all values in a graph: pre-order, post-order, and reverse post-order
Instructions
If you were to build a GPS system, how could each type of graph search be useful? What map-routing factors do these algorithms not take into consideration when path-finding?
Sign up to start coding
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.