La technologie sous-jacente Python révélée : comment implémenter des algorithmes graphiques

Avec le développement continu de la technologie informatique, la théorie des graphes et ses algorithmes associés sont devenus une partie très importante du domaine informatique. Pour les programmeurs Python, la maîtrise de ces technologies sous-jacentes peut non seulement améliorer l’efficacité et la qualité du code, mais également contribuer à optimiser les performances du programme et l’efficacité du développement.

Cet article présentera la technologie sous-jacente à l'implémentation d'algorithmes de graphes en Python, y compris les méthodes de stockage de graphes, les méthodes de traversée, les algorithmes de chemin le plus court, les algorithmes d'arbre couvrant minimum et les algorithmes de tri topologique, en se concentrant sur les idées d'implémentation et les exemples de code de chaque algorithme.

1. Comment stocker des graphiques

En Python, nous pouvons utiliser des matrices de contiguïté ou des listes de contiguïté pour stocker des graphiques.

1. Matrice de contiguïté

La matrice de contiguïté est une matrice bidimensionnelle dans laquelle les lignes et les colonnes des sommets correspondent respectivement à deux sommets. S'il y a une arête reliant deux sommets, la valeur de position est définie sur 1 ou son poids d'arête est défini sur 0 ; Par exemple, voici un exemple de matrice de contiguïté :

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

Cette matrice représente un graphe non orienté avec un total de 4 sommets, parmi lesquels 1, 2 et 3 sont connectés les uns aux autres.

2. Liste d'adjacence

La liste d'adjacence est un dictionnaire, où chaque clé correspond à un sommet, et la valeur correspondante est la liste des sommets voisins du sommet. Par exemple :

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

Ce dictionnaire représente le même graphe non orienté, dans lequel chaque valeur clé correspond à un sommet, et la valeur correspondant à ce sommet est l'arête entre ce sommet et les autres sommets.

2. Méthode de parcours graphique

1. Parcours en profondeur d'abord (DFS)

Le parcours en profondeur recherche la direction de la profondeur de tous les sous-arbres, c'est-à-dire qu'il visite d'abord le sommet actuel, puis visite récursivement chacun de ses sommets voisins. . Pour chaque sommet, il faut se rappeler s'il a été visité ; sinon, parcourir récursivement ses sommets voisins. Implémentation du code :

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. Traversée en largeur en premier (BFS)

La traversée en largeur recherche la direction en largeur de tous les sous-arbres, c'est-à-dire qu'elle visite d'abord le sommet actuel, puis visite tous ses sommets voisins. Pour chaque sommet, nous devons nous rappeler s'il a été visité ; sinon, l'ajouter à la file d'attente et le marquer comme visité, puis revenir à ses sommets voisins. Implémentation du code :

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. Algorithme de graphique

1. Algorithme du chemin le plus court

L'algorithme du chemin le plus court est un algorithme permettant de trouver le chemin le plus court entre deux sommets d'un graphique. Parmi eux, l'algorithme de Dijkstra est utilisé pour les graphes acycliques dirigés (DAG), et l'algorithme de Bellman-Ford convient à n'importe quel graphe.

(1) L'algorithme de Dijkstra

L'algorithme de Dijkstra est utilisé pour les graphiques acycliques orientés et ne peut gérer que des graphiques avec des poids non négatifs. Le cœur de cet algorithme est la stratégie gloutonne, qui suppose que le chemin est composé de nombreuses unités indépendantes (nœuds), considère le chemin le plus court de chaque unité une par une et trouve le chemin le plus court global. Implémentation du code :

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) Algorithme de Bellman-Ford

L'algorithme de Bellman-Ford peut gérer n'importe quel graphique, y compris les graphiques avec des poids négatifs. Cet algorithme résout le problème du chemin le plus court grâce à une programmation dynamique. Implémentation du code :

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. Algorithme d'arbre couvrant minimum

Le problème de l'arbre couvrant minimum est de trouver un sous-graphe composé de tous les sommets d'un graphe pondéré non orienté de telle sorte que la somme des poids de toutes les arêtes du sous-graphe soit minimisée. Parmi eux, les algorithmes Kruskal et Prim sont tous deux des algorithmes classiques pour résoudre ce problème.

(1) Algorithme de Kruskal

L'algorithme de Kruskal est un algorithme glouton, qui sélectionne l'arête avec le plus petit poids parmi toutes les arêtes et recherche l'arête suivante avec le plus petit poids dans la séquence jusqu'à ce que le nombre de sommets corresponde au nombre d'arêtes. Implémentation du code :

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) Algorithme Prim

L'algorithme Prim commence par sélectionner un sommet comme point de départ, et à chaque fois il en sélectionne un en fonction de la distance entre l'arbre couvrant actuel et les autres sommets du graphique, et le minimum distance entre les autres sommets et l'arbre couvrant actuel. De nouveaux sommets sont ajoutés à l'arbre couvrant. Implémentation du code :

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. Algorithme de tri topologique

L'algorithme de tri topologique est principalement utilisé pour traiter les dépendances logiques dans les graphes acycliques orientés, et est généralement utilisé pour résoudre les dépendances de compilation ou les problèmes de planification de tâches. Implémentation du code :

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

IV. Résumé

Cet article présente la technologie sous-jacente de Python pour implémenter des algorithmes de graphe, y compris la méthode de stockage de graphe, la méthode de parcours, l'algorithme du chemin le plus court, l'algorithme d'arbre couvrant minimum et l'algorithme de tri topologique à travers des exemples de code spécifiques. Laissez les lecteurs comprendre les idées d’implémentation et les détails d’implémentation du code de chaque algorithme. Dans le processus de développement actuel, les lecteurs peuvent choisir différents algorithmes en fonction de leurs propres besoins pour améliorer l'efficacité et la qualité du programme.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!