The Basics of Graph Theory
In this article, we will get a quick introduction to the basics of graph theory. We will talk about graphs in general — and the two classes they can fall into directed or undirected graphs. Afterward, we will also tackle another form of graphs — trees and so-called minimum spanning trees. This will all serve as the theoretical foundations for this series of articles where we will try to understand various algorithms which function upon graphs — for example, Depth and Breadth-First Search.
Graphs and Their Representation
Firstly, we need to understand what a graph is — and how we can recognize them when we see them in the wild. A graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense “related”. The objects are called vertices, with one being called a vertex, and the relation connecting two vertices is called an edge. We can take a simple example to understand the idea behind it.
Let us imagine that we have two groups, A and B, of friends — each group has 3 members. Let us say group A consists of Edgar, Henry, and Jack. Group B consists of Max, Millie, and Bobby. We now want to model the friendship relations in these two groups of friends. Hence, the vertices are the different members — and the edges are whether there is a friendship between two individuals or not.
