12.5 Graph Algorithms in Python

NicePython

— 5 min read

A graph is a data structure that consists of a set of nodes (or vertices) and a set of edges that connect pairs of nodes. Graphs are used to represent relationships or connections between entities. Common examples include social networks, computer networks, road maps, and dependencies in software systems.

Graphs can be either directed or undirected:

  • In a directed graph, edges have a direction (from one node to another).
  • In an undirected graph, edges do not have a direction (they connect two nodes symmetrically).

In this section, we will explore how to represent and implement graphs in Python, followed by common algorithms used to traverse and solve problems in graphs, such as depth-first search (DFS), breadth-first search (BFS), Dijkstra’s shortest path algorithm, and topological sorting.

12.5.1 Graph Representation

Graphs can be represented in several ways, with the two most common methods being:

  1. Adjacency Matrix: A 2D matrix where rows and columns represent nodes, and matrix values indicate whether there is an edge between nodes.
  2. Adjacency List: A dictionary where each node is associated with a list of nodes that it is connected to.

12.5.2 Adjacency List Representation

An adjacency list is the most common and efficient way to represent a graph in Python, as it allows us to store only the existing edges rather than an entire matrix.

Example: Adjacency List Representation of a Graph

class Graph:
    def __init__(self):
        self.graph = {}  # Dictionary to store the graph as an adjacency list

    # Add a node to the graph
    def add_node(self, node):
        if node not in self.graph:
            self.graph[node] = []

    # Add an edge to the graph (for an undirected graph, add both directions)
    def add_edge(self, node1, node2):
        self.graph[node1].append(node2)
        self.graph[node2].append(node1)

    # Print the graph
    def print_graph(self):
        for node in self.graph:
            print(f"{node}: {self.graph[node]}")

# Example usage
g = Graph()
g.add_node(1)
g.add_node(2)
g.add_node(3)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.print_graph()

Output:

1: [2, 3]
2: [1, 3]
3: [1, 2]

In this example:

  • We define a Graph class that represents a graph as an adjacency list using a dictionary. The keys are nodes, and the values are lists of connected nodes.
  • add_node() adds a new node to the graph.
  • add_edge() adds an edge between two nodes.

12.5.3 Graph Traversal Algorithms

Graph traversal algorithms explore the nodes and edges of a graph. Two of the most common traversal techniques are Depth-First Search (DFS) and Breadth-First Search (BFS).

12.5.4 Depth-First Search (DFS)

Depth-First Search (DFS) is an algorithm that starts at a given node and explores as far as possible along each branch before backtracking. DFS can be implemented either iteratively (using a stack) or recursively.

Example: Recursive DFS Algorithm

class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, node1, node2):
        if node1 not in self.graph:
            self.graph[node1] = []
        if node2 not in self.graph:
            self.graph[node2] = []
        self.graph[node1].append(node2)
        self.graph[node2].append(node1)

    # Depth-First Search (DFS) Recursive
    def dfs(self, start, visited=None):
        if visited is None:
            visited = set()
        visited.add(start)
        print(start, end=" ")
        
        for neighbor in self.graph[start]:
            if neighbor not in visited:
                self.dfs(neighbor, visited)

# Example usage
g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(3, 5)

print("DFS Traversal:")
g.dfs(1)

Output:

DFS Traversal:
1 2 4 3 5

In this example:

  • The dfs() method is implemented recursively. It starts at the given node, marks it as visited, and recursively explores each neighbor.
  • The traversal explores each branch deeply before backtracking, as shown in the output.

12.5.5 Breadth-First Search (BFS)

Breadth-First Search (BFS) explores the nodes of a graph layer by layer. It visits all the neighbors of a node before moving on to their neighbors. BFS is typically implemented using a queue.

Example: BFS Algorithm Using a Queue

from collections import deque

class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, node1, node2):
        if node1 not in self.graph:
            self.graph[node1] = []
        if node2 not in self.graph:
            self.graph[node2] = []
        self.graph[node1].append(node2)
        self.graph[node2].append(node1)

    # Breadth-First Search (BFS)
    def bfs(self, start):
        visited = set()
        queue = deque([start])
        visited.add(start)

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

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

