Die zugrunde liegende Python-Technologie enthüllte: wie man Diagrammalgorithmen implementiert

Mit der kontinuierlichen Weiterentwicklung der Computertechnologie sind die Graphentheorie und die damit verbundenen Algorithmen zu einem sehr wichtigen Teil des Computerbereichs geworden. Für Python-Programmierer kann die Beherrschung dieser zugrunde liegenden Technologien nicht nur die Effizienz und Qualität des Codes verbessern, sondern auch dazu beitragen, die Programmleistung und Entwicklungseffizienz zu optimieren.

In diesem Artikel wird die zugrunde liegende Technologie zur Implementierung von Diagrammalgorithmen in Python vorgestellt, einschließlich Diagrammspeichermethoden, Traversierungsmethoden, Algorithmen für den kürzesten Pfad, Algorithmen für minimale Spannbäume und topologische Sortieralgorithmen, wobei der Schwerpunkt auf den Implementierungsideen und Codebeispielen jedes Algorithmus liegt.

1. So speichern Sie Diagramme

In Python können wir Adjazenzmatrizen oder Adjazenzlisten zum Speichern von Diagrammen verwenden.

1. Adjazenzmatrix

Die Adjazenzmatrix ist eine zweidimensionale Matrix, in der die Zeilen und Spalten der Scheitelpunkte jeweils zwei Scheitelpunkten entsprechen. Wenn es eine Kante gibt, die zwei Scheitelpunkte verbindet, wird der Positionswert auf 1 oder dessen Kantengewicht gesetzt, andernfalls wird er auf 0 gesetzt. Das Folgende ist beispielsweise ein Beispiel für eine Adjazenzmatrix:

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

Diese Matrix stellt einen ungerichteten Graphen mit insgesamt 4 Eckpunkten dar, von denen 1, 2 und 3 miteinander verbunden sind.

2. Adjazenzliste

Die Adjazenzliste ist ein Wörterbuch, in dem jeder Schlüssel einem Scheitelpunkt entspricht und der entsprechende Wert die Liste der Nachbarscheitelpunkte des Scheitelpunkts ist. Beispiel:

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

Dieses Wörterbuch stellt denselben ungerichteten Graphen dar, in dem jeder Schlüsselwert einem Scheitelpunkt entspricht und der diesem Scheitelpunkt entsprechende Wert die Kante zwischen diesem Scheitelpunkt und anderen Scheitelpunkten ist.

2. Graph-Traversal-Methode

1. Depth-First-Traversal (DFS)

Depth-First-Traversal durchsucht die Tiefenrichtung aller Teilbäume, d. h. besucht zuerst den aktuellen Scheitelpunkt und besucht dann rekursiv jeden seiner Nachbarscheitelpunkte . Für jeden Scheitelpunkt müssen wir uns merken, ob er besucht wurde. Wenn nicht, müssen wir seine Nachbarscheitelpunkte rekursiv durchlaufen. Code-Implementierung:

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. Breitenorientierte Durchquerung (BFS)

Breitenorientierte Durchquerung durchsucht die Breitenrichtung aller Teilbäume, dh besucht zuerst den aktuellen Scheitelpunkt und dann alle seine Nachbarscheitelpunkte. Für jeden Scheitelpunkt müssen wir uns merken, ob er besucht wurde. Wenn nicht, fügen wir ihn der Warteschlange hinzu, markieren ihn als besucht und kehren dann zu seinen Nachbarscheitelpunkten zurück. Code-Implementierung:

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. Diagrammalgorithmus

1. Algorithmus für den kürzesten Pfad

Der Algorithmus für den kürzesten Pfad ist ein Algorithmus zum Finden des kürzesten Pfads zwischen zwei Eckpunkten in einem Diagramm. Unter diesen wird der Dijkstra-Algorithmus für gerichtete azyklische Graphen (DAG) verwendet, und der Bellman-Ford-Algorithmus ist für jeden Graphen geeignet.

(1) Dijkstras Algorithmus

Dijkstras Algorithmus wird für gerichtete azyklische Graphen verwendet und kann nur Graphen mit nicht negativen Gewichten verarbeiten. Der Kern dieses Algorithmus ist die Greedy-Strategie, die davon ausgeht, dass der Pfad aus vielen unabhängigen Einheiten (Knoten) besteht, den kürzesten Pfad jeder Einheit einzeln betrachtet und den globalen kürzesten Pfad findet. Code-Implementierung:

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-Algorithmus

Der Bellman-Ford-Algorithmus kann jedes Diagramm verarbeiten, einschließlich Diagrammen mit negativen Gewichten. Dieser Algorithmus löst das Problem des kürzesten Weges durch dynamische Programmierung. Code-Implementierung:

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-Algorithmus

Das Minimum-Spanning-Tree-Problem besteht darin, einen Teilgraphen zu finden, der aus allen Eckpunkten eines ungerichteten gewichteten Graphen besteht, sodass die Summe der Gewichte aller Kanten im Teilgraphen minimiert wird. Unter diesen sind der Kruskal- und der Prim-Algorithmus klassische Algorithmen zur Lösung dieses Problems.

(1) Kruskal-Algorithmus

Der Kruskal-Algorithmus ist ein gieriger Algorithmus, der aus allen Kanten die Kante mit dem geringsten Gewicht auswählt und der Reihe nach nach der nächsten Kante mit dem kleinsten Gewicht sucht, bis die Anzahl der Scheitelpunkte mit der Anzahl der Kanten übereinstimmt. Code-Implementierung:

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-Algorithmus

Der Prim-Algorithmus beginnt mit der Auswahl eines Scheitelpunkts als Startpunkt und wählt jedes Mal einen Scheitelpunkt basierend auf dem Abstand zwischen dem aktuellen Spanning Tree und anderen Scheitelpunkten im Diagramm sowie dem Mindestabstand aus zwischen anderen Scheitelpunkten und dem aktuellen Spannbaum. Neue Scheitelpunkte werden dem Spannbaum hinzugefügt. Code-Implementierung:

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. Topologischer Sortieralgorithmus

Der topologische Sortieralgorithmus wird hauptsächlich zur Behandlung logischer Abhängigkeiten in gerichteten azyklischen Diagrammen verwendet und wird normalerweise zur Lösung von Kompilierungsabhängigkeiten oder Aufgabenplanungsproblemen verwendet. Code-Implementierung:

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. Zusammenfassung

In diesem Artikel wird anhand spezifischer Codebeispiele die zugrunde liegende Technologie von Python zur Implementierung von Diagrammalgorithmen vorgestellt, einschließlich der Diagrammspeichermethode, der Durchquerungsmethode, des Algorithmus für den kürzesten Pfad, des Minimum-Spanning-Tree-Algorithmus und des topologischen Sortieralgorithmus. Lassen Sie die Leser die Implementierungsideen und Codeimplementierungsdetails jedes Algorithmus verstehen. Im eigentlichen Entwicklungsprozess können Leser je nach Bedarf verschiedene Algorithmen auswählen, um die Effizienz und Qualität des Programms zu verbessern.

Das obige ist der detaillierte Inhalt vonDie zugrunde liegende Python-Technologie enthüllte: wie man Diagrammalgorithmen implementiert. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!