Graph Theory Algorithms “Simplified”
Graph theory 101
Graph theory is a very broad branch of mathematics and it is highly applicable in real-world problems. Originally, graph theory was “invented” to solve real-world problems and after that, it was hijacked by abstract mathematicians like all other branches of mathematics.
In this tutorial and subsequent tutorials, we will look at some graph theory algorithms and their implementations in Python. Now, back to the meat of the subject.
What Is a Graph?
In a nutshell, a graph is a set of vertices/nodes and edges. If you are not comfortable with “set” replace it with collection.
What is vertice/node?
In the above graph, a vertice/node will be the person.
Vertices are fundamental units of a graph. It can represent almost any entity and generally it is represented as a circle.
What is an edge?
In the above graph, the lines connecting the people are edges.
A line or connection between the vertices is called an edge. It can represent any kind of relation between the vertices.
Types of Graph
Directed graph
A graph with edges that have direction on them is called a directed graph. It may be used to show relations to predecessors (arrow from parents to their child) or ancestors (arrow from children to their parents).
Undirected graph
A graph with edges without directions on them is called an undirected graph. It may be used to show a two-way road.
Weighted graph
A graph in which the edges have a number on them to represent the cost of a transaction, fair of a journey, the distance between cities, etc. It can have any type of edge.
Tree
An undirected graph with no cycles in it is a tree. Here, cycle means that there is only one way to go to a node by following edges from a given other node.
A tree has all its nodes connected by an edge to some other node and has N nodes with N-1 edges.
Representing Graphs
There are many ways to represent a graph, two of the most common ones are:
Adjacency matrix
Let’s say we have N nodes in a graph. We can represent it using a matrix with N rows and N columns where a row and column of that matrix will represent a node and entry in them represents a directed edge (with or without weight).
They form the node representing the row to the node representing the column. Generally, 0 or infinity is used to represent no edge between the nodes. In Python, the adjacency matrix can be represented as:
Adjacency list
Similarly, with graphs of N nodes, we can represent the graph using an adjacency list, where all edges of a node are kept in a list of tuples (node, weight). In python, it can be represented as:
Nested dictionary
I represent the graph using nested dictionaries (this is what I call it) and dictionaries with sets (if the node does not has any edge with weight).
In the next post, I will be posting the Python code for an elaborated graph class with different methods, and we will be using that to implement a depth-first search.
For further information see this video on YouTube by freecodecamp, or for a much deeper dive, click here.
