健身网站设计模板下载,广州贝勤网络科技有限公司,济南旅游网页设计,织梦建设网站需要什么软件提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、Python数据结构与算法的详细介绍1.Python中的常用的图论算法2. 图论算法3.详细的图论算法1#xff09;深度优先搜索#xff08;DFS#xff09;2#xf… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、Python数据结构与算法的详细介绍1.Python中的常用的图论算法2. 图论算法3.详细的图论算法1深度优先搜索DFS2广度优先搜索BFS3Dijkstra算法4Prim算法5Kruskal算法6Floyd-Warshall算法 总结 前言
提示这里可以添加本文要记录的大概内容
第一天Python数据结构与算法的详细介绍 第二天五种常见的排序算法 第三天两种常见的搜索算法 第四天两种常见的递归算法 第五天一种常见的动态规划算法 第六天一种常见的贪心算法 第七天一种常见的分治算法 第八天一种常见的回溯算法 第九天六种常见的图论算法
提示以下是本篇文章正文内容下面案例可供参考
一、Python数据结构与算法的详细介绍
1.Python中的常用的图论算法
以下是Python中的一些常用算法
2. 图论算法 图论算法 深度优先搜索DFS 用途用于图的遍历或路径查找。 时间复杂度O(VE)其中V是顶点数E是边数。 空间复杂度O(V)递归栈空间。广度优先搜索BFS 用途用于图的遍历或最短路径查找无权图。 时间复杂度O(VE)。 空间复杂度O(V)队列空间。Dijkstra算法 用途用于计算单源最短路径有权图。 时间复杂度O(V^2)朴素实现或O((VE) 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, visitedNone):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)3Dijkstra算法
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# 优先队列存储距离顶点对初始时只包含源点0startpriority_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})4Prim算法
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(Prims MST:, prim(graph))5Kruskal算法
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(Kruskals MST:, kruskal(graph))6Floyd-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)总结
提示这里对文章进行总结 例如以上就是今天要讲的内容本文简单介绍六种常见的图论算法。
