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.