摘要：
图数据结构是计算机科学中一种重要的数据结构，广泛应用于网络、图论等领域。本文将围绕图数据结构，探讨最小生成树和最短路径两个经典问题，并分别介绍Prim算法、Kruskal算法、Dijkstra算法和Bellman-Ford算法的实现。
一、
图数据结构由节点（顶点）和边组成，节点表示实体，边表示实体之间的关系。在图数据结构中，最小生成树和最短路径问题是两个重要的应用场景。最小生成树问题要求在无向连通图中，找出一个包含所有节点的最小权值生成树；最短路径问题则要求在图中找到两个节点之间的最短路径。
二、最小生成树
最小生成树问题可以通过Prim算法和Kruskal算法解决。
1. Prim算法
Prim算法是一种基于贪心策略的最小生成树算法。其基本思想是从一个节点开始，逐步扩展生成树，每次选择与已生成树连接的最小权值边。
python
def prim(graph):
n = len(graph)
visited = [False] n
min_edge = [float('inf')] n
min_edge[0] = 0
parent = [-1] n
for i in range(n):
u = min_edge.index(min(min_edge))
visited[u] = True
for v in range(n):
if graph[u][v] and not visited[v] and graph[u][v] < min_edge[v]:
min_edge[v] = graph[u][v]
parent[v] = u
return parent
示例
graph = [
[0, 2, 0, 6, 0],
[2, 0, 3, 8, 5],
[0, 3, 0, 0, 7],
[6, 8, 0, 0, 9],
[0, 5, 7, 9, 0]
]
parent = prim(graph)
print(parent)
2. Kruskal算法
Kruskal算法是一种基于并查集的最小生成树算法。其基本思想是将所有边按照权值从小到大排序，然后依次选择边，如果选择该边不会形成环，则将其加入生成树。
python
def find(parent, i):
if parent[i] == i:
return i
return find(parent, parent[i])
def union(parent, rank, x, y):
xroot = find(parent, x)
yroot = find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
def kruskal(graph):
n = len(graph)
parent = [i for i in range(n)]
rank = [0] n
result = []
for i in range(n):
for j in range(i + 1, n):
if graph[i][j]:
result.append((i, j, graph[i][j]))
result.sort(key=lambda x: x[2])
for edge in result:
x = find(parent, edge[0])
y = find(parent, edge[1])
if x != y:
union(parent, rank, x, y)
result.append(edge)
return result
示例
graph = [
[0, 2, 0, 6, 0],
[2, 0, 3, 8, 5],
[0, 3, 0, 0, 7],
[6, 8, 0, 0, 9],
[0, 5, 7, 9, 0]
]
result = kruskal(graph)
print(result)
三、最短路径
最短路径问题可以通过Dijkstra算法和Bellman-Ford算法解决。
1. Dijkstra算法
Dijkstra算法是一种基于贪心策略的最短路径算法。其基本思想是从源节点开始，逐步扩展最短路径，每次选择与已扩展路径连接的最短权值边。
python
import heapq
def dijkstra(graph, src):
n = len(graph)
min_heap = [(0, src)]
dist = [float('inf')] n
dist[src] = 0
while min_heap:
d, u = heapq.heappop(min_heap)
if d > dist[u]:
continue
for v, weight in enumerate(graph[u]):
if weight and dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
heapq.heappush(min_heap, (dist[v], v))
return dist
示例
graph = [
[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
]
dist = dijkstra(graph, 0)
print(dist)
2. Bellman-Ford算法
Bellman-Ford算法是一种基于动态规划的最短路径算法。其基本思想是从源节点开始，逐步扩展最短路径，每次检查是否有更短的路径。
python
def bellman_ford(graph, src):
n = len(graph)
dist = [float('inf')] n
dist[src] = 0
for _ in range(n - 1):
for u in range(n):
for v, weight in enumerate(graph[u]):
if weight and dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
return dist
示例
graph = [
[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
]
dist = bellman_ford(graph, 0)
print(dist)
四、总结
本文介绍了图数据结构在最小生成树和最短路径问题中的应用。Prim算法和Kruskal算法可以解决最小生成树问题，而Dijkstra算法和Bellman-Ford算法可以解决最短路径问题。在实际应用中，可以根据具体问题选择合适的算法。
Comments NOTHING