图算法在计算机科学中占有重要地位,广泛应用于网络连接、路径查找、社会网络分析等领域。本文将介绍几种常见的图算法,包括Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法、Kruskal算法和Prim算法,并提供相应的Python代码示例。
图的基本概念
- 图:由节点(顶点)和节点之间的边组成的集合。图可以是有向图或无向图。
- 有向图:边有方向,即边的起点和终点是有序的。
- 无向图:边没有方向,即边的起点和终点是无序的。
- 权重:边可以有一个数值,表示从一个节点到另一个节点的代价或距离。
1. Dijkstra算法(最短路径)
简介:Dijkstra算法用于计算单源最短路径,即从一个起始节点到所有其他节点的最短路径。它适用于非负权重的图,通过贪心策略逐步找到最短路径。
实现过程:
- 初始化距离数组
dist
,起始节点到自身的距离为0,其余为无限大。 - 使用优先队列(最小堆)存储节点及其当前最短距离。
- 每次从队列中取出距离最小的节点,更新其邻接节点的距离。
- 重复上述过程,直到所有节点的最短距离都被确定。
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算法用于计算单源最短路径,允许图中存在负权边。该算法通过反复更新边的权重来找到最短路径。
实现过程:
- 初始化距离数组
dist
,起始节点到自身的距离为0,其余为无限大。 - 进行|V|-1次松弛操作,每次遍历所有边并更新距离。
- 检查是否存在负权回路,如果在第|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算法用于计算所有节点之间的最短路径。它利用动态规划的思想,通过逐步更新路径长度来找到最短路径。
实现过程:
- 初始化距离矩阵
dist
,对角线为0,其余为边的权重或无限大。 - 对每一对节点,检查通过中间节点的路径是否更短,若是则更新距离。
- 重复上述过程,直到所有节点之间的最短路径都被确定。
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),即连接所有节点且总权重最小的树。该算法适用于无向加权图,通过贪心策略,每次选择权重最小的边,保证不形成环。
实现过程:
- 初始化每个节点的父节点和秩(用于实现并查集)。
- 按权重升序排序所有边。
- 依次选择最小权重的边,若不形成环则加入生成树。
- 使用并查集检测环的形成。
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算法也是一种用于计算最小生成树的算法,适用于连通无向加权图。它通过贪心策略,每次选择连接生成树和未访问节点的最小权重边。
实现过程:
- 初始化距离数组
dist
,起始节点到自身的距离为0,其余为无限大。 - 使用优先队列(最小堆)存储节点及其当前最短距离。
- 每次从队列中取出距离最小的节点,加入生成树,并更新其邻接节点的距离。
- 重复上述过程,直到所有节点都被访问。
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'))
这一章的图算法和上一章的动态规划,都在运筹学中运用较多。是运筹优化和决策的不二之选。