【第九天】零基础入门刷题Python-算法篇-数据结构与算法的介绍-六种常见的图论算法（持续更新）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言
一、Python数据结构与算法的详细介绍
- 1.Python中的常用的图论算法
- - 2. 图论算法
  - 3.详细的图论算法
  - - 1）深度优先搜索（DFS）
    - 2）广度优先搜索（BFS）
    - 3）Dijkstra算法
    - 4）Prim算法
    - 5）Kruskal算法
    - 6）Floyd-Warshall算法
总结

前言

提示：这里可以添加本文要记录的大概内容：

第一天Python数据结构与算法的详细介绍
第二天五种常见的排序算法
第三天两种常见的搜索算法
第四天两种常见的递归算法
第五天一种常见的动态规划算法
第六天一种常见的贪心算法
第七天一种常见的分治算法
第八天一种常见的回溯算法
第九天六种常见的图论算法
第十天两种常见的字符串算法

提示：以下是本篇文章正文内容，下面案例可供参考

一、Python数据结构与算法的详细介绍

1.Python中的常用的图论算法

以下是Python中的一些常用算法：

2. 图论算法

图论算法：

深度优先搜索（DFS）：
用途：用于图的遍历或路径查找。
时间复杂度：O(V+E)，其中V是顶点数，E是边数。
空间复杂度：O(V)（递归栈空间）。
广度优先搜索（BFS）：
用途：用于图的遍历或最短路径查找（无权图）。
时间复杂度：O(V+E)。
空间复杂度：O(V)（队列空间）。
Dijkstra算法：
用途：用于计算单源最短路径（有权图）。
时间复杂度：O(V^2)（朴素实现）或O((V+E) log V)（优先队列实现）。
空间复杂度：O(V)。
最小生成树算法：
Prim算法：
用途：用于求解最小生成树。
时间复杂度：
使用邻接矩阵：O(V^2)。
使用斐波那契堆等数据结构：O(E log V)。
空间复杂度：根据具体实现而定，通常与顶点数和边的数量相关。
Kruskal算法：
用途：用于求解最小生成树。
时间复杂度：O(E log E)，其中E是边的数量。
空间复杂度：O(E)（存储边）和O(V)（并查集数据结构）。
Floyd-Warshall算法：
用途：用于计算所有顶点对之间的最短路径（有权图）。
时间复杂度：O(V^3)，其中V是顶点数。注意这里的复杂度是立方，与上述算法不同。
空间复杂度：O(V^2)（存储距离矩阵）。

3.详细的图论算法

1）深度优先搜索（DFS）

# 图的表示使用邻接表
graph = {'A': ['B', 'C'],'B': ['A', 'D', 'E'],'C': ['A', 'F'],'D': ['B'],'E': ['B', 'F'],'F': ['C', 'E']
}# 深度优先搜索的递归实现
def dfs(graph, start, visited=None):if visited is None:visited = set()visited.add(start)print(start)  # 访问节点，这里简单打印出来for neighbor in graph[start]:if neighbor not in visited:dfs(graph, neighbor, visited)return visited# 从节点 'A' 开始进行深度优先搜索
dfs(graph, 'A')

2）广度优先搜索（BFS）

from collections import deque# 图的表示使用邻接表
graph = {'A': ['B', 'C'],'B': ['A', 'D', 'E'],'C': ['A', 'F'],'D': ['B'],'E': ['B', 'F'],'F': ['C', 'E']
}# 广度优先搜索的实现
def bfs(graph, start):visited = set()  # 用于跟踪访问过的节点queue = deque([start])  # 初始化队列，将起始节点入队while queue:vertex = queue.popleft()  # 从队列左侧出队一个节点if vertex not in visited:visited.add(vertex)  # 标记该节点为已访问print(vertex)  # 访问节点，这里简单打印出来# 将该节点的所有未访问过的相邻节点入队for neighbor in graph[vertex]:if neighbor not in visited:queue.append(neighbor)# 从节点 'A' 开始进行广度优先搜索
bfs(graph, 'A')

3）Dijkstra算法

import heapq# 图的表示使用邻接表，其中权重作为边的值
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}
}def dijkstra(graph, start):# 初始化距离字典，所有顶点的距离都设为无穷大（float('inf')），源点的距离设为0distances = {vertex: float('inf') for vertex in graph}distances[start] = 0# 优先队列，存储（距离，顶点）对，初始时只包含源点（0，start）priority_queue = [(0, start)]heapq.heapify(priority_queue)# 已访问顶点集合，用于避免重复处理visited = set()while priority_queue:# 弹出当前距离最小的顶点current_distance, current_vertex = heapq.heappop(priority_queue)# 如果该顶点已被访问过，则跳过if current_vertex in visited:continue# 标记该顶点为已访问visited.add(current_vertex)# 更新相邻顶点的距离for neighbor, weight in graph[current_vertex].items():distance = current_distance + weight# 如果通过当前顶点到达相邻顶点的距离更短，则更新距离if distance < distances[neighbor]:distances[neighbor] = distanceheapq.heappush(priority_queue, (distance, neighbor))return distances# 从顶点 'A' 开始进行Dijkstra算法求解最短路径
start_vertex = 'A'
shortest_paths = dijkstra(graph, start_vertex)# 打印结果
for vertex, distance in shortest_paths.items():print(f"从 {start_vertex} 到 {vertex} 的最短距离是 {distance}")

