In this article, we will look into the basics of graphs, the different types of graphs, and their representation.
Graphs are complex, nonlinear data structures that are characterized by a group of vertices, connected by edges. For more information on the different types of data structures in Python, check out the following articles:
Table of Contents
 Graphs: Introduction
 Applications of Graphs
 Types of Graphs
 Representing Graphs
 Conclusion
 Further Reading
Graphs: Introduction
Graphs are nonlinear data structures made up of two major components:

Vertices – Vertices are entities in a graph. Every vertex has a value associated with it. For example, if we represent a list of cities using a graph, the vertices would represent the cities.

Edges – Edges represent the relationship between the vertices in the graph. Edges may or may not have a value associated with them. For example, if we represent a list of cities using a graph, the edges would represent the path between the cities.
Figure: Graph
Applications of Graphs
Graphs are used everywhere, from schooling to business. Especially in the fields of computer science, physics, and chemistry.
A few other applications of graphs are:

To visualize organized data.

Directed Graphs are used in Google’s Page Ranking Algorithm.

Social Networks use graphs to represent different users as vertices and edges to represent the connections between them.

In a mapping application, graphs are used to represent places and the path (distance) between them.
Types of Graphs
There are many types of graphs, based on weights, direction, interconnectivity, and special properties. Let’s look at the most common types of graphs.
Based on Direction
Undirected Graphs
In an undirected graph, the edges have no path or direction. If there is a path from vertex X to vertex Y, then there is a path from vertex Y to vertex X. Edge (X, Y) represents the edge connecting vertex X to vertex Y.
That is, edge (X, Y) == edge (Y, X)
.
Figure: Undirected Graph
Directed Graphs
In a directed graph or digraph, the edges have an orientation. If there is a path from vertex X to vertex Y, then there isn’t necessarily a path from vertex Y to vertex X.
That is, edge (X, Y) != edge (Y, X)
.
Figure: Directed Graph
Based on Weights
Weighted Graphs
A weighted graph has a value associated with every edge. The value may represent quantities like cost, distance, time, etc., depending on the graph. An edge of a weighted graph is represented as, (u, v, w)
.
u
> Source vertexv
> Destination vertexw
> Weight associated to go from u to v.
These weighted graphs are extensively used in modelling Computer Networks. For a career as a Networking Engineer, the knowledge of weighted graphs are a must.
Figure: Weighted Graph
Unweighted Graphs
An unweighted graph does not have a value associated with every edge. An edge of an unweighted graph is represented as, (u, v)
.
u
> Source vertexv
> Destination vertex
Relationships in query languages like GraphQL can be represented by using Unweighted Graphs.
Figure: Unweighted Graph
Special Graphs
Trees
An undirected graph with zero cycles is called a tree. A cycle in a graph is a sequence with the first and last vertices in the repeating sequence.
It has X vertices and X1 edges.
Figure: Tree
Rooted Tree
A rooted tree is a tree that has a designated root node. If edges point away from the root, it is called an arborescence/outtree. If edges point towards the root, it is called an antiarborescence/intree.
Figure: Rooted Tree
Directed Acyclic Graphs
Directed Acyclic Graphs or DAGs are graphs with no directed cycles. They represent structures with dependencies. It’s also important to note that: All arborescences are DAGs, but not all DAGs are arborescences.
Directed Acyclic Graphs are used by compilers to represent expressions and relationships in a program.
Figure: Directed Acyclic Graph
Complete Graphs
Complete graphs have a unique edge between every pair of vertices. A complete graph n
vertices have (n*(n1)) / 2
edges and are represented by Kn.
Fully connected networks in a Computer Network uses a complete graph in its representation.
Figure: Complete Graph
Representing Graphs
There are multiple ways of using data structures to represent a graph. The three most common ways are:
Adjacency Matrix
An Adjacency Matrix is a very simple way to represent a graph. In a weighted graph, the element A[i][j]
represents the cost of moving from vertex i
to vertex j
.
In an unweighted graph, the element A[i][j]
represents a Boolean value that determines if a path exists from vertex i
to vertex j
. If A[i][j] == 0
, then no path from vertex i
to vertex j
exists. If A[i][j] == 1
, there is a path from vertex i
to vertex j
.
For example, a snake and ladder game can be represented by using an adjacency matrix. This enables us to use various algorithms to find the shortest path to finish the game. Similarly, many shortest path algorithms use an adjacency matrix.
Example:
graph = [[0, 1, 2],
[2, 0, 5],
[4, 5, 0]]
The adjacency matrix above represents a graph that has 3 vertices. The cost of moving from vertex 0 to vertex 1 is 1, the cost of moving from vertex 0 to vertex 2 is 2, and so on. Usually, the cost of travelling from a vertex to itself is zero.
Advantages and Disadvantages of Adjacency Matrix
Advantages  Disadvantages 

Spaceefficient for dense graph representation.  Space Complexity of this Data Structure  O(V^2). 
The time complexity of getting an edge weight is O(1).  Iterating through the edges takes O(V^2) time. 
Simplest Graph Representation. 
Adjacency List
An adjacency list represents a graph as a list that has vertexedge mappings. Example, A → [(B, 4), (C, 1)] represents an adjacency list where the vertex A is connected to B (weight 4) and C (weight 1). This works really well for sparse graphs.
Advantages and Disadvantages of Adjacency List
Advantages  Disadvantages 

Spaceefficient for sparse graphs.  Less space efficient for dense graphs. 
Iterating over the edges is efficient.  Edge weight lookup is O(E). (worse case) 
Slightly more complex to represent. 
Edge List
An edge list represents the graph as an unstructured list of edges.
Example:
graph = [(C, A, 4), (A, C, 1), (B, C, 6),
(A, B, 4), (C, B, 1), (C, D, 2)]
They are not widely used because this representation lacks structure.
Advantages and Disadvantages of Edge List
Advantages  Disadvantages 

Spaceefficient for sparse graphs.  Less space efficient for dense graphs. 
Iterating over the edges is efficient.  Edge weight lookup is O(E). (worse case) 
Extremely simple representation.  This representation lacks structure. 
Conclusion
In this article, we learned about the various types of graphs, their representations, and their applications.
To summarize,
Types of Graphs

Based on Direction
 Undirected Graph
 Directed Graph

Based on Weights
 Weighted Graph
 Unweighted Graph

Special Graphs
 Tree
 Rooted Tree
 Directed Acyclic Graph
 Complete Graph
Graph Representation

Adjacency Matrix
 Used for dense graphs

Adjacency List
 Used for sparse graphs

Edge List
 Used for simple representation
Further Reading
To learn more about graphs, check out the following pages:
 Practice Graphs – LeetCode
 Graph Theory Notes
 Graph Representation – HackerEarth
Peer Review Contributions by: Gregory Manley
About the author
Saiharsha Balasubramaniam
Saiharsha Balasubramaniam is a Computer Science Undergrad at Amrita Vishwa Vidyapeetham University, India. He is also a passionate software developer and an avid researcher. He designs and develops aesthetic websites, and loves blockchain technology. While he is not programming, he usually binges NetFlix or can be seen reading a book.