图算法实现

图算法是计算机科学中用于处理图数据结构的一类算法。以下是一些常见的图算法及其实现：

深度优先搜索 (DFS)

深度优先搜索是一种用于遍历或搜索树或图的算法。以下是一个使用 Python 实现的 DFS 算法示例：

def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

广度优先搜索 (BFS)

广度优先搜索是一种用于遍历或搜索树或图的算法。以下是一个使用 Python 实现的 BFS 算法示例：

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)
    return visited

最短路径算法 (Dijkstra)

Dijkstra 算法用于找到图中两点之间的最短路径。以下是一个使用 Python 实现的 Dijkstra 算法示例：

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    return distances

生成树算法 (Prim)

Prim 算法用于找到图中的最小生成树。以下是一个使用 Python 实现的 Prim 算法示例：

import heapq

def prim(graph):
    visited = set()
    min_heap = [(0, 0)]  # (weight, vertex)
    total_weight = 0
    edges = []

    while min_heap:
        weight, vertex = heapq.heappop(min_heap)
        if vertex in visited:
            continue
        visited.add(vertex)
        total_weight += weight
        for neighbor, edge_weight in graph[vertex].items():
            if neighbor not in visited:
                heapq.heappush(min_heap, (edge_weight, neighbor))
                edges.append((vertex, neighbor, edge_weight))
    return total_weight, edges

更多关于图算法的细节和实现，您可以访问本站图算法教程。

图片