4）Prim算法

import heapqdef prim(graph):start_vertex = next(iter(graph))  # 选择任意一个顶点作为起始点mst = []visited = set()min_heap = [(0, start_vertex, None)]  # (权重, 当前顶点, 前驱顶点)while min_heap:weight, current_vertex, prev_vertex = heapq.heappop(min_heap)if current_vertex in visited:continuevisited.add(current_vertex)if prev_vertex is not None:mst.append((prev_vertex, current_vertex, weight))for neighbor, edge_weight in graph[current_vertex].items():if neighbor not in visited:heapq.heappush(min_heap, (edge_weight, neighbor, current_vertex))return mst# 图的表示（邻接表）
graph = {'A': {'B': 1, 'C': 3},'B': {'A': 1, 'C': 1, 'D': 6},'C': {'A': 3, 'B': 1, 'D': 2},'D': {'B': 6, 'C': 2}
}print("Prim's MST:", prim(graph))

5）Kruskal算法

class DisjointSet:def __init__(self, vertices):self.parent = {v: v for v in vertices}self.rank = {v: 0 for v in vertices}def find(self, item):if self.parent[item] != item:self.parent[item] = self.find(self.parent[item])return self.parent[item]def union(self, set1, set2):root1 = self.find(set1)root2 = self.find(set2)if root1 != root2:if self.rank[root1] > self.rank[root2]:self.parent[root2] = root1elif self.rank[root1] < self.rank[root2]:self.parent[root1] = root2else:self.parent[root2] = root1self.rank[root1] += 1def kruskal(graph):edges = []for u in graph:for v, weight in graph[u].items():if u < v:  # 避免重复边（无向图）edges.append((weight, u, v))edges.sort()  # 按权重排序vertices = set(u for u in graph for v in graph[u])disjoint_set = DisjointSet(vertices)mst = []for weight, u, v in edges:if disjoint_set.find(u) != disjoint_set.find(v):disjoint_set.union(u, v)mst.append((u, v, weight))return mst# 图的表示（邻接表）
graph = {'A': {'B': 1, 'C': 3},'B': {'A': 1, 'C': 1, 'D': 6},'C': {'A': 3, 'B': 1, 'D': 2},'D': {'B': 6, 'C': 2}
}print("Kruskal's MST:", kruskal(graph))

6）Floyd-Warshall算法

def floyd_warshall(graph):# 初始化距离矩阵，使用无穷大表示不可达的顶点对num_vertices = len(graph)dist = [[float('inf')] * num_vertices for _ in range(num_vertices)]# 设置顶点到自身的距离为0for i in range(num_vertices):dist[i][i] = 0# 设置图的边权重for u in range(num_vertices):for v, weight in graph[u].items():v = list(graph.keys()).index(v)  # 将顶点转换为索引dist[u][v] = weight# Floyd-Warshall算法核心for k in range(num_vertices):for i in range(num_vertices):for j in range(num_vertices):if dist[i][k] != float('inf') and dist[k][j] != float('inf') and dist[i][k] + dist[k][j] < dist[i][j]:dist[i][j] = dist[i][k] + dist[k][j]# 输出结果for u in range(num_vertices):for v in range(num_vertices):if dist[u][v] == float('inf'):print(f"从顶点 {u} 到顶点 {v} 不可达", end='\t')else:print(f"从顶点 {u} 到顶点 {v} 的最短距离是 {dist[u][v]}", end='\t')print()# 图的表示（邻接表转换为索引表示）
# 注意：这里为了简化，我们假设顶点已经按字母顺序排列，并可以直接用字母的ASCII码减去'A'的ASCII码来作为索引
# 在实际应用中，你可能需要一个映射来将顶点名称转换为索引
graph = [{'B': 1, 'C': 3},{'A': 1, 'C': 1, 'D': 6},{'A': 3, 'B': 1, 'D': 2},{'B': 6, 'C': 2}
]# 由于Floyd-Warshall算法需要顶点索引，而上面的graph表示是基于顶点名称的邻接表，
# 在这里我们直接按字母顺序和数量假设了顶点索引，并跳过了转换步骤。
# 在实际应用中，请确保图的表示与算法输入要求相匹配。# 调用Floyd-Warshall算法
floyd_warshall(graph)