# Example usage
g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(3, 5)

print("BFS Traversal:")
g.bfs(1)

Output:

BFS Traversal:
1 2 3 4 5

In this example:

  • The bfs() method uses a queue to explore each node's neighbors before moving to the next level of nodes.
  • The traversal explores each level of the graph, starting from the root.

12.5.6 Dijkstra’s Algorithm for Shortest Path

Dijkstra’s Algorithm is a greedy algorithm used to find the shortest path from a source node to all other nodes in a weighted graph. It maintains a set of nodes whose shortest distance from the source is known, and iteratively updates the distances of the remaining nodes.

Example: Dijkstra's Algorithm

import heapq

class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, node1, node2, weight):
        if node1 not in self.graph:
            self.graph[node1] = []
        if node2 not in self.graph:
            self.graph[node2] = []
        self.graph[node1].append((node2, weight))
        self.graph[node2].append((node1, weight))

    # Dijkstra's Algorithm
    def dijkstra(self, start):
        distances = {node: float('inf') for node in self.graph}
        distances[start] = 0
        priority_queue = [(0, start)]  # (distance, node)

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

            if current_distance > distances[current_node]:
                continue

            for neighbor, weight in self.graph[current_node]:
                distance = current_distance + weight

                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    heapq.heappush(priority_queue, (distance, neighbor))

        return distances

# Example usage
g = Graph()
g.add_edge(1, 2, 1)
g.add_edge(1, 3, 4)
g.add_edge(2, 3, 2)
g.add_edge(2, 4, 5)
g.add_edge(3, 4, 1)

print("Shortest paths from node 1:")
distances = g.dijkstra(1)
print(distances)

Output:

Shortest paths from node 1:
{1: 0, 2: 1, 3: 3, 4: 4}

In this example:

  • dijkstra() calculates the shortest path from a starting node to all other nodes in the graph.
  • A priority queue (min-heap) is used to efficiently determine the next node to explore based on the shortest known distance.

12.5.7 Topological Sorting

Topological Sorting is an ordering of the nodes in a directed acyclic graph (DAG) such that for every directed edge from node u to node v, u appears before v in the ordering. This is commonly used in scheduling tasks that have dependencies.

Example: Topological Sort Using DFS

class Graph:
    def __init__(self):
        self

.graph = {}

    def add_edge(self, node1, node2):
        if node1 not in self.graph:
            self.graph[node1] = []
        self.graph[node1].append(node2)

    # Topological Sort (using DFS)
    def topological_sort_util(self, node, visited, stack):
        visited.add(node)
        for neighbor in self.graph.get(node, []):
            if neighbor not in visited:
                self.topological_sort_util(neighbor, visited, stack)
        stack.append(node)

    def topological_sort(self):
        visited = set()
        stack = []

        for node in self.graph:
            if node not in visited:
                self.topological_sort_util(node, visited, stack)

        return stack[::-1]  # Return in reverse order

# Example usage
g = Graph()
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)

print("Topological Sort:")
result = g.topological_sort()
print(result)

Output:

Topological Sort:
[5, 4, 2, 3, 1, 0]

In this example:

  • topological_sort() uses DFS to recursively visit nodes and stores the order in which nodes are finished. The result is the topological order of nodes.

12.5.8 Summary

  • Graphs: Data structures that represent relationships between entities. They consist of nodes and edges and can be either directed or undirected.
    • Adjacency List: A common and efficient way to represent graphs in Python.
  • Graph Traversal Algorithms:
    • Depth-First Search (DFS): Explores a graph deeply before backtracking. Useful for exploring all paths in a graph.
    • Breadth-First Search (BFS): Explores a graph layer by layer, visiting all neighbors of a node before moving to their neighbors.
  • Dijkstra’s Algorithm: Finds the shortest path from a source node to all other nodes in a weighted graph.
  • Topological Sorting: Provides an ordering of nodes in a directed acyclic graph (DAG) where each node appears before its dependent nodes.

By mastering graphs and their associated algorithms, you can solve a wide range of real-world problems involving relationships, connectivity, shortest paths, and dependencies. These algorithms are foundational in computer science and are used in domains like network analysis, route optimization, and task scheduling.

Read more