Graph theory

Behind the somewhat daunting name "graph theory", which comes from mathematics, lies a set of tools that are very much rooted in the real world. These tools are especially interesting in computer science, because they let you solve a huge number of problems.

A graph lets you model entities (called vertices or nodes) that interact with each other. These interactions are represented by links between the vertices, and these links are called edges.

The vertices and edges of a graph can have properties (sometimes called labels in the literature).

Edges can be directed. They are then called arcs or arrows.

Well... all this vocabulary is very nice, but what is a graph actually good for? Loads of things, of course! A very classic example is the graph of a road network: the vertices are the intersections, and the edges are the roads. Edges? Not quite: it makes more sense here to use arcs, to represent roads that can only be driven in one direction because of one-way streets. We can also add labels to our arcs for the speed limits and the lengths of the roads.

The advantage of using graphs to represent a road network is that we can then use a huge number of "ready-to-use" algorithms to solve the problems we might have with that road network. Typically, we'll want to compute shortest paths. And bingo! We can implement Dijkstra's algorithm :)

And what can it be used for in Leek Wars? To start with, you can represent the map as a graph. First, you can save a few operations when you want to call getPath, if you use a more efficient algorithm than the native one. Next, a graph structure makes it easier to handle the Jump and Teleportation chips.

Among the well-known shortest-path algorithms, there is the famous Dijkstra's algorithm we already mentioned, but there are others, such as the A* algorithm.

Your search for the accessible cells could also benefit from the breadth-first search algorithm (BFS).

For more advanced uses, some farmers use special graph structures called trees), which let them generate the possible sequences of actions.