Graphs are mathematical objects which encode relationships between entities. They consist of vertices or nodes, which stand for said entities, and edges, which are the relationships between the vertices and nodes. By virtue of their simplicity and power, they have become a cornerstone of modern computer science. Below we show three ways to search graphs: breadth first search, depth first search, and Dijkstra's algorithm.
In breadth first search, we exhaust all nodes of a particular depth from the start and repeat for increasing depth until we run out of nodes. In the example given, we see that breadth first search starts at the top node, and eventually propagates through the entire tree. Breadth first search is helpful for ensuring that every possibility at a given depth is explored before we move on, for example if we want to find all English words with length at most some integer n.
In depth first search, we exhaust a branch of a tree before we continue looking at other branches. In the example given, notice that the entire left branch is traversed before the right branches are examined. In fact, the order of how we check depth matters as well; in particular graphs, choosing random branches for depth first search as opposed to going in order as shown here can have, on average, much faster searches in many graphs.
Dijkstra's algorithm seeks to find the shortest path from a given node in a graph and taking into account edge weights. This implementation stores nodes to visit, represented in pink, in a minimum heap and afterwards visits nodes in order of least cost, with visited nodes represented in red. Also known as Uniform Cost Search, it can also be used to find all shortest paths between all nodes.