算法学习5——图算法

图算法在计算机科学中占有重要地位，广泛应用于网络连接、路径查找、社会网络分析等领域。本文将介绍几种常见的图算法，包括Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法、Kruskal算法和Prim算法，并提供相应的Python代码示例。

图的基本概念

• 图：由节点（顶点）和节点之间的边组成的集合。图可以是有向图或无向图。
• 有向图：边有方向，即边的起点和终点是有序的。
• 无向图：边没有方向，即边的起点和终点是无序的。
• 权重：边可以有一个数值，表示从一个节点到另一个节点的代价或距离。

1. Dijkstra算法（最短路径）

简介：Dijkstra算法用于计算单源最短路径，即从一个起始节点到所有其他节点的最短路径。它适用于非负权重的图，通过贪心策略逐步找到最短路径。

实现过程：

1. 初始化距离数组dist，起始节点到自身的距离为0，其余为无限大。
2. 使用优先队列（最小堆）存储节点及其当前最短距离。
3. 每次从队列中取出距离最小的节点，更新其邻接节点的距离。
4. 重复上述过程，直到所有节点的最短距离都被确定。

Python代码：

import heapq

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

# 示例
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
print(dijkstra(graph, 'A'))

2. Bellman-Ford算法（最短路径）

简介：Bellman-Ford算法用于计算单源最短路径，允许图中存在负权边。该算法通过反复更新边的权重来找到最短路径。

实现过程：

1. 初始化距离数组dist，起始节点到自身的距离为0，其余为无限大。
2. 进行|V|-1次松弛操作，每次遍历所有边并更新距离。
3. 检查是否存在负权回路，如果在第|V|次松弛操作中还能更新距离，说明存在负权回路。

Python代码：

def bellman_ford(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                if dist[node] + weight < dist[neighbor]:
                    dist[neighbor] = dist[node] + weight
    # 检查负权回路
    for node in graph:
        for neighbor, weight in graph[node].items():
            if dist[node] + weight < dist[neighbor]:
                return "Graph contains a negative-weight cycle"
    return dist

# 示例
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
print(bellman_ford(graph, 'A'))

3. Floyd-Warshall算法（全对全最短路径）

简介：Floyd-Warshall算法用于计算所有节点之间的最短路径。它利用动态规划的思想，通过逐步更新路径长度来找到最短路径。

实现过程：

1. 初始化距离矩阵dist，对角线为0，其余为边的权重或无限大。
2. 对每一对节点，检查通过中间节点的路径是否更短，若是则更新距离。
3. 重复上述过程，直到所有节点之间的最短路径都被确定。

Python代码：

def floyd_warshall(graph):
    nodes = list(graph.keys())
    dist = {node: {node2: float('inf') for node2 in nodes} for node in nodes}
    for node in nodes:
        dist[node][node] = 0
    for node in graph:
        for neighbor, weight in graph[node].items():
            dist[node][neighbor] = weight
    for k in nodes:
        for i in nodes:
            for j in nodes:
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

# 示例
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
print(floyd_warshall(graph))

4. Kruskal算法（最小生成树）

简介：Kruskal算法用于计算最小生成树（MST），即连接所有节点且总权重最小的树。该算法适用于无向加权图，通过贪心策略，每次选择权重最小的边，保证不形成环。

实现过程：

1. 初始化每个节点的父节点和秩（用于实现并查集）。
2. 按权重升序排序所有边。
3. 依次选择最小权重的边，若不形成环则加入生成树。
4. 使用并查集检测环的形成。

Python代码：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

def kruskal(edges, n):
    uf = UnionFind(n)
    mst = []
    edges.sort(key=lambda x: x[2])  # 按权重排序边
    for u, v, weight in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, weight))
    return mst

# 示例
edges = [
    (0, 1, 1),
    (0, 2, 4),
    (1, 2, 2),
    (1, 3, 5),
    (2, 3, 1)
]
n = 4  # 节点数量
print(kruskal(edges, n))

5. Prim算法（最小生成树）

简介：Prim算法也是一种用于计算最小生成树的算法，适用于连通无向加权图。它通过贪心策略，每次选择连接生成树和未访问节点的最小权重边。

实现过程：

1. 初始化距离数组dist，起始节点到自身的距离为0，其余为无限大。
2. 使用优先队列（最小堆）存储节点及其当前最短距离。
3. 每次从队列中取出距离最小的节点，加入生成树，并更新其邻接节点的距离。
4. 重复上述过程，直到所有节点都被访问。

Python代码：

import heapq

def prim(graph, start):
    mst = []
    visited = set()
    min_heap = [(0, start, None)]  # (权重, 当前节点, 父节点)
    while min_heap:
        weight, node, parent = heapq.heappop(min_heap)
        if node not in visited:
            visited.add(node)
            if parent is not None:
                mst.append((parent, node, weight))
            for neighbor, edge_weight in graph[node].items():
                if neighbor not in visited:
                    heapq.heappush(min_heap, (edge_weight, neighbor, node))
    return mst

# 示例
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
print(prim(graph, 'A'))

这一章的图算法和上一章的动态规划，都在运筹学中运用较多。是运筹优化和决策的不二之选。