Networkx 算法

# NetworkX 图算法 ## 最短路径 ### 单源最短路径 python # Dijkstra 算法 (加权图) path = nx.shortest_path(G, source=1, target=5, weight='weight') length = nx.shortest_path_length(G, source=1, target=5, weight='weight') # 从源点出发的所有最短路径 paths = nx.single_source_shortest_path(G, source=1) lengths = nx.single_source_shortest_path_length(G, source=1) # Bellman-Ford (处理负权重) path = nx.bellman_ford_path(G, source=1, target=5, weight='weight') ### 全对最短路径 python # 全对 (返回迭代器) for source, paths in nx.all_pairs_shortest_path(G): print(f"从 {source} 出发: {paths}") # Floyd-Warshall 算法 lengths = dict(nx.all_pairs_shortest_path_length(G)) ### 专用最短路径算法 python # A* 算法 (带启发式函数) def heuristic(u, v): # 自定义启发式函数 return abs(u - v) path = nx.astar_path(G, source=1, target=5, heuristic=heuristic, weight='weight') # 平均最短路径长度 avg_length = nx.average_shortest_path_length(G) ## 连通性 ### 连通分量 (无向图) python # 检查是否连通 is_connected = nx.is_connected(G) # 分量数量 num_components = nx.number_connected_components(G) # 获取所有分量 (返回集合的迭代器) components = list(nx.connected_components(G)) largest_component = max(components, key=len) # 获取包含特定节点的分量 component = nx.node_connected_component(G, node=1) ### 强/弱连通性 (有向图) python # 强连通 (相互可达) is_strongly_connected = nx.is_strongly_connected(G) strong_components = list(nx.strongly_connected_components(G)) largest_scc = max(strong_components, key=len) # 弱连通 (忽略方向) is_weakly_connected = nx.is_weakly_connected(G) weak_components = list(nx.weakly_connected_components(G)) # 凝聚 (强连通分量的 DAG) condensed = nx.condensation(G) ### 割与连通度 python # 最小节点/边割 min_node_cut = nx.minimum_node_cut(G, s=1, t=5) min_edge_cut = nx.minimum_edge_cut(G, s=1, t=5) # 节点/边连通度 node_connectivity = nx.node_connectivity(G) edge_connectivity = nx.edge_connectivity(G) ## 中心性度量 ### 度中心性 python # 每个节点连接到的节点比例 degree_cent = nx.degree_centrality(G) # 用于有向图 in_degree_cent = nx.in_degree_cent