Teknologi asas Python didedahkan: cara melaksanakan algoritma graf

Dengan perkembangan berterusan teknologi komputer, teori graf dan algoritma berkaitannya telah menjadi bahagian yang sangat penting dalam bidang komputer. Bagi pengaturcara Python, menguasai teknologi asas ini bukan sahaja dapat meningkatkan kecekapan dan kualiti kod, tetapi juga membantu mengoptimumkan prestasi program dan kecekapan pembangunan.

Artikel ini akan memperkenalkan teknologi asas untuk melaksanakan algoritma graf dalam Python, termasuk kaedah penyimpanan graf, kaedah traversal, algoritma laluan terpendek, algoritma pepohon rentang minimum dan algoritma pengisihan topologi, memfokuskan pada idea pelaksanaan dan contoh kod bagi setiap algoritma.

1. Cara menyimpan graf

Dalam Python, kita boleh menggunakan matriks bersebelahan atau senarai bersebelahan untuk menyimpan graf.

1. Matriks bersebelahan

Matriks bersebelahan ialah matriks dua dimensi di mana baris dan lajur bucu masing-masing sepadan dengan dua bucu. Jika terdapat tepi yang menghubungkan dua bucu, nilai kedudukan ditetapkan kepada 1 atau berat tepinya jika tidak ia ditetapkan kepada 0. Contohnya, berikut ialah contoh matriks bersebelahan:

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

Matriks ini mewakili graf tidak berarah dengan jumlah 4 bucu, antaranya 1, 2, dan 3 disambungkan antara satu sama lain.

2. Senarai bersebelahan

Senarai bersebelahan ialah kamus, di mana setiap kekunci sepadan dengan bucu, dan nilai yang sepadan ialah senarai bucu jiran bucu. Contohnya:

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

Kamus ini mewakili graf tidak terarah yang sama, di mana setiap nilai kunci sepadan dengan bucu, dan nilai yang sepadan dengan bucu ini ialah tepi antara bucu ini dan bucu lain.

2. Kaedah lintasan graf

1. Laluan kedalaman-pertama (DFS)

Perjalanan kedalaman-pertama mencari arah kedalaman semua subpokok, iaitu, mula-mula melawat bucu semasa, dan kemudian melawati setiap bucu jirannya secara rekursif . Untuk setiap bucu, kita mesti ingat sama ada ia telah dilawati, jika tidak, melintasi bucu jiran secara rekursif. Pelaksanaan kod:

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 mencari arah keluasan semua subpokok, iaitu mula-mula melawat bucu semasa, dan kemudian melawat semua bucu jirannya. Untuk setiap bucu, kita perlu ingat sama ada ia telah dilawati, jika tidak, tambahkannya pada baris gilir dan tandakannya sebagai dilawati, dan kemudian ulangi ke bucu jirannya. Pelaksanaan kod:

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. Algoritma graf

1. Algoritma laluan terpendek

Algoritma laluan terpendek ialah algoritma untuk mencari laluan terpendek antara dua bucu dalam graf. Antaranya, algoritma Dijkstra digunakan untuk graf asiklik terarah (DAG), dan algoritma Bellman-Ford sesuai untuk sebarang graf.

(1) Algoritma Dijkstra

Algoritma Dijkstra digunakan untuk graf akiklik terarah dan hanya boleh mengendalikan graf dengan pemberat bukan negatif. Teras algoritma ini ialah strategi tamak, yang menganggap bahawa laluan itu terdiri daripada banyak unit bebas (nod), mempertimbangkan laluan terpendek setiap unit satu demi satu, dan mencari laluan terpendek global. Pelaksanaan kod:

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) Algoritma Bellman-Ford

Algoritma Bellman-Ford boleh mengendalikan sebarang graf, termasuk graf dengan pemberat negatif. Algoritma ini menyelesaikan masalah laluan terpendek melalui pengaturcaraan dinamik. Pelaksanaan kod:

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. Algoritma pokok rentang minimum

Masalah pokok rentang minimum ialah mencari subgraf yang terdiri daripada semua bucu graf berwajaran tidak berarah supaya jumlah pemberat semua tepi dalam subgraf diminimumkan. Antaranya, algoritma Kruskal dan Prim adalah kedua-dua algoritma klasik untuk menyelesaikan masalah ini.

(1) Algoritma Kruskal

Algoritma Kruskal ialah algoritma tamak, yang memilih tepi dengan berat terkecil dari semua tepi dan mencari tepi seterusnya dengan berat terkecil dalam urutan sehingga bilangan bucu sepadan dengan bilangan tepi. Pelaksanaan kod:

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) Algoritma prim

Algoritma prim bermula dengan memilih bucu sebagai titik permulaan, dan memilih satu setiap kali berdasarkan jarak antara pokok rentang semasa dan bucu lain dalam graf, dan jarak minimum antara bucu lain dan pokok rentang semasa. Pelaksanaan kod:

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. Algoritma pengisihan topologi

Algoritma pengisihan topologi digunakan terutamanya untuk menangani kebergantungan logik dalam graf akiklik terarah, dan biasanya digunakan untuk menyelesaikan kebergantungan kompilasi atau masalah penjadualan tugas. Pelaksanaan kod:

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 Ringkasan

Artikel ini memperkenalkan teknologi asas Python untuk melaksanakan algoritma graf, termasuk kaedah penyimpanan graf, kaedah traversal, algoritma laluan terpendek, algoritma pepohon rentang minimum dan algoritma pengisihan topologi. Biarkan pembaca memahami idea pelaksanaan dan butiran pelaksanaan kod bagi setiap algoritma. Dalam proses pembangunan sebenar, pembaca boleh memilih algoritma yang berbeza mengikut keperluan mereka sendiri untuk meningkatkan kecekapan dan kualiti program.

Atas ialah kandungan terperinci Teknologi asas Python didedahkan: cara melaksanakan algoritma graf. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!