Introduction to Graphs In python
Introduction to Graphs In Python
Graphs are fundamental data structures used in computer science and mathematics to model various relationships and connections between entities. They are versatile and find applications in a wide range of fields, including social networks, transportation systems, and computer networks.
In this article, we will explore the basics of graphs in Python, their types, representation, and common algorithms.
What is a Graph?
A graph is a collection of nodes (vertices) and edges. Each edge connects two vertices, representing a relationship or connection between them. Graphs can be used to model a wide array of scenarios, making them an essential data structure in computer science.
- A 2D array where each cell shows if an edge exists between two vertices.
- A list where each index stores the neighboring vertices of that node.
Types of Graphs
There are several types of graphs, and understanding their distinctions is crucial for various applications.
Directed Graphs
In a directed graph, edges have a specific direction, indicating a one-way relationship between nodes. For example, in a social media network, a directed edge could represent the “follow” relationship between users.
Undirected Graphs
Undirected graphs have edges without a specific direction, meaning the relationship is bidirectional. In a road network, an undirected edge represents a two-way road.
Weighted Graphs
In weighted graphs, each edge has a weight or cost associated with it. These weights can represent distances, costs, or any other relevant measure.
Unweighted Graphs
Conversely, unweighted graphs have edges without any associated weights.
Prime Course Trailer
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Related Banners
Graph Representation:
Graphs can be represented in two main ways using an adjacency matrix or an adjacency list:
Representation of Graphs in Python using Adjacency Matrix
The adjacency matrix is a 2D array used to represent a graph, where each cell at position (i, j) indicates whether there is an edge between vertex i and vertex j. This method is simple and efficient for dense graphs.
Here’s the Python code with output and explanation:
# Number of vertices
V = 4
# Initialize a 4x4 matrix with all 0s
adj_matrix = [[0] * V for _ in range(V)]
# Function to add edge between vertices
def add_edge(v1, v2):
adj_matrix[v1][v2] = 1
adj_matrix[v2][v1] = 1 # for undirected graph
# Adding edges
add_edge(0, 1)
add_edge(0, 2)
add_edge(1, 2)
add_edge(2, 3)
# Displaying the adjacency matrix
print("Adjacency Matrix Representation:")
for row in adj_matrix:
print(row)
Output:
Adjacency Matrix Representation: [0, 1, 1, 0] [1, 0, 1, 0] [1, 1, 0, 1] [0, 0, 1, 0]
Explanation:
- Each row and column represents a vertex.
- A 1 in adj_matrix[i][j] means there is an edge between vertex i and vertex j.
- Since it’s an undirected graph, the matrix is symmetric (both adj_matrix[i][j] and adj_matrix[j][i] are 1).
- For example, the 1 at position [0][1] and [1][0] indicates an edge between vertex 0 and 1.
Time and Space Complexity of Adjacency Matrix
- Space Complexity: O(V²) – Always stores all possible vertex pairs.
- Time Complexity:
- Add/Remove Edge: O(1)
- Check Edge: O(1)
- Traverse Neighbors: O(V)
Representation of Graphs in Python using Adjacency List:
An adjacency list represents a graph as a dictionary where each key is a vertex, and the value is a list of connected vertices. It’s memory efficient for sparse graphs.
Here’s the Python code with output and explanation:
# Initialize the graph using dictionary
adj_list = {
0: [1, 2],
1: [0, 2],
2: [0, 1, 3],
3: [2]
}
# Display the adjacency list
print("Adjacency List Representation:")
for vertex in adj_list:
print(f"{vertex} -> {adj_list[vertex]}")
Output:
Adjacency List Representation: 0 -> [1, 2] 1 -> [0, 2] 2 -> [0, 1, 3] 3 -> [2]
Explanation:
- Each key is a vertex, and the list contains all vertices connected to it.
- It’s space-efficient and only stores existing edges.
- Ideal for sparse graphs, where number of edges is much less than V².
Time & Space Complexity:
- Space: O(V + E)
- Add/Remove Edge: O(1) (amortized)
- Check Edge: O(K) (K = neighbors of a node)
- Traverse Neighbors: O(K)
Traversing a Graph:
Traversing a graph is a fundamental operation in graph theory and computer science. It involves visiting all the vertices (nodes) and edges (connections) of a graph in a systematic manner. There are two main methods for graph traversal: depth-first traversal and breadth-first traversal.
- Depth-First Traversal (DFS):
- In DFS, you start at an initial vertex and explore as far as possible along each branch before backtracking.
- This can be implemented using recursion or a stack data structure.
- DFS is often used to find paths, cycles, and connected components in a graph.
Here’s a simple pseudocode for DFS:
function DFS(graph, start_vertex):
if start_vertex is not visited:
mark start_vertex as visited
for each neighbor in graph[start_vertex]:
if neighbor is not visited:
DFS(graph, neighbor)
- Breadth-First Traversal (BFS):
- In BFS, you start at an initial vertex and explore all its neighbors before moving on to their neighbors.
- This is typically implemented using a queue data structure.
- BFS is often used to find the shortest path or to explore the graph level by level.
Here’s a simple pseudocode for BFS:
function BFS(graph, start_vertex):
create an empty queue
enqueue start_vertex into the queue
mark start_vertex as visited
while the queue is not empty:
current_vertex = dequeue from the queue
for each neighbor in graph[current_vertex]:
if neighbor is not visited:
enqueue neighbor into the queue
mark neighbor as visited
Applications of Graphs:
Graphs have a wide range of applications, including:
- Social networks
- Transportation systems
- Recommendation systems
- Network analysis
- And many more
Graph Algorithms :
Various graph algorithms are used for solving specific problems.
Final Thoughts
Graphs in Python provide a powerful way to model complex relationships between entities. Whether using adjacency matrices or lists, understanding how to represent and traverse graphs is key to solving real world problems efficiently.
By mastering different graph types, traversal techniques like DFS and BFS, and algorithms like Dijkstra and Kruskal, developers can build scalable systems for routing, networking, recommendation engines, and more.
FAQs
An adjacency matrix is space-intensive but faster for edge checks, while an adjacency list is more memory efficient and ideal for sparse graphs.
Use BFS for shortest path or level-wise traversal, and DFS for exploring deep paths or checking connectivity in components.
Graphs are used in social networks, transportation systems, recommendation engines, and network routing among many other fields.
Yes, Python is excellent for prototyping graph algorithms due to its readable syntax and support for data structures like dictionaries and sets.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment