Python の基礎となるテクノロジーが明らかに: グラフ アルゴリズムの実装方法

コンピュータ技術の継続的な発展に伴い、グラフ理論とその関連アルゴリズムはコンピュータ分野の非常に重要な部分になりました。 Python プログラマーにとって、これらの基礎となるテクノロジーを習得すると、コードの効率と品質が向上するだけでなく、プログラムのパフォーマンスと開発効率の最適化にも役立ちます。

この記事では、グラフ保存方法、トラバーサル方法、最短パス アルゴリズム、最小スパニング ツリー アルゴリズム、トポロジカル ソート アルゴリズムなど、Python のグラフ アルゴリズムの基盤となるテクノロジを、実装アイデアとコード例に焦点を当てて紹介します。それぞれのアルゴリズム。

1. グラフの保存方法

Python では、隣接行列または隣接リストを使用してグラフを保存できます。

1. 隣接行列

隣接行列は、頂点の行と列がそれぞれ 2 つの頂点に対応する 2 次元行列です。 2 つの頂点を接続するエッジがある場合、位置の値は 1 またはそのエッジの重みに設定され、それ以外の場合は 0 に設定されます。たとえば、次は隣接行列の例です。

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

この行列は、合計 4 つの頂点を持つ無向グラフを表し、そのうちの 1、2、および 3 はエッジによって互いに接続されています。

2. 隣接リスト

隣接リストは辞書であり、各キーは頂点に対応し、対応する値は頂点の隣接頂点のリストです。例:

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

このディクショナリは同じ無向グラフを表します。各キー値は頂点に対応し、この頂点に対応する値はこの頂点と他の頂点の間のエッジです。

2. グラフ走査方法

1. 深さ優先走査 (DFS)

深さ優先走査では、すべてのサブツリーの深さ方向を検索します。つまり、現在のサブツリーを訪問します。最初に頂点を訪問し、次にその隣接する頂点のそれぞれを再帰的に訪問します。各頂点について、その頂点が訪問されたかどうかを記憶する必要があり、訪問されていない場合は、隣接する頂点を再帰的に走査します。コード実装:

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. 幅優先トラバーサル (BFS)

幅優先トラバーサルは、すべてのサブツリーの幅方向を検索することです。つまり、最初に現在の頂点にアクセスし、次に、すべての隣接する頂点を訪問します。各頂点について、その頂点が訪問されているかどうかを記憶する必要があります。訪問されていない場合は、その頂点をキューに追加して訪問済みとしてマークし、隣接する頂点を再帰的に調べます。コード実装:

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. グラフ アルゴリズム

1. 最短パス アルゴリズム

最短パス アルゴリズムは、グラフ内の 2 つの頂点間の最短パスを見つけるアルゴリズムです。このうち、ダイクストラのアルゴリズムは有向非巡回グラフ (DAG) に使用され、ベルマン・フォードのアルゴリズムはあらゆるグラフに適しています。

(1) ダイクストラ アルゴリズム

ダイクストラ アルゴリズムは、有向非巡回グラフに使用され、非負の重みを持つグラフのみを処理できます。このアルゴリズムの中心となるのは、パスが多数の独立したユニット (ノード) で構成されていると仮定し、各ユニットの最短パスを 1 つずつ考慮し、全体的な最短パスを見つける貪欲戦略です。コード実装:

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 アルゴリズム

Bellman-Ford アルゴリズムは、負の重みを持つグラフを含むあらゆるグラフを処理できます。このアルゴリズムは、動的計画法を通じて最短経路問題を解決します。コード実装:

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. 最小スパニング ツリー アルゴリズム

最小スパニング ツリー問題は、無向重み付きグラフのすべての頂点で構成されるサブグラフを見つけ、サブグラフ 値の合計が最小になります。その中でも、Kruskal アルゴリズムと Prim アルゴリズムは、どちらもこの問題を解決するための古典的なアルゴリズムです。

(1) クラスカルアルゴリズム

クラスカルアルゴリズムは貪欲なアルゴリズムであり、すべてのエッジから最小の重みを持つエッジを選択し、次の最小の重みを持つエッジを順番に探索します。エッジの数が一致するまで、頂点の数は と等しくなります。コード実装:

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) プリム アルゴリズム

プリム アルゴリズムは、現在のスパニング ツリーとグラフ内の他の頂点の間の距離に基づいて、頂点を開始点として選択することから始まります。 、および他の頂点と現在の頂点間の距離 スパニング ツリーに追加する新しい頂点を選択するためのスパニング ツリーの最小距離。コード実装:

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. トポロジカル ソート アルゴリズム

トポロジカル ソート アルゴリズムは、主に有向非巡回グラフの論理依存関係を処理するために使用され、通常はコンパイルの依存関係やタスク スケジューリングの問題を解決するために使用されます。 。コード実装:

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. 概要

この記事では、グラフ ストレージ方法、トラバーサル方法、最短パス アルゴリズム、最小スパニング ツリー アルゴリズム、トポロジカル アルゴリズムなどのグラフ アルゴリズムを実装するための Python の基礎となるテクノロジを紹介します。ソート アルゴリズムでは、具体的なコード例を通じて、読者が各アルゴリズムの実装アイデアとコード実装の詳細を理解できるようにします。実際の開発プロセスでは、読者は自分のニーズに応じてさまざまなアルゴリズムを選択し、プログラムの効率と品質を向上させることができます。

以上がPython の基礎となるテクノロジーが明らかに: グラフ アルゴリズムの実装方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。