企业官网建设流程全解析

网站网站建设的原则有哪些,二级分销模式图,制作公司网站 黑龙江,买域名必须买服务器吗图搜索算法是解决图论问题的核心工具#xff0c;在计算机科学、人工智能、网络路由等领域有广泛应用。#x1f4ca; 图的基本概念什么是图#xff1f;图(Graph)由顶点(Vertex/Node)和边(Edge)组成#xff0c;用于表示对象之间的关系。from collections import defaultdict,…图搜索算法是解决图论问题的核心工具在计算机科学、人工智能、网络路由等领域有广泛应用。 图的基本概念什么是图图(Graph)由顶点(Vertex/Node)和边(Edge)组成用于表示对象之间的关系。from collections import defaultdict, deque from typing import List, Dict, Set, Optional, Tuple class Graph: def __init__(self, directedFalse): self.graph defaultdict(list) self.directed directed self.vertices set() def add_vertex(self, vertex): 添加顶点 self.vertices.add(vertex) def add_edge(self, u, v, weight1): 添加边 self.vertices.add(u) self.vertices.add(v) self.graph[u].append((v, weight)) if not self.directed: self.graph[v].append((u, weight)) def get_neighbors(self, vertex): 获取邻居节点 return self.graph[vertex] def display(self): 显示图结构 for vertex in self.vertices: neighbors [f{v}(w:{w}) for v, w in self.graph[vertex]] print(f{vertex}: {neighbors}) # 示例创建图 g Graph(directedFalse) g.add_edge(A, B, 4) g.add_edge(A, C, 2) g.add_edge(B, C, 1) g.add_edge(B, D, 5) g.add_edge(C, D, 8) g.add_edge(C, E, 10) g.add_edge(D, E, 2) g.add_edge(D, F, 6) g.add_edge(E, F, 3) print(图结构:) g.display() 深度优先搜索 (DFS)核心思想沿着一条路径尽可能深入地访问节点直到无法继续才回溯。递归实现def dfs_recursive(graph: Dict[str, List[Tuple[str, int]]], start: str, visited: Optional[Set[str]] None) - List[str]: 递归DFS实现 时间复杂度: O(V E) 空间复杂度: O(V) - 递归栈和访问集合 if visited is None: visited set() visited.add(start) traversal_order [start] for neighbor, _ in graph[start]: if neighbor not in visited: traversal_order.extend(dfs_recursive(graph, neighbor, visited)) return traversal_order # 使用示例 print(递归DFS遍历:, dfs_recursive(g.graph, A))迭代实现 (栈)def dfs_iterative(graph: Dict[str, List[Tuple[str, int]]], start: str) - List[str]: 迭代DFS - 使用栈避免递归深度限制 visited set() stack [start] traversal_order [] while stack: node stack.pop() if node not in visited: visited.add(node) traversal_order.append(node) # 逆序添加邻居以保持一致的遍历顺序 for neighbor, _ in reversed(graph[node]): if neighbor not in visited: stack.append(neighbor) return traversal_order print(迭代DFS遍历:, dfs_iterative(g.graph, A))DFS的应用def detect_cycle_dfs(graph: Dict[str, List[str]]) - bool: 使用DFS检测环 visited set() rec_stack set() def dfs_util(node): visited.add(node) rec_stack.add(node) for neighbor, _ in graph[node]: if neighbor not in visited: if dfs_util(neighbor): return True elif neighbor in rec_stack: return True rec_stack.remove(node) return False for vertex in graph: if vertex not in visited: if dfs_util(vertex): return True return False # 拓扑排序 (有向无环图) def topological_sort_dfs(graph: Dict[str, List[str]]) - List[str]: DFS实现拓扑排序 visited set() temp_visited set() result [] def dfs_topo(node): if node in temp_visited: raise ValueError(图中存在环无法进行拓扑排序) if node not in visited: temp_visited.add(node) for neighbor, _ in graph[node]: dfs_topo(neighbor) temp_visited.remove(node) visited.add(node) result.append(node) for vertex in graph: if vertex not in visited: dfs_topo(vertex) return result[::-1] # 反转得到正确顺序 广度优先搜索 (BFS)核心思想逐层访问节点先访问距离起始节点最近的节点。队列实现from collections import deque def bfs(graph: Dict[str, List[Tuple[str, int]]], start: str) - List[Tuple[str, int]]: BFS实现 - 使用队列 时间复杂度: O(V E) 空间复杂度: O(V) visited set([start]) queue deque([(start, 0)]) # (节点, 距离) traversal_order [] while queue: node, distance queue.popleft() traversal_order.append((node, distance)) for neighbor, weight in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, distance weight)) return traversal_order print(BFS遍历及距离:) bfs_result bfs(g.graph, A) for node, dist in bfs_result: print(f节点 {node}: 距离起点 {dist})BFS的应用def shortest_path_bfs(graph: Dict[str, List[str]], start: str, end: str) - Tuple[List[str], int]: 使用BFS找最短路径(无权图) if start end: return [start], 0 visited set() queue deque([(start, [start], 0)]) # (当前节点, 路径, 距离) while queue: node, path, distance queue.popleft() if node end: return path, distance if node not in visited: visited.add(node) for neighbor, _ in graph[node]: if neighbor not in visited: new_path path [neighbor] queue.append((neighbor, new_path, distance 1)) return [], -1 # 无路径 # 连通分量检测 def find_connected_components(graph: Dict[str, List[str]]) - List[List[str]]: 使用BFS找连通分量 visited set() components [] for vertex in graph: if vertex not in visited: # 找到一个新的连通分量 component [] queue deque([vertex]) visited.add(vertex) while queue: node queue.popleft() component.append(node) for neighbor, _ in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) components.append(component) return components⚡ 最短路径算法Dijkstra算法 (带权图最短路径)import heapq def dijkstra(graph: Dict[str, List[Tuple[str, int]]], start: str) - Dict[str, Tuple[int, str]]: Dijkstra算法 - 单源最短路径 适用于非负权重图 时间复杂度: O((VE)logV) 使用优先队列 distances {vertex: float(infinity) for vertex in graph} previous {vertex: None for vertex in graph} distances[start] 0 # 优先队列: (距离, 节点) priority_queue [(0, start)] while priority_queue: current_distance, current_node heapq.heappop(priority_queue) # 如果找到更短的路径跳过 if current_distance distances[current_node]: continue for neighbor, weight in graph[current_node]: distance current_distance weight # 找到更短的路径 if distance distances[neighbor]: distances[neighbor] distance previous[neighbor] current_node heapq.heappush(priority_queue, (distance, neighbor)) return distances, previous def reconstruct_path(previous: Dict[str, str], start: str, end: str) - List[str]: 重构最短路径 path [] current end while current is not None: path.append(current) current previous[current] return path[::-1] # 反转路径 # 使用Dijkstra算法 distances, previous dijkstra(g.graph, A) print(\nDijkstra最短路径结果:) for vertex in sorted(distances.keys()): path reconstruct_path(previous, A, vertex) print(fA - {vertex}: 距离{distances[vertex]}, 路径{ - .join(path)})Bellman-Ford算法 (支持负权边)def bellman_ford(graph: Dict[str, List[Tuple[str, int]]], vertices: List[str], start: str) - Tuple[Dict[str, int], bool]: Bellman-Ford算法 - 支持负权边的最短路径 时间复杂度: O(VE) distances {vertex: float(infinity) for vertex in vertices} distances[start] 0 # 松弛操作 V-1 次 for _ in range(len(vertices) - 1): for u in graph: for v, weight in graph[u]: if distances[u] weight distances[v]: distances[v] distances[u] weight # 检查负权环 for u in graph: for v, weight in graph[u]: if distances[u] weight distances[v]: return {}, True # 存在负权环 return distances, False # 创建带负权边的图测试Bellman-Ford neg_graph Graph() neg_graph.add_edge(A, B, 4) neg_graph.add_edge(A, C, 2) neg_graph.add_edge(B, C, -1) # 负权边 neg_graph.add_edge(B, D, 5) neg_graph.add_edge(C, D, 8) distances_neg, has_negative_cycle bellman_ford( neg_graph.graph, list(neg_graph.vertices), A ) print(f\nBellman-Ford结果: {存在负权环 if has_negative_cycle else 无负权环}) 其他重要图算法Floyd-Warshall算法 (所有点对最短路径)def floyd_warshall(graph: Dict[str, Dict[str, int]]) - Dict[str, Dict[str, int]]: Floyd-Warshall算法 - 所有点对最短路径 时间复杂度: O(V^3) 支持负权边但不能有负权环 vertices list(graph.keys()) n len(vertices) # 初始化距离矩阵 dist {u: {v: float(infinity) for v in vertices} for u in vertices} # 设置直接相连的边 for u in graph: dist[u][u] 0 for v, weight in graph[u].items(): dist[u][v] weight # Floyd-Warshall核心算法 for k in vertices: for i in vertices: for j in vertices: if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j] return dist最小生成树算法Prim算法def prim_mst(graph: Dict[str, List[Tuple[str, int]]]) - List[Tuple[str, str, int]]: Prim算法 - 最小生成树 时间复杂度: O(E log V) 使用优先队列 if not graph: return [] start_vertex next(iter(graph)) visited set([start_vertex]) edges [(weight, start_vertex, neighbor) for neighbor, weight in graph[start_vertex]] heapq.heapify(edges) mst [] while edges and len(visited) len(graph): weight, u, v heapq.heappop(edges) if v in visited: continue visited.add(v) mst.append((u, v, weight)) # 添加新顶点的所有边 for neighbor, edge_weight in graph[v]: if neighbor not in visited: heapq.heappush(edges, (edge_weight, v, neighbor)) return mst 算法比较总结算法时间复杂度空间复杂度适用场景特点DFS​O(VE)O(V)拓扑排序、连通性、环检测内存效率高可能找不到最短路径BFS​O(VE)O(V)最短路径(无权)、层次遍历保证找到最短路径内存消耗大Dijkstra​O((VE)logV)O(V)最短路径(非负权)高效不支持负权Bellman-Ford​O(VE)O(V)最短路径(含负权)支持负权检测负环Floyd-Warshall​O(V³)O(V²)所有点对最短路径简单但效率低Prim​O(E log V)O(V)最小生成树稠密图效果好️ 实际应用示例社交网络分析class SocialNetwork: def __init__(self): self.graph defaultdict(list) def add_friendship(self, person1, person2): self.graph[person1].append(person2) self.graph[person2].append(person1) def find_friends_degree(self, start_person, target_person): 寻找两个人之间的度数(朋友的朋友...) if start_person target_person: return 0, [start_person] visited set() queue deque([(start_person, 0, [start_person])]) # (人, 度数, 路径) while queue: person, degree, path queue.popleft() if person target_person: return degree, path if person not in visited: visited.add(person) for friend in self.graph[person]: if friend not in visited: queue.append((friend, degree 1, path [friend])) return -1, [] # 无连接 # 使用示例 social SocialNetwork() social.add_friendship(Alice, Bob) social.add_friendship(Bob, Charlie) social.add_friendship(Charlie, David) social.add_friendship(Alice, Eve) degree, path social.find_friends_degree(Alice, David) print(f\n社交网络: Alice和David相差{degree}度) print(f连接路径: { - .join(path)})图搜索算法是计算机科学的基石掌握这些算法对于解决复杂问题和面试都至关重要