Python - Data Structures - Graphs

Python Data Structures – Graphs

Introduction to Graphs in Python

Graphs are one of the most versatile and widely used data structures in computer science and Python programming. A graph is a collection of nodes, called vertices, connected by edges. Graphs are non-linear data structures that are perfect for modeling complex relationships, such as social networks, transportation systems, and web link structures. Unlike arrays, lists, or stacks, graphs allow representation of multiple interconnections between entities.

Understanding graphs in Python is essential for solving advanced algorithmic problems, optimizing routes, implementing network analysis, and performing tasks in artificial intelligence. This tutorial will provide a detailed explanation of graphs, their types, representations, traversal algorithms, and real-world applications with practical Python code examples and outputs.

Graph Terminology

Vertices and Edges

In a graph, a vertex (or node) represents an entity, and an edge represents the connection between two vertices. Vertices can be represented using numbers, strings, or objects in Python. Edges may have direction and weights depending on the type of graph. Understanding these fundamental concepts is critical before working with graphs.

Directed and Undirected Graphs

An undirected graph has edges without direction, meaning connections between vertices are bidirectional. In contrast, a directed graph (or digraph) has edges with direction, represented as ordered pairs of vertices. Directed graphs are used in modeling workflows, website links, and task dependencies, while undirected graphs are used for friendships, networks, and transportation systems.

Weighted and Unweighted Graphs

Weighted graphs assign numerical values to edges representing distance, cost, or time. Unweighted graphs treat all edges equally. Weighted graphs are commonly used in shortest path and optimization algorithms, while unweighted graphs are simpler and mainly used in traversal problems.

Graph Representation in Python

Adjacency List Representation

An adjacency list stores each vertex and its neighboring vertices in a dictionary or list of lists. It is memory-efficient and ideal for sparse graphs. Python’s dictionaries provide a natural way to implement adjacency lists, allowing easy access and iteration over neighbors.

# Adjacency List Representation
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"]
}

print(graph)

Output:

{'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C']}

Adjacency Matrix Representation

An adjacency matrix represents a graph using a 2D array where each cell indicates whether an edge exists between vertices. This representation is simple and easy to implement but uses more memory, especially for sparse graphs. Adjacency matrices are suitable for dense graphs with many edges.

# Adjacency Matrix Representation
vertices = ["A", "B", "C", "D"]
matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0]
]

for row in matrix:
    print(row)

Output:

[0, 1, 1, 0]
[1, 0, 0, 1]
[1, 0, 0, 1]
[0, 1, 1, 0]

Graph Traversal Algorithms

Breadth First Search (BFS)

Breadth First Search is a traversal technique that explores all neighbors of a vertex before moving to the next level. BFS uses a queue to keep track of vertices to visit. It is commonly used in shortest path finding in unweighted graphs, connectivity analysis, and level-order traversal of trees.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

bfs(graph, "A")

Output:

A B C D

Depth First Search (DFS)

Depth First Search explores as deep as possible along each branch before backtracking. DFS can be implemented recursively or using a stack. DFS is used in topological sorting, cycle detection, and connected components identification. It is a fundamental algorithm in problem-solving with graphs.

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()

    visited.add(start)
    print(start, end=" ")

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

dfs(graph, "A")

Output:

A B D C

Weighted Graphs in Python

Representation of Weighted Graphs

Weighted graphs associate a numerical value with each edge. Python dictionaries of lists of tuples provide an efficient way to represent weighted graphs. Each tuple contains a neighbor vertex and the edge weight. This format is ideal for implementing shortest path and minimum spanning tree algorithms.

weighted_graph = {
    "A": [("B", 2), ("C", 4)],
    "B": [("A", 2), ("D", 3)],
    "C": [("A", 4), ("D", 1)],
    "D": [("B", 3), ("C", 1)]
}

print(weighted_graph)

Output:

{'A': [('B', 2), ('C', 4)], 'B': [('A', 2), ('D', 3)], 'C': [('A', 4), ('D', 1)], 'D': [('B', 3), ('C', 1)]}

Shortest Path Algorithms

Dijkstra’s Algorithm

Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative weights. It is widely used in routing systems, GPS navigation, and network optimization. The algorithm repeatedly selects the vertex with the smallest tentative distance.

import heapq

def dijkstra(graph, start):
    distances = {vertex: float("inf") for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

print(dijkstra(weighted_graph, "A"))

Output:

{'A': 0, 'B': 2, 'C': 4, 'D': 5}

Advanced Graph Applications

Graphs have extensive applications in real-world systems. They model social networks, web page links, transportation networks, communication networks, recommendation engines, and project dependencies. Graph algorithms are also crucial in artificial intelligence, machine learning, and data mining.

For example, BFS and DFS are used in social network analysis, Dijkstra’s algorithm in navigation systems, and Minimum Spanning Trees in designing efficient networks. Mastering graph algorithms enhances programming skills and problem-solving abilities.

Learning Graphs

To master graphs in Python, start with understanding basic terminology and simple representations. Practice implementing BFS and DFS multiple times. Gradually learn weighted graphs, shortest path algorithms, and advanced topics like Topological Sorting and Minimum Spanning Trees. Visualizing graphs using diagrams helps improve understanding and retention.

Solving real-world problems and practicing coding challenges strengthens conceptual knowledge. Using Python data structures such as dictionaries, lists, sets, and queues efficiently is key to mastering graph algorithms.

Graphs are an essential data structure in Python with applications in computer science, networking, AI, and software development. This tutorial covered graph types, representations, BFS, DFS, weighted graphs, Dijkstra’s algorithm, and practical applications with Python code examples and outputs. By mastering graph concepts, learners can solve complex problems and build scalable, efficient applications.