Python underlying technology revealed: how to implement graph algorithms

With the continuous development of computer technology, graph theory and its related algorithms have become a very important part of the computer field. For Python programmers, mastering these underlying technologies can not only improve the efficiency and quality of code, but also help optimize program performance and development efficiency.

This article will introduce the underlying technology of graph algorithms in Python, including graph storage methods, traversal methods, shortest path algorithms, minimum spanning tree algorithms, and topological sorting algorithms, focusing on the implementation ideas and code examples of each algorithm.

1. How to store graphs

In Python, we can use adjacency matrices or adjacency lists to store graphs.

1. Adjacency matrix

The adjacency matrix is ​​a two-dimensional matrix in which the rows and columns of the vertices correspond to two vertices respectively. If there is an edge connecting two vertices, the position value is set to 1 or its edge weight; otherwise it is set to 0. For example, the following is an example of an adjacency matrix:

graph = [[0, 1, 1, 0], 
         [1, 0, 1, 1], 
         [1, 1, 0, 1], 
         [0, 1, 1, 0]]

This matrix represents an undirected graph with a total of 4 vertices, among which 1, 2, and 3 are connected to each other by edges.

2. Adjacency list

The adjacency list is a dictionary, in which each key corresponds to a vertex, and the corresponding value is a list of neighbor vertices of the vertex. For example:

graph = {0: [1, 2], 
         1: [0, 2, 3], 
         2: [0, 1, 3], 
         3: [1, 2]}

This dictionary represents the same undirected graph, in which each key value corresponds to a vertex, and the value corresponding to this vertex is the edge between this vertex and other vertices.

2. Graph traversal method

1. Depth-first traversal (DFS)

Depth-first traversal searches the depth direction of all subtrees, that is, visits the current vertex first , and then recursively visit each of its neighbor vertices. For each vertex, we must remember whether it has been visited; if not, recursively traverse its neighbor vertices. Code implementation:

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next_vertex in graph[start] - visited:
        dfs(graph, next_vertex, visited)
    return visited

2. Breadth-first traversal (BFS)

Breadth-first traversal is to search the breadth direction of all subtrees, that is, first visit the current vertex, and then visit all its neighbor vertices . For each vertex, we have to remember whether it has been visited; if not, add it to the queue and mark it as visited, and then recurse to its neighbor vertices. Code implementation:

from collections import deque

def bfs(graph, start):
    visited, queue = set(), deque([start])
    visited.add(start)
    while queue:
        vertex = queue.popleft()
        print(vertex)
        for next_vertex in graph[vertex] - visited:
            visited.add(next_vertex)
            queue.append(next_vertex)

3. Graph algorithm

1. Shortest path algorithm

The shortest path algorithm is an algorithm for finding the shortest path between two vertices in a graph. Among them, Dijkstra's algorithm is used for directed acyclic graphs (DAG), and Bellman-Ford algorithm is suitable for any graph.

(1) Dijkstra algorithm

Dijkstra algorithm is used for directed acyclic graphs and can only handle graphs with non-negative weights. The core of this algorithm is the greedy strategy, which assumes that the path is composed of many independent units (nodes), considers the shortest path of each unit one by one, and finds the global shortest path. Code implementation:

import heapq
import sys

def dijkstra(graph, start):
    visited = set()
    distance = {vertex: sys.maxsize for vertex in graph}
    distance[start] = 0
    queue = [(0, start)]
    while queue:
        dist, vertex = heapq.heappop(queue)
        if vertex not in visited:
            visited.add(vertex)
            for neighbor, weight in graph[vertex].items():
                total_distance = dist + weight
                if total_distance < distance[neighbor]:
                    distance[neighbor] = total_distance
                    heapq.heappush(queue, (total_distance, neighbor))
    return distance

(2) Bellman-Ford algorithm

The Bellman-Ford algorithm can handle any graph, including graphs with negative weights. This algorithm solves the shortest path problem through dynamic programming. Code implementation:

import sys

def bellman_ford(graph, start):
    distance = {vertex: sys.maxsize for vertex in graph}
    distance[start] = 0
    for _ in range(len(graph) - 1):
        for vertex in graph:
            for neighbor, weight in graph[vertex].items():
                total_distance = distance[vertex] + weight
                if total_distance < distance[neighbor]:
                    distance[neighbor] = total_distance
    return distance

2. Minimum spanning tree algorithm

The minimum spanning tree problem is to find a subgraph composed of all vertices of an undirected weighted graph such that the weights of all edges in the subgraph The sum of values ​​is the smallest. Among them, Kruskal and Prim algorithms are both classic algorithms to solve this problem.

(1) Kruskal algorithm

Kruskal algorithm is a greedy algorithm. It selects the edge with the smallest weight from all edges and searches for the next edge with the smallest weight in sequence until the number of vertices is equal to until the number of edges matches. Code implementation:

def kruskal(graph):
    parent = {}
    rank = {}
    for vertex in graph:
        parent[vertex] = vertex
        rank[vertex] = 0
    minimum_spanning_tree = set()
    edges = list(graph.edges)
    edges.sort()
    for edge in edges:
        weight, vertex1, vertex2 = edge
        root1 = find(parent, vertex1)
        root2 = find(parent, vertex2)
        if root1 != root2:
            minimum_spanning_tree.add(edge)
            if rank[root1] > rank[root2]:
                parent[root2] = root1
            else:
                parent[root1] = root2
                if rank[root1] == rank[root2]:
                    rank[root2] += 1
    return minimum_spanning_tree

(2) Prim algorithm

Prim algorithm starts by selecting a vertex as the starting point, each time based on the distance between the current spanning tree and other vertices in the graph, and the distance between other vertices and the current The minimum distance of the spanning tree to select a new vertex to add to the spanning tree. Code implementation:

import heapq

def prim(graph, start):
    minimum_spanning_tree = set()
    visited = set(start)
    edges = list(graph[start].items())
    heapq.heapify(edges)
    while edges:
        weight, vertex1 = heapq.heappop(edges)
        if vertex1 not in visited:
            visited.add(vertex1)
            minimum_spanning_tree.add((weight, start, vertex1))
            for vertex2, weight in graph[vertex1].items():
                if vertex2 not in visited:
                    heapq.heappush(edges, (weight, vertex1, vertex2))
    return minimum_spanning_tree

3. Topological sorting algorithm

The topological sorting algorithm is mainly used to deal with logical dependencies in directed acyclic graphs, and is usually used to solve compilation dependencies or task scheduling problems. Code implementation:

from collections import defaultdict

def topological_sort(graph):
    in_degree = defaultdict(int)
    for vertex1 in graph:
        for vertex2 in graph[vertex1]:
            in_degree[vertex2] += 1
    queue = [vertex for vertex in graph if in_degree[vertex] == 0]
    result = []
    while queue:
        vertex = queue.pop()
        result.append(vertex)
        for next_vertex in graph[vertex]:
            in_degree[next_vertex] -= 1
            if in_degree[next_vertex] == 0:
                queue.append(next_vertex)
    if len(result) != len(graph):
        raise ValueError("The graph contains a cycle")
    return result

4. Summary

This article introduces the underlying technology of Python to implement graph algorithms, including graph storage method, traversal method, shortest path algorithm, minimum spanning tree algorithm and topological sorting Algorithms, through specific code examples, let readers understand the implementation ideas and code implementation details of each algorithm. In the actual development process, readers can choose different algorithms according to their own needs to improve the efficiency and quality of the program.

The above is the detailed content of Python underlying technology revealed: how to implement graph algorithms. For more information, please follow other related articles on the PHP Chinese website!