Using the Graph Data Structure in Python

In this article, we will look into the basics of graphs, the different types of graphs, and their representation. <!--more--> Graphs are complex, non-linear 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:

• Introduction to Data Structures
• List
• Stack
• Queue
• Linked Lists
• Binary Trees
• Heaps

Table of Contents #

• Graphs: Introduction
• Applications of Graphs
• Types of Graphs
• Representing Graphs
• Conclusion
• Further Reading

Graphs: Introduction #

Graphs are non-linear 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.

• Graphs Based on Direction
• Graphs Based on Weights
• Special 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 vertex
• v -> Destination vertex
• w -> 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 vertex
• v -> 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 X-1 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/out-tree. If edges point towards the root, it is called an anti-arborescence/in-tree.

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*(n-1)) / 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
• Adjacency List
• Edge List

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
Space-efficient 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 vertex-edge 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
Space-efficient 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
Space-efficient 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