Hey, everyone. Some of you might not know this, but I’m a big nerd when it comes to the topic of computer science. Coding, functions, runtime analysis, space complexity, algorithms… you name a CS topic, I’m probably interested in it. In this series of articles I’m going to outline how I used graph theory, a fundamental topic of computer science, in developing a feature for my current project.
In this article series, I want to give a surface-level introduction to graph theory and showcase the solution to a problem from one of my projects
First and foremost, let’s talk about what graph theory is by defining some of the terms. A graph is a set of vertices (aka nodes), which have edges (aka arcs) connecting them. Two vertices are adjacent if they share an edge. An undirected graph is one in which edges have no direction (edges are lines), and the edges in a directed graph have a direction (edges are arrows). A weighted graph assigns a value to edges
Pictured above is a representation of an unweighted, undirected graph featuring nodes labelled A through F. This graph could represent many real-world ideas:
- A physical map of cities connected by highways
- A social network of people connected by friendships
- A set of game board states connected by moves you have to make to get from one state to another
- A final boss’ attack pattern (nodes are unique attack states, edges are transitions)
Notice how not all of these examples are physical things! They are instead collections of things and relationships between those things. I hope you can start to imagine the many different applications of graphs to real-world problems. Many algorithms have been dreamed up to solve problems involving graphs. To name just a few:
- Breadth-first (BFS) and depth-first search (DFS) – Two methods of visiting all the nodes in a graph but in different orders
- Dijkstra’s algorithm – For weighted graphs, find the lowest cost path between two nodes (you cannot use negative edge weights).
- The Bellman-Ford algorithm – Similar to Dijkstra’s and slower, except you can use negative edge weights (however, there must not be any negative cycles in the graph – a cycle of edges that sum to a negative number)
- The Floyd-Warshall algorithm – For weighted graphs, calculate all of the paths from each node to every other node.
- Prim’s algorithm – For weighted graphs, find a minimum spanning tree that visits all nodes, and picks edges so that all nodes are part of the complete graph, while also minimizing costs of used edges.
In the next article, I’ll describe a problem that I identified while working on my project. Later, I show how one of these solve my problem. Click here for part 2 of this series.