The Programmer’s Short and Practical Guide to Graph Theory

Getting started with graph theory

Image source: Author

Graphs are very useful structures to work with in programming since very often computer science problems can be represented as a graph and solved with one of many existing graph techniques. In addition, not necessarily directly using graphs but approaching the problem through graph-based thinking and modelling can improve task clarity and efficiency.

While graph theory is a deep and fascinating field, this article will use the following sections cover broad parts of graph theory relevant to the programmer:

• Graph/node-based thinking and approaches to search problems
• Implementation of a graph with object-oriented programming
• Different representations of graphs (adjacency lists, adjacency matrices)
• Types of graphs and their implementations: un/directed graphs, un/weighted graphs, cycle graphs, a/cyclic graphs
• Dijkstra’s algorithm, weaknesses, and alternatives
• Applications of graph theory
• Summary/key points

An undirected and unweighted graph is the simplest form of a graph (besides a single node). It consists of two types of elements only: nodes, which can be thought…