网站的总体风格包括企业网站app开发平台

网站的总体风格包括,企业网站app开发平台,南通做网站推广的公司,营销宣传策划方案一、引言 图是一种强大的数据结构#xff0c;用于表示对象之间的关系。从社交网络到路线规划#xff0c;从网页连接到生物信息学#xff0c;图算法在计算机科学的各个领域都有着广泛的应用。本文将介绍图的基本概念、常见算法及其实现。 二、图的表示方法 邻接矩阵 class Gr…一、引言图是一种强大的数据结构用于表示对象之间的关系。从社交网络到路线规划从网页连接到生物信息学图算法在计算机科学的各个领域都有着广泛的应用。本文将介绍图的基本概念、常见算法及其实现。二、图的表示方法邻接矩阵classGraphMatrix:def__init__(self,vertices):self.Vvertices self.graph[[0]*verticesfor_inrange(vertices)]defadd_edge(self,u,v,weight1,directedFalse):self.graph[u][v]weightifnotdirected:self.graph[v][u]weightdefprint_graph(self):foriinrange(self.V):print(f顶点{i}:{self.graph[i]})邻接表更节省空间fromcollectionsimportdefaultdictclassGraphAdjList:def__init__(self,directedFalse):self.graphdefaultdict(list)self.directeddirected self.verticesset()defadd_edge(self,u,v,weight1):self.graph[u].append((v,weight))self.vertices.add(u)self.vertices.add(v)ifnotself.directed:self.graph[v].append((u,weight))defprint_graph(self):forvertexinself.graph:print(f{vertex}:{self.graph[vertex]})三、基础图遍历算法深度优先搜索 (DFS)defdfs_recursive(graph,start,visitedNone):递归实现DFSifvisitedisNone:visitedset()visited.add(start)print(start,end )forneighbor,_ingraph.get(start,[]):ifneighbornotinvisited:dfs_recursive(graph,neighbor,visited)returnvisiteddefdfs_iterative(graph,start):迭代实现DFSvisitedset()stack[start]whilestack:vertexstack.pop()ifvertexnotinvisited:print(vertex,end )visited.add(vertex)# 将邻居逆序加入栈中以保持与递归相同的遍历顺序forneighbor,_inreversed(graph.get(vertex,[])):ifneighbornotinvisited:stack.append(neighbor)returnvisited广度优先搜索 (BFS)fromcollectionsimportdequedefbfs(graph,start):BFS实现visitedset([start])queuedeque([start])whilequeue:vertexqueue.popleft()print(vertex,end )forneighbor,_ingraph.get(vertex,[]):ifneighbornotinvisited:visited.add(neighbor)queue.append(neighbor)returnvisited四、最短路径算法Dijkstra算法单源最短路径权重非负importheapqdefdijkstra(graph,start):Dijkstra最短路径算法# 初始化距离字典distances{vertex:float(inf)forvertexingraph}distances[start]0previous{vertex:Noneforvertexingraph}# 优先队列priority_queue[(0,start)]whilepriority_queue:current_distance,current_vertexheapq.heappop(priority_queue)# 如果当前距离大于已知最短距离跳过ifcurrent_distancedistances[current_vertex]:continue# 更新邻居节点的距离forneighbor,weightingraph.get(current_vertex,[]):distancecurrent_distanceweightifdistancedistances[neighbor]:distances[neighbor]distance previous[neighbor]current_vertex heapq.heappush(priority_queue,(distance,neighbor))returndistances,previousdefget_path(previous,target):从previous字典重构路径path[]currenttargetwhilecurrentisnotNone:path.append(current)currentprevious[current]returnpath[::-1]Floyd-Warshall算法所有节点对最短路径deffloyd_warshall(graph_matrix,vertices):Floyd-Warshall算法# 初始化距离矩阵dist[[float(inf)]*verticesfor_inrange(vertices)]foriinrange(vertices):dist[i][i]0forj,weightinenumerate(graph_matrix[i]):ifweight!0:dist[i][j]weight# 动态规划forkinrange(vertices):foriinrange(vertices):forjinrange(vertices):ifdist[i][j]dist[i][k]dist[k][j]:dist[i][j]dist[i][k]dist[k][j]returndist五、最小生成树算法Prim算法defprim_mst(graph,start):Prim最小生成树算法mst[]visitedset([start])edges[]# 初始化起始点的边forneighbor,weightingraph.get(start,[]):heapq.heappush(edges,(weight,start,neighbor))whileedgesandlen(visited)len(graph):weight,u,vheapq.heappop(edges)ifvnotinvisited:visited.add(v)mst.append((u,v,weight))# 添加新顶点的边forneighbor,wingraph.get(v,[]):ifneighbornotinvisited:heapq.heappush(edges,(w,v,neighbor))returnmstKruskal算法classDisjointSet:并查集实现用于Kruskal算法def__init__(self,vertices):self.parent{v:vforvinvertices}self.rank{v:0forvinvertices}deffind(self,v):ifself.parent[v]!v:self.parent[v]self.find(self.parent[v])returnself.parent[v]defunion(self,v1,v2):root1self.find(v1)root2self.find(v2)ifroot1!root2:ifself.rank[root1]self.rank[root2]:self.parent[root2]root1elifself.rank[root1]self.rank[root2]:self.parent[root1]root2else:self.parent[root2]root1 self.rank[root1]1returnTruereturnFalsedefkruskal_mst(graph):Kruskal最小生成树算法edges[]verticesset()# 收集所有边foruingraph:vertices.add(u)forv,weightingraph.get(u,[]):vertices.add(v)edges.append((weight,u,v))# 按权重排序edges.sort()# 初始化并查集dsDisjointSet(vertices)mst[]forweight,u,vinedges:ifds.union(u,v):mst.append((u,v,weight))iflen(mst)len(vertices)-1:breakreturnmst六、拓扑排序用于有向无环图deftopological_sort_kahn(graph):Kahn算法实现拓扑排序# 计算入度in_degree{vertex:0forvertexingraph}foruingraph:forv,_ingraph[u]:in_degree[v]in_degree.get(v,0)1# 初始化队列queuedeque([vforvingraphifin_degree.get(v,0)0])topo_order[]whilequeue:uqueue.popleft()topo_order.append(u)forv,_ingraph.get(u,[]):in_degree[v]-1ifin_degree[v]0:queue.append(v)iflen(topo_order)len(graph):returntopo_orderelse:# 图中存在环returnNonedeftopological_sort_dfs(graph):DFS实现拓扑排序visitedset()tempset()# 临时标记用于检测环stack[]defdfs(vertex):ifvertexintemp:# 检测到环raiseValueError(图中有环无法进行拓扑排序)ifvertexinvisited:returntemp.add(vertex)forneighbor,_ingraph.get(vertex,[]):dfs(neighbor)temp.remove(vertex)visited.add(vertex)stack.append(vertex)forvertexingraph:ifvertexnotinvisited:dfs(vertex)returnstack[::-1]七、应用示例社交网络分析classSocialNetworkAnalyzer:def__init__(self):self.graphGraphAdjList(directedFalse)defadd_friendship(self,person1,person2,strength1):self.graph.add_edge(person1,person2,strength)deffind_degrees_of_separation(self,start,target):使用BFS查找两个人之间的分离度数ifstarttarget:return0visitedset([start])queuedeque([(start,0)])# (person, distance)whilequeue:current_person,distancequeue.popleft()forneighbor,_inself.graph.graph.get(current_person,[]):ifneighbortarget:returndistance1ifneighbornotinvisited:visited.add(neighbor)queue.append((neighbor,distance1))return-1# 没有路径deffind_influential_people(self,top_n5):使用度中心性查找最有影响力的人centrality{}forpersoninself.graph.vertices:centrality[person]len(self.graph.graph.get(person,[]))# 按中心性排序sorted_centralitysorted(centrality.items(),keylambdax:x[1],reverseTrue)returnsorted_centrality[:top_n]deffind_communities(self):使用DFS查找连通分量社区visitedset()communities[]forpersoninself.graph.vertices:ifpersonnotinvisited:communitydfs_recursive(self.graph.graph,person,set())visited.update(community)communities.append(community)returncommunities# 使用示例if__name____main__:# 创建图graphGraphAdjList()graph.add_edge(0,1,4)graph.add_edge(0,7,8)graph.add_edge(1,2,8)graph.add_edge(1,7,11)graph.add_edge(2,3,7)graph.add_edge(2,8,2)graph.add_edge(2,5,4)graph.add_edge(3,4,9)graph.add_edge(3,5,14)graph.add_edge(4,5,10)graph.add_edge(5,6,2)graph.add_edge(6,7,1)graph.add_edge(6,8,6)graph.add_edge(7,8,7)print(图结构:)graph.print_graph()print(\nDFS遍历 (从节点0开始):)dfs_recursive(graph.graph,0)print(\n\nBFS遍历 (从节点0开始):)bfs(graph.graph,0)print(\n\nDijkstra最短路径 (从节点0开始):)distances,previousdijkstra(graph.graph,0)forvertexindistances:print(f到节点{vertex}的最短距离:{distances[vertex]})print(f路径:{get_path(previous,vertex)})print(\nPrim最小生成树:)mst_primprim_mst(graph.graph,0)print(f最小生成树边:{mst_prim})total_weightsum(weightfor_,_,weightinmst_prim)print(f总权重:{total_weight})# 社交网络示例print(\n--- 社交网络分析示例 ---)social_netSocialNetworkAnalyzer()social_net.add_friendship(Alice,Bob)social_net.add_friendship(Alice,Charlie)social_net.add_friendship(Bob,David)social_net.add_friendship(Charlie,David)social_net.add_friendship(David,Eve)social_net.add_friendship(Frank,Grace)print(fAlice和Eve之间的分离度数:{social_net.find_degrees_of_separation(Alice,Eve)})print(f最有影响力的人:{social_net.find_influential_people(3)})print(f发现的社区:{social_net.find_communities()})八、总结与扩展本文介绍了图的基本表示方法和几种核心算法。图算法的应用远不止于此还包括网络流算法如Ford-Fulkerson算法解决最大流问题图匹配算法如匈牙利算法解决二分图匹配强连通分量Kosaraju或Tarjan算法图着色问题用于调度和寄存器分配旅行商问题启发式算法如遗传算法、模拟退火图算法的选择取决于具体问题对于无权图最短路径使用BFS对于有权图非负权最短路径使用Dijkstra对于负权图最短路径使用Bellman-Ford对于所有节点对最短路径使用Floyd-Warshall对于最小生成树Prim适合稠密图Kruskal适合稀疏图理解这些基础算法是解决更复杂图问题的基础也是许多实际应用的核心。