Graph search is a highly important algorithm that is fundamental blazingly fast and widely applicable. The problem of graph search can be condensed down to the following:
Input: An undirected or directed graph and a starting vertex
Output: All the vertices of the graph reachable from the starting vertex
Sometimes this is also called the Graph Traversal problem.
A generic search algorithm can be implemented as one that chooses an edge randomly on the frontier of the explored part of the graph. There can be many such edges so to specify the algorithm fully, we need a method for choosing one of them. The two most important strategies for doing this are:
Both approaches are useful because they have different applications. Both of them are useful for finding different properties of the graph in the most efficient way possible.
A very important technique in graph traversal is Backtracking which is an application of DFS that is best in breaking down search spaces.
Graph Problems
Graph Problems come in a variety of forms and it is not possible to learn the algorithm for every graph problem that you come across. In general, we have two strategies which we can use to solve graph problems:
- Modify an existing algorithm to solve a new problem.
- Black box the a known algorithm, but transform our problem into one our algorithm will solve.
This is useful because there are a lot of graph problems. Even seemingly unrelated problems can often be converted into one.
In particular for graph problems, there are a few common ways to extend the graph algorithms we have to problems that might not be conventional graph problems:
- Add a few extra nodes
- Add a few extra edges
- Create multiple copies of the graph
Then, we can apply any of the know graph traversal algorithms to solve the problems, notably:
- Cycle Detection (which is slightly different for directed graphs)
- Topological Sort (using DFS)
- Connected Components (SCCs for directed graphs)
- Counting edges and vertices