By Noah S., age 16
Hi! Today I’m going to be explaining graph theory, a complex algorithm used almost exclusively in object oriented languages that shines when you want to know the shortest path from something to another thing. Some applications include finding the shortest route to a location, the smallest number of moves to win a chess game, and the fastest way to solve a Rubik’s cube. Overall, graph theory has a lot of potential when applied to something large, and can really be utilized in many amazing ways. Without further ado, let’s jump right in.
Let’s try to visualize the graphs that are mainly used in graph theory. Imagine a bunch of points, with every single point connected to one or two other points. These are called nodes. Nodes are used in many other types of searching algorithms, such as linked lists and trees. Since there are two types of graphs used in graph theory, imagine these two scenarios. First imagine the same points and connections as stated above. This is an undirected graph. An undirected graph is when every line between the points is unmarked. To contrast, now imagine the same graph, but every line between the points has a direction, marked with an arrow. This shows how one node connects to another. Undirected graphs use unmarked lines to indicate that information flows both ways, while directed graphs use marked arrows to indicate information that flows only one way.
Now that we have understood what kinds of graphs exist, let’s discuss the ways they can be utilized. Commonly known as simple graphs, any graph without a clear pattern or shape, and doesn’t loop whatsoever is deemed so. Most graphs used in graph theory are simple graphs. Other types of graphs are non-simple graphs, which can be identified with their use of loops (for example, three nodes all pointing to the next node to form a triangle shape). Another type of graph is an isomorphic graph. These graphs are just simplified versions of the non-simple graph. Since many non-simple graphs end up showing some kind of pattern, usually it can be arranged to form a particular shape. Imagine a bunch of nodes all pointing to each other to form a pentagram or such.
There is one type of graph that stands out, however. It is the weighted graph. A weighted graph is just a normal graph with a catch: Every line that connects two nodes has a weight, usually an integer, of how much it “costs” to use this line. As a result, a path that connects two nodes might end up being longer than a path that goes through 4 or 5 nodes. Knowing the weight allows the algorithm to show signs of sophistication. For example, maybe you see a lot of traffic going to your destination. Weighted graphs allow you to determine the fastest route, and you may end up arriving there a few minutes earlier. Of all the graphs mentioned in this post, weighted graphs are the most complex, but the most fundamental in properly understanding and utilizing this code.
Now let’s talk about how to actually make this code work. If you have experience with linked lists or trees, or basically anything with nodes, it’s pretty simple to understand. You traverse through the graph, starting with node 1, you traverse through the graph (test out every option) until you hit your destination. Then, it calculates the fastest possible route. If weights are not present, it is simply the path with the least amount of lines. If weights are present, however, it will calculate which path has the least weight.
This is graph theory in a nutshell. There are some other small nuances and such, but knowing the stuff that I have written will set you pretty well off. Understanding graph theory will help you understand other object oriented algorithms, like trees and linked-lists (although I would start there if you have no coding experience with nodes).