基于图的相关算法实现

基于图的相关算法有很多，下面介绍一些常见的算法及其实现方式。

1. 最短路径算法

最短路径算法用于寻找两个节点之间的最短路径，常用的算法有Dijkstra算法和Bellman-Ford算法。其中，Dijkstra算法适用于边权值为非负数的图，而Bellman-Ford算法适用于边权值可以为负数的图。

Dijkstra算法的实现：

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    while pq:
        curr_distance, curr_node = heapq.heappop(pq)
        if curr_distance > distances[curr_node]:
            continue
        for neighbor, weight in graph[curr_node].items():
            distance = curr_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    return distances

Bellman-Ford算法的实现：

def bellman_ford(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                distance = distances[node] + weight
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
    for node in graph:
        for neighbor, weight in graph[node].items():
            distance = distances[node] + weight
            if distance < distances[neighbor]:
                raise ValueError("Negative weight cycle detected.")
    return distances

2. 最小生成树算法

最小生成树算法用于寻找一棵树，使得树上所有边的权值之和最小。常用的算法有Prim算法和Kruskal算法。

Prim算法的实现：

import heapq

def prim(graph, start):
    visited = {node: False for node in graph}
    visited[start] = True
    edges = [(weight, start, neighbor) for neighbor, weight in graph[start].items()]
    heapq.heapify(edges)
    mst_weight = 0
    mst_edges = []
    while edges:
        weight, curr_node, neighbor = heapq.heappop(edges)
        if visited[neighbor]:
            continue
        visited[neighbor] = True
        mst_edges.append((curr_node, neighbor))
        mst_weight += weight
        for next_neighbor, weight in graph[neighbor].items():
            if not visited[next_neighbor]:
                heapq.heappush(edges, (weight, neighbor, next_neighbor))
    return mst_edges, mst_weight

Kruskal算法的实现：

def kruskal(graph):
    edges = [(weight, node, neighbor) for node in graph for neighbor, weight in graph[node].items()]
    edges.sort()
    parent = {node: node for node in graph}
    mst_weight = 0
    mst_edges = []
    for weight, node, neighbor in edges:
        root_node = find(parent, node)
        root_neighbor = find(parent, neighbor)
        if root_node != root_neighbor:
            mst_edges.append((node, neighbor))
            mst_weight += weight
            parent[root_node] = root_neighbor
    return mst_edges, mst_weight

def find(parent, node):
    while parent[node] != node:
        node = parent[node]
    return node

3. 拓扑排序算法

拓扑排序算法用于对有向无环图进行排序，使得所有的有向边从排在前面的节点指向排在后面的节点。常用的算法有Kahn算法和DFS算法。

Kahn算法的实现：

from collections import deque

def kahn(graph):
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    queue = deque(node for node in graph if in_degree[node] == 0)
    topological_order = []
    while queue:
        node = queue.popleft()
        topological_order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    if len(topological_order) != len(graph):
        raise ValueError("Graph contains a cycle.")
    return topological_order

DFS算法的实现：

def dfs(graph):
    visited = {node: False for node in graph}
    topological_order = []
    def dfs_visit(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs_visit(neighbor)
        topological_order.append(node)
    for node in graph:
        if not visited[node]:
            dfs_visit(node)
    return list(reversed(topological_order))

这些算法只是常见的基于图的算法，实际上还有很多其他的算法，如最大流算法、二分图匹配算法等